Как работают равномерные, префиксные коды и условие Фано?

Кодирование сопоставляет символам исходного алфавита слова другого алфавита. В равномерном коде все кодовые слова имеют одинаковую длину, поэтому границы читаются по…

Кодирование сопоставляет символам исходного алфавита слова другого алфавита. В равномерном коде все кодовые слова имеют одинаковую длину, поэтому границы читаются по фиксированному числу знаков. Неравномерный код может быть короче в среднем, но требует правила однозначного разбиения потока.

Префиксное свойство

Если ни одно кодовое слово не является началом другого, код называют префиксным. Декодер читает поток слева направо и завершает символ сразу после совпадения с кодовым словом. Такое условие Фано достаточно для однозначного декодирования без разделителей, хотя существуют однозначные коды, которые не являются префиксными.

Обратное условие

В задачах встречается и суффиксный вариант: ни одно слово не должно быть окончанием другого. Тогда сообщение удобно разбирать справа налево. Нельзя механически применять префиксную проверку, если условие прямо задаёт обратный порядок декодирования.

Частоты и код Хаффмана

Часто встречающимся символам выгодно назначать короткие слова, редким — длинные. Алгоритм Хаффмана последовательно объединяет два наименее частых узла и строит двоичное дерево. Итоговый код префиксный, а длина сообщения вычисляется как сумма произведений частоты символа на длину его слова.

Код символа и кодировка текста

ASCII покрывает ограниченный набор знаков, а Unicode задаёт универсальные кодовые позиции. Способ хранения этих позиций, например UTF-8, — отдельный уровень. Количество символов строки поэтому не обязано совпадать с количеством байтов, и привычное «один знак — один байт» ненадёжно для кириллицы.

Алгоритм решения

Сначала выпишите кодовую таблицу и проверьте нужное свойство попарно. Затем декодируйте строго в указанном направлении, не угадывая слова по смыслу. Для оптимизации постройте дерево и посчитайте взвешенную длину. Контрольный пример должен снова кодироваться в исходный поток без остатка.

Проверка кода как дерева

Префиксный код удобно хранить в боре: ребро соответствует биту, а вершина отмечает конец символа. Во время вставки конфликт возникает в двух случаях. Мы встречаем уже завершённое слово до конца нового — старое слово является префиксом. Либо после вставки у конечной вершины остаются потомки — новое слово стало префиксом старого. Такая проверка надёжнее визуального сравнения длинного списка.

def is_prefix_code(words: list[str]) -> bool:
    trie: dict[str, dict] = {}
    terminal = "end"
    for word in words:
        node = trie
        for bit in word:
            if terminal in node:
                return False
            node = node.setdefault(bit, {})
        if terminal in node or node:
            return False
        node[terminal] = {}
    return True

print(is_prefix_code(["0", "10", "110", "111"]))  # True
print(is_prefix_code(["0", "01", "11"]))            # False

Алгоритм проходит каждый бит один раз, поэтому время пропорционально суммарной длине слов. Для обратного условия Фано можно обратить каждое слово и применить тот же тест: суффиксы исходных слов станут префиксами обращённых.

Практика: декодер с диагностикой

Возьмите таблицу A→0, B→10, C→110, D→111 и декодируйте поток 011010111 вручную и программой. Декодер должен сообщать позицию, если ни одно продолжение невозможно, и обнаруживать незавершённый хвост. Затем добавьте слово 01 и объясните конкретный конфликт. В дополнительной части посчитайте среднюю длину при частотах 40, 30, 20 и 10 и сравните её с равномерным двухбитовым кодом.