Префиксные коды и условие Фано

Как закодировать символы битами разной длины так, чтобы поток всегда читался однозначно — без пробелов и разделителей.

Префиксный код — двоичный код, в котором ни одно кодовое слово не является началом (префиксом) другого. Такой код декодируется однозначно, даже если коды у символов разной длины.

В базовых уроках мы кодировали каждый символ фиксированным числом бит: при алфавите из $N$ символов нужно $i = \lceil \log_2 N \rceil$ бит на знак. Это удобно, но расточительно. Буква «о» в русском тексте встречается в сотни раз чаще, чем «ъ», а тратим мы на них одинаково. Идея сжатия — частым символам дать короткие коды, редким — длинные. Тогда средняя длина записи символа падает, и весь текст занимает меньше.

Но возникает проблема. Если «а» = 0, «б» = 01, то поток 001 читается двумя способами: «аб» или «аа?» — декодер запутается. Чтобы коды переменной длины оставались читаемыми без разделителей, нужно особое свойство.

Зачем нужны коды переменной длины

Представьте сообщение из 4 символов А, Б, В, Г. Равномерный код требует 2 бита на символ: А=00, Б=01, В=10, Г=11. Сообщение из 100 символов займёт 200 бит независимо от содержания.

Пусть теперь А встречается в 70% случаев, Б — в 20%, В и Г — по 5%. Дадим коды разной длины: А=0 (1 бит), Б=10 (2 бита), В=110, Г=111 (по 3 бита). Средняя длина символа:

$$ L = 0{,}7 \cdot 1 + 0{,}2 \cdot 2 + 0{,}05 \cdot 3 + 0{,}05 \cdot 3 = 1{,}4 \text{ бита} $$

Вместо 2 бит — 1,4. Те же 100 символов теперь займут в среднем 140 бит вместо 200: выигрыш 30%. Чем сильнее перекос частот, тем больше экономия.

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

Чтобы поток 0101100111 читался однозначно, код обязан быть префиксным: ни один код не должен совпадать с началом другого. Проверим набор А=0, Б=10, В=110, Г=111. Код «0» — не начало ни одного из 10, 110, 111 (все они начинаются с 1). Код «10» — не начало 110 и 111 (у тех после 1 идёт 1, а не 0). Свойство выполнено.

Декодирование идёт слева направо: читаем биты, пока не соберём ровно один код, выдаём символ и начинаем заново. Разберём 0101100111:

Шаг	Накоплено	Распознано
1	`0`	А
2	`10`	Б
3	`110`	В
4	`0`	А
5	`111`	Г

Получили «АБВАГ» — единственное прочтение. Никакие разделители не понадобились.

Дерево кодов

Любой двоичный код удобно представить деревом: из каждого узла влево ведёт ветка «0», вправо — «1». Спускаясь от корня по битам кода, мы приходим к узлу-символу. Для нашего набора:

Ключевое наблюдение: в префиксном коде все символы сидят только в листьях (концах веток), а внутренние узлы пусты. Если бы какой-то символ оказался во внутреннем узле, путь к нему был бы началом путей к символам ниже — а это и есть нарушение префиксности.

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

В школьном курсе и на ЕГЭ префиксность формулируют как условие Фано.

Условие Фано: ни одно кодовое слово не является началом другого. Достаточно для однозначного декодирования слева направо.
Обратное условие Фано: ни одно кодовое слово не является окончанием другого. Достаточно для однозначного декодирования справа налево.

Это два разных, независимых условия. Код может удовлетворять прямому, обратному, обоим сразу или ни одному. Если выполнено хотя бы одно из них — код декодируется однозначно (в соответствующую сторону).

Пример на различие. Коды А=1, Б=01, В=001. Прямое условие Фано: «1» не начинает «01» и «001», «01» не начинает «001» — выполнено. Обратное: «1» является окончанием и «01», и «001» — нарушено. Значит, читать такой поток можно слева направо, но не справа налево.

Как это работает

Откуда берётся гарантия однозначности? Когда декодер читает биты слева направо и набранная цепочка совпала с кодом какого-то символа, в префиксном коде эта цепочка не может быть началом другого, более длинного кода. Значит, продолжать чтение бессмысленно — символ определён единственным образом. Декодер фиксирует его и стартует с пустого. Ошибиться негде: на каждом шаге ровно один символ заканчивается ровно в этой точке.

На дереве это видно нагляднее. Декодирование — спуск от корня по битам. Как только мы попали в лист, мы обязаны вернуться в корень: вниз идти некуда, символ прочитан. Поскольку символы только в листьях, момент «символ собран» всегда определён однозначно.

Неравенство Крафта

Есть точный критерий, когда префиксный код с заданными длинами кодов $l_1, l_2, \ldots, l_n$ вообще существует, — неравенство Крафта:

$$ \sum_{i=1}^{n} 2^{-l_i} \le 1 $$

Для нашего набора длин 1, 2, 3, 3: $2^{-1} + 2^{-2} + 2^{-3} + 2^{-3} = 0{,}5 + 0{,}25 + 0{,}125 + 0{,}125 = 1$. Сумма равна 1 — код существует и при этом «плотный»: свободного места в дереве не осталось.

Разбор задания 4 ЕГЭ

Типовая формулировка: «По каналу передаются сообщения из букв А, Б, В, Г. Для А используется код 00, для Б — 11. Укажите кратчайшие коды для В и Г, чтобы код удовлетворял условию Фано и при этом суммарная длина кодов В и Г была минимальной».

Решаем через дерево. Заняты пути 00 (А) и 11 (Б). На длине 2 свободны 01 и 10. Но если взять В=01 и Г=10 — это и есть кратчайший вариант (по 2 бита). Проверяем префиксность: ни 00, ни 01, ни 10, ни 11 не начинают друг друга (все длины 2 и все различны). Условие Фано выполнено, суммарная длина В и Г равна 4 — минимум.

Другой вариант задания: «А=0, Б=10. Найдите кратчайшие коды В и Г». Раз А=0, то ни один код больше не может начинаться с 0 (иначе А — его префикс). Все остальные коды начинаются с 1. Б=10 заняло путь 1→0. Свободна ветка 11; от неё кратчайшие листья — 110 и 111. Значит В=110, Г=111 (по 3 бита), суммарно 6.

Дерево к варианту А=0, Б=10:
       корень
      0/    \1
      А      *
          0/   \1
          Б     *
              0/  \1
            110   111
             В     Г

Частые ошибки

Путают прямое и обратное Фано. «Начало другого кода» и «окончание другого кода» — разные вещи. На ЕГЭ почти всегда спрашивают прямое условие (про начало).
Берут код, который начинает другой. Если А=0, то Б не может быть 01: «0» — префикс «01». Декодер не отличит А+что-то от начала Б.
Ищут не кратчайшие коды. В задании 4 нужны именно минимальные по длине свободные пути в дереве; берут первый попавшийся длинный код и теряют баллы.
Думают, что любой код переменной длины однозначен. Без префиксного свойства (или обратного) поток читается неоднозначно — это и есть суть условия Фано.

Итоги

Коды переменной длины экономят память: частым символам — короткие коды, редким — длинные.
Чтобы поток без разделителей читался однозначно, код должен быть префиксным.
Условие Фано: ни один код не начинает другой (декодирование слева направо). Обратное Фано — про окончания (справа налево).
Префиксный код = дерево, где символы только в листьях.
Неравенство Крафта $\sum 2^{-l_i} \le 1$ говорит, существует ли код с такими длинами.
В задании 4 ЕГЭ ищите кратчайшие свободные пути в дереве кодов.