Код Хаффмана

Код Хаффмана (Дэвид Хаффман, 1952) — способ сжатия без потерь: частым символам достаются короткие кодовые слова, редким — длинные. Среди всех префиксных кодов он даёт наименьшую среднюю длину, поэтому его используют форматы DEFLATE (ZIP, PNG), JPEG и MP3.

Префиксные коды

Префиксный код декодируется однозначно и без разделителей: читаем биты слева направо, пока прочитанное не совпадёт с каким-то кодовым словом, — это слово единственное. Код {0, 01, 11} не префиксный: «0» — начало «01», и строку «011» нельзя прочитать, не заглянув вперёд.

Префиксный код удобно изображать двоичным деревом: из каждого узла выходят рёбра «0» (влево) и «1» (вправо), символы стоят в листьях, а кодовое слово — путь от корня до листа. Префиксность означает ровно то, что символы находятся только в листьях.

Идея доказательства. Достроим дерево до полного глубины l_max. Слово длины l_i «занимает» все 2^(l_max − l_i) листьев своего поддерева, и у разных слов эти множества не пересекаются. Значит, Σ 2^(l_max − l_i) ≤ 2^(l_max). Обратно, если неравенство выполнено, раздаём слова в порядке возрастания длины, каждый раз занимая самое левое свободное поддерево.

Средняя длина и энтропия

Если символ a_i встречается с вероятностью p_i и кодируется словом длины l_i, средняя длина кода

Нижняя граница верна для любого префиксного кода (следует из неравенства Крафта). Верхняя: длины l_i = ⌈−log₂ p_i⌉ удовлетворяют неравенству Крафта и дают L < H + 1, а код Хаффмана не хуже любого префиксного кода.

Алгоритм

1. Для каждого символа создаём лист с весом, равным его частоте.
2. Пока узлов больше одного: берём два узла с наименьшими весами и объединяем их в новый узел, вес которого — сумма весов. Одному потомку приписываем ребро «0», другому — «1».
3. Оставшийся узел — корень. Код символа — последовательность меток на пути от корня до его листа.

Удобная структура данных — очередь с приоритетами (куча): N − 1 объединение, каждое за O(log N), итого O(N log N).

Пример: «абракадабра»

При равных весах объединять можно разные пары, поэтому код Хаффмана не единственный: меняются кодовые слова, но средняя длина у всех вариантов одинакова и минимальна.

Почему код оптимален

Доказательство (индукция по числу символов N; пусть p_1 ≥ … ≥ p_N).

1. В оптимальном коде более вероятный символ не длиннее менее вероятного: иначе обмен их слов уменьшит L.
2. В дереве оптимального кода каждый внутренний узел имеет двух потомков (иначе узел можно «схлопнуть» и укоротить слова). Поэтому на самой глубокой позиции есть два листа-брата, и в них можно поместить два самых редких символа a_(N−1), a_N.
3. Склеим эти два листа в один символ с вероятностью p_(N−1) + p_N. Для любого кода, где они братья, L = L' + p_(N−1) + p_N, где L' — средняя длина кода для N − 1 символов. Добавка не зависит от кода, поэтому минимизировать L — то же, что минимизировать L', а это по предположению индукции делает код Хаффмана.

Практические замечания

• Таблицу кодов нужно передать вместе с сообщением (или договориться о ней заранее) — для коротких сообщений это съедает весь выигрыш. В лаборатории можно взять частоты из самого сообщения или из файла со статистикой русского текста («Война и мир»).
• Код Хаффмана тратит целое число бит на символ, поэтому при очень неравномерных вероятностях (например, p = 0,99) он заметно хуже энтропии. Арифметическое кодирование обходит это ограничение.
• Одна ошибка в канале сбивает синхронизацию декодера: префиксные коды не защищают от помех, для этого нужны помехоустойчивые коды.

Вопросы для самопроверки

1. Является ли код {0, 10, 110, 111} префиксным? Выполняется ли для него неравенство Крафта с равенством?
   Ответ

   Да; 1/2 + 1/4 + 1/8 + 1/8 = 1 — дерево полное.
2. Постройте код Хаффмана для частот A — 4, B — 2, C — 1, D — 1 и найдите среднюю длину.
   Ответ

   Длины 1, 2, 3, 3; L = (4 + 4 + 3 + 3)/8 = 1,75 бита — совпадает с энтропией, так как все вероятности — степени 1/2.
3. Когда средняя длина кода Хаффмана в точности равна энтропии?
   Ответ

   Когда все вероятности имеют вид 2^(−k).