<?php

function normalize($first, $second) {
    $diff = array_sum($first) - array_sum($second);

    list($first, $second) = $diff > 0 ? [$second, $first] : [$first, $second];

    $diff = abs($diff / 2);

    $maxChar = null;
    $maxCount = 0;

    foreach ($second as $char => $count) {
        if ($count <= $diff) {
            if ($count > $maxCount) {
                $maxCount = $count;
                $maxChar = $char;
            }
        }
    }

    if ($maxChar === null) {
        return [$first, $second, false];
    }

    $first[$maxChar] = $maxCount;

    unset($second[$maxChar]);

    return [$first, $second, true];
}

function divide_array($array) {
    $first = [];
    $second = [];

    $index = 0;
    $firstSum = 0;

    foreach ($array as $key => $value) {
        if (($firstSum + $value) > array_sum(array_slice($array, $index + 1))) {
            $second = array_splice($array, $index);

            break;
        }

        $first[$key] = $value;
        $firstSum += $value;

        $index++;
    }

    $needNormalization = true;

    while ($needNormalization) {
        list($first, $second, $needNormalization) = normalize($first, $second);
    }

    return [$first, $second];
}

function encode_alphabet($alphabet) {
    list($first, $second) = divide_array($alphabet);

    if (count($first) === 1) {
        $key = key($first);

        $firstCodes = [$key => '0'];
    } else {
        $firstCodes = [];

        foreach (encode_alphabet($first) as $char => $code) {
            $firstCodes[$char] = '0'.$code;
        }
    }

    if (count($second) === 1) {
        $key = key($second);

        $secondCodes = [$key => '1'];
    } else {
        $secondCodes = [];

        foreach (encode_alphabet($second) as $char => $code) {
            $secondCodes[$char] = '1'.$code;
        }
    }

    return array_merge($firstCodes, $secondCodes);
}

function encode_string($string)
{
    $chars = preg_split('//u', $string, -1, PREG_SPLIT_NO_EMPTY);
    $alphabet = array_count_values($chars);

    $codes = encode_alphabet($alphabet);

    $encodedString = str_replace(array_keys($codes), array_values($codes), $string);

    return [$codes, $encodedString];
}

function decode_string($encodedString, $codes) {
    uasort($codes, function ($a, $b){
        return mb_strlen($b) - mb_strlen($a);
    });

    $decodedString = '';

    while ($encodedString !== '') {
        foreach ($codes as $char => $code) {
            $len = mb_strlen($code);

            if ($len > mb_strlen($encodedString)) {
                continue;
            }

            if (mb_substr($encodedString, 0, $len) === $code) {
                $decodedString .= $char;
                $encodedString = mb_substr($encodedString, $len);

                break;
            }
        }
    }

    return $decodedString;
}

$string = 'Lorem ipsum dolor sit amet, consectetur adipisicing elit. Sequi perferendis dicta, atque veniam est labore.';

list($codes, $encodedString) = encode_string($string);

$decodedString = decode_string($encodedString, $codes);

echo $string === $decodedString ? "Equals" : "Not Equals", PHP_EOL;