Основы кодирования: префиксные коды и неравенство Крафта

Архиватор сжал документ с трёх мегабайт до полутора — без потерь: после распаковки совпал каждый байт. Откуда берётся такая щедрость? Из неравномерного кода: частые символы получают короткие цепочки бит, редкие — длинные. Схема работает, пока не возникает вопрос, который легко задать и трудно пережить: раз слова разной длины, где кончается одно слово и начинается следующее? Теория кодирования отвечает на него строго — через префиксные коды, неравенство Крафта—Макмиллана и жадный алгоритм Хаффмана. К концу урока вы построите оптимальный код вручную и проверите его на пределе сжатия.

Что значит закодировать сообщение?#

Пусть источник выдаёт символы алфавита $\{A,B,C,D\}$. Код — правило, которое каждому символу ставит в соответствие кодовое слово: цепочку нулей и единиц. Самый простой вариант — равномерный код: $A\to 00$, $B\to 01$, $C\to 10$, $D\to 11$, все слова по два бита. Разбить длинную цепочку на слова элементарно — режем по два бита, и каждому кусочку однозначно соответствует символ. На $m$ символов равномерный код тратит $\lceil {\log }_{2}m\rceil$ бит на символ: для шести символов это три бита — восемь возможных комбинаций, из которых хватает шести, две пустуют — платим за простоту.

Экономия на частотах — не мелочь. В живых текстах буквы распределены отнюдь не поровну: в русском тексте «о» и «е» занимают добрую треть всех букв, а «ъ» и «э» — доли процента. Архиваторы этим питаются: внутри форматов ZIP и gzip код Хаффмана трудится как часть алгоритма DEFLATE, JPEG кодирует им коэффициенты картинки, а MP3 — спектральные данные. Один и тот же жадный алгоритм с 1952 года экономит место в файловых архивах и в фотографии.

Экономия живёт в неравномерности: если $A$ встречается в половине сообщений, короткое слово для неё окупит длинные слова для редких букв. Но с разной длиной приходит беда. Возьмём код $\{A\to 0,B\to 01,C\to 1\}$ и цепочку $01$. Она читается двумя способами: как $B$ целиком и как $A$ с последующим $C$. Приёмник не восстановит сообщение, даже зная код идеально: код неоднозначно декодируем — брак, не подлежащий починке на стороне приёмника.

Почему префиксный код декодируется на лету?#

Префиксный код — код, в котором ни одно кодовое слово не является началом (префиксом) другого. В наборе $\{0,10,110,111\}$ ни одно слово не начинается с другого: ноль никогда не открывает десятку, десятка — сотню с единицей. Читаем цепочку слева направо, и как только накопленное совпало со словом — символ определён однозначно, следующий символ начинается с чистого листа. Никаких пауз, никаких возвратов назад; такое декодирование — работа для конечного автомата с двумя-тремя состояниями.

Префиксность имеет наглядную геометрию — кодовое дерево. Каждый бит — выбор ветви: ноль влево, единица вправо; кодовое слово — путь от корня. Требование префиксности означает: слова сидят только в листьях, ни одно не лежит на пути к другому. Именно поэтому прочтение всегда останавливается вовремя. Строить и обходить такие структуры учит урок о деревьях и алгоритмах, здесь же дерево — рабочая картинка, а не предмет изучения.

Что запрещает неравенство Крафта—Макмиллана?#

Какие наборы длин слов вообще возможны? Интуиция подсказывает: слишком много коротких слов разом — не выйдет, дерево не резиновое. Точная формулировка:

Смысл простой: двоичная ёмкость делится пополам с каждым битом. Слово длины 2 — это одна четверть всего пространства цепочек, слово длины 3 — одна восьмая. Складываем вклады всех слов — должно остаться не больше целого. Проверим на полном коде $\{0,10,110,111\}$:

Равенство означает полноту: добавить пятое слово, не разрушив префиксность, невозможно. А вот у набора длин $2,2,2,3$ (код $\{00,01,10,110\}$) сумма $\frac{3}{4}+\frac{1}{8}=\frac{7}{8}<1$ — есть запас, и слово $111$ добавимо. Мини-тренировка на полминуты: код $\{0,10\}$ даёт $\frac{1}{2}+\frac{1}{4}=\frac{3}{4}$ — запас есть, добавляем $110$ и $111$ и дотягиваемся до единицы. А пара $\{0,1\}$ уже исчерпала ёмкость дерева — третье слово к ней не пристроить в принципе.

Теорема Макмиллана добавляет неожиданное: неравенство обязано выполняться у любого однозначно декодируемого кода, даже не префиксного. А теорема Крафта — обратное: если длины прошли проверку, существует префиксный код с ровно этими длинами. Вместе выходит, что префиксные коды ничего не теряют: по длинам они не хуже любых однозначных, а декодируются проще. Отсюда и привычка всей теории: заниматься префиксными.

Как построить код Хаффмана по шагам?#

Идея: частым символам — короткие слова, редким — длинные. Алгоритм Хаффмана (1952) реализует её жадно: берём два самых редких символа (или узла), сливаем их в новый узел с суммарной частотой, возвращаем в список и повторяем, пока не останется один корень. Потом развешиваем по левым рёбрам нули, по правым единицы — и слова готовы. Прогоним на шести символах с частотами из сотни: $a$ — 45, $b$ — 13, $c$ — 12, $d$ — 16, $e$ — 9, $f$ — 5.

Деталь, о которую спотыкаются на контрольных: при равных весах порядок слияний неоднозначен, и коды двух прогонов могут отличаться словами. Это нормально: все варианты оптимальны одновременно — сумма вкладов одинакова, различаются лишь метки рёбер. На экзамене достаточно показать корректное дерево и посчитать среднюю длину; совпадать с ответом соседа должен не код, а число $2,24$.

Проверка по Крафту: $2^{-1}+3\cdot 2^{-3}+2\cdot 2^{-4}=\frac{1}{2}+\frac{3}{8}+\frac{1}{8}=1$ — код полный, длиннее и экономнее уже не бывает при этих частотах. Почему жадность не подводит: в оптимальном коде два самых редких символа обязаны сидеть на самой глубине и по соседству — иначе поменяем их местами с более глубокими листьями и улучшим код. Слияние пары просто фиксирует это обязательство, после чего задача уменьшается на один символ. Индукция заканчивает доказательство. Со списком, организованным в кучу, алгоритм работает за $O(n\log n)$; что стоит за такой записью — урок о сложности алгоритмов.

Куда упирается сжатие: энтропия#

Есть нижний предел, который не перепрыгнет никакой код. Энтропия распределения измеряет среднюю неожиданность символа:

Для любого однозначно декодируемого кода средняя длина не меньше энтропии: $\bar{L}\ge H$. В нашем примере частоты дают вероятности $0,45;0,13;0,12;0,16;0,09;0,05$, и $H\approx 2,22$ бита. Хаффман выдал $2,24$ — зазор в две сотых бита: до предела почти дотянулись, а дальше некуда.

Масштабируем на файл из 10 000 символов. Равномерный код: 30 000 бит. Хаффман: 22 400 бит. Энтропийный предел: около 22 200 бит. Побуквенным кодированием ниже не уйти — остаются блоки: кодировать пары и тройки символов как один знак нового алфавита, зазор до энтропии делится на длину блока. А если символы источника коррелируют (после «ч» в русском языке почти наверняка пойдёт гласная), энтропия блоков ещё ниже суммы энтропий букв.

Сжатие — половина дела кодирования. Вторая половина — защита от помех: туда, где биты теряются и портятся, избыточность добавляют сознательно, чтобы приёмник чинил ошибки. Как устроена такая арифметика — в парном уроке про коды Хэмминга; сжатие и помехоустойчивость — две стороны одного баланса между экономией и надёжностью.

• Равномерный код тратит $\lceil {\log }_{2}m\rceil$ бит на символ; неравномерный экономит, но требует разделения слов
• Префиксность — достаточное условие однозначного декодирования: слова — листья дерева, чтение останавливается вовремя
• Крафт—Макмиллан: $\sum 2^{-l_i}\le 1$ — обязательное условие для любых однозначных кодов; при выполнении префиксный код с этими длинами существует
• Хаффман: слияние двух самых редких, средняя длина оптимальна среди побуквенных префиксных кодов
• Энтропия $H$ — предел сжатия: $\bar{L}\ge H$, зазор сокращают блочным кодированием

Следующий шаг логичен: префиксные коды экономят биты, а помехоустойчивые — платят ими осознанно. Открывайте коды Хэмминга и посмотрите, как три контрольных бита чинят один сбитый. Практика по смежным темам — задачи по комбинаторике и тренажёр по графам; деревья и их обходы повторяются по шпаргалке по графам и алгоритмам.