Алгоритм Хаффмана

Сформулируем задачу строго, иначе непонятно, что считать решением.

Дано: алфавит из N символов и частота каждого из них – сколько раз символ встречается в тексте (или какую долю он занимает).
Требуется: назначить каждому символу кодовое слово из нулей и единиц так, чтобы код был префиксным, а средняя длина L – минимальной.

Два уточнения, чтобы не было иллюзий.

Первое: частоты берутся из конкретного текста, который мы собираемся кодировать. Не «вообще из русского языка» – именно отсюда. Поэтому код, построенный для одного текста, для другого будет уже не оптимальным (а иногда и хуже равномерного – про это в уроке 7.4).

Второе: префиксность входит в условие не как каприз. Без неё задача вырождается – можно раздать всем символам код 0 и получить $L = 1$, только прочитать это обратно нельзя.

Хаффман стал строить дерево снизу вверх – не от корня к листьям, а от листьев к корню. Опирался он на два наблюдения, каждое из которых можно проверить самому.

Наблюдение первое: самый редкий символ обязан оказаться в самом глубоком листе. Если бы редкий символ сидел выше частого, их можно было бы поменять местами – и суммарная длина записи уменьшилась бы. Значит, исходный код не был лучшим.

Наблюдение второе: в самом глубоком листе символ не один. У его развилки есть второй потомок, и он не может быть пустым: пустая ветка означает, что кто-то зря тратит бит. Значит, два самых редких символа висят на одной развилке – они братья.

А раз мы уже точно знаем, что эти двое – братья, их можно склеить и дальше не различать. Заменим пару символов одним «сдвоенным» узлом с суммарной частотой. Алфавит стал короче на один символ, а задача осталась ровно той же – только меньше. Повторяем, пока не останется один узел: это корень.

Вот и весь метод. Ни перебора, ни возвратов – на каждом шаге мы делаем ход, про который уже доказано, что он не ошибочный.

1. Выписать все символы как отдельные узлы с их частотами.
2. Выбрать два узла с наименьшими частотами.
3. Объединить их в новый узел: его частота – сумма частот, а выбранные узлы становятся его потомками (левым и правым).
4. Вернуть новый узел в общий список, а два исходных из списка убрать.
5. Повторять шаги 2–4, пока не останется один узел. Это корень дерева.
6. Разметить рёбра: шаг влево – 0, шаг вправо – 1. Код символа – путь от корня до его листа.

Обратите внимание: за один шаг число узлов уменьшается на единицу, значит, для $N$ символов шагов будет ровно $N - 1$. Алгоритм не может зациклиться, и заранее известно, сколько он проработает.

И ещё одно, ради чего всё затевалось: условие Фано проверять не нужно. Символы попадают в дерево только как листья и внутренними узлами стать не могут – внутренние узлы алгоритм создаёт сам, и символов в них нет.

Возьмём слово АБРАКАДАБРА – 11 символов, 5 разных букв. Считаем частоты:

Равномерным кодом тут не обойтись меньше чем тремя битами на символ: букв 5, а $2^2 = 4 < 5 \le 8 = 2^3$ (формула из урока 7.1). Итого $11 \times 3 = 33$ бита. Это то, что нужно побить.

Теперь по шагам. Список узлов: К:1, Д:1, Б:2, Р:2, А:5.

Шаг 1. Два самых лёгких – К (1) и Д (1). Склеиваем: новый узел [КД] весом 2.

Список: Б:2, Р:2, [КД]:2, А:5.

Шаг 2. Три узла весом 2 – берём Б и Р (про то, кого брать при равенстве, ниже отдельный разговор). Новый узел [БР] весом 4.

Список: [КД]:2, [БР]:4, А:5.

Шаг 3. Самые лёгкие – [КД] (2) и [БР] (4). Новый узел [КДБР] весом 6.

Список: А:5, [КДБР]:6.

Шаг 4. Остались двое, склеиваем: корень весом 11 – как раз длина слова, и это удобная проверка на арифметическую ошибку.

Дерево готово, шагов было ровно $4 = 5 - 1$.

Спускаемся от корня к каждому листу и записываем маршрут:

Ровно та картина, ради которой всё делалось: самая частая буква получила один бит, самые редкие – по три.

Слово АБРАКАДАБРА в этом коде выглядит так:

 А  Б   Р  А  К  А  Д  А  Б   Р  А
 0 110 111 0 100 0 101 0 110 111 0

Одной лентой: 01101110100010101101110 – 23 бита.

Складываем биты по таблице:

А:  5 × 1 =  5
Б:  2 × 3 =  6
Р:  2 × 3 =  6
К:  1 × 3 =  3
Д:  1 × 3 =  3
           ──
           23 бита вместо 33

Средняя длина кодового слова: $L = 23 / 11 \approx 2{,}09$ бита на символ против ровно 3 у равномерного кода.

Сэкономлено 10 битов из 33 – почти треть записи, и это на слове из одиннадцати букв. Причём Хаффман не просто «сжал»: доказано, что лучшего посимвольного префиксного кода для этих частот не существует. 23 бита – не «неплохой результат», а точный минимум.

Здесь $b$ – сколько битов тратил на символ равномерный код (урок 7.1), $L$ – средняя длина кодового слова у нашего кода (урок 7.4). Отношение показывает, во сколько раз запись стала короче: $k = 3 / 2{,}09 \approx 1{,}43$, то есть файл ужался примерно в полтора раза.

Тот же результат получится, если поделить объёмы целиком: $33 / 23 \approx 1{,}43$. А ту же величину часто называют иначе – «экономия 30%»: это $(33 - 23) / 33$. Числа описывают одно и то же, важно только не перепутать, что именно у вас в числителе.

На шаге 2 мы выбирали из трёх узлов веса 2 и взяли Б и Р. А если бы взяли [КД] и Б?

Тогда получилось бы другое дерево и другая таблица: А = 0, Б = 111, Р = 10, К = 1100, Д = 1101. Коды непохожи, у К и Д теперь по 4 бита вместо трёх. Считаем:

5×1 + 2×3 + 2×2 + 1×4 + 1×4 = 23 бита

Ровно столько же. И это не совпадение: алгоритм гарантирует минимальную суммарную длину, но не единственность дерева.

Проверьте это в виджете, не отходя от кассы. Сделайте первый шаг кнопкой «Шаг за меня», а на втором выберите вручную [КД] и Б вместо Б и Р. Виджет не возразит – и правильно сделает: узлы весом 2 равноправны, никакого нарушения правила тут нет. Коды получатся другие, а внизу по-прежнему будет 23 бита и бейдж «минимум достигнут».

Отсюда два следствия, которые стоит запомнить.

• Не пугайтесь, если ваша таблица не совпала с ответом в разборе – сравнивать надо не коды, а число битов.
• Кто и в каком порядке разрешает ничьи и что считать «левым» потомком – это соглашение. Значит, декодировать чужую запись, зная только частоты, нельзя: вместе с данными нужно передать саму таблицу кодов.

23 бита против 33 – красиво, но мы кое о чём умолчали. Получателю нужна таблица кодов, иначе лента для него – бессмысленный набор битов. А таблица тоже занимает место, и для слова из одиннадцати букв она окажется тяжелее самих данных.

Отсюда три следствия, которые объясняют, как это выглядит на практике.

• На коротких данных сжатие бессмысленно. Выигрыш растёт с длиной текста, а накладные расходы на таблицу постоянны. Именно поэтому крошечный файл в архиве иногда становится больше оригинала.
• Таблицу хранят экономно. Передавать дерево целиком не нужно: достаточно длин кодов каждого символа – по ним обе стороны соберут одинаковую таблицу, если заранее договорятся о правиле раздачи кодов. Такой приём называется каноническим кодом Хаффмана, им пользуются JPEG и ZIP, и как именно он работает – разбираем в следующем блоке.
• Иногда таблицу не передают вовсе. Её фиксируют в стандарте раз и навсегда – тогда она уже зашита в программу-декодер, и платить за неё в каждом файле не приходится.

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

Само правило – четыре пункта.

1. Символы выстраиваются по возрастанию длины кода, а внутри одной длины – по алфавиту. Годится любой заранее оговорённый порядок, важно лишь, чтобы он был один и тот же у обеих сторон.
2. Первому символу достаётся код из одних нулей – столько нулей, какова его длина.
3. Каждый следующий код – это предыдущий, увеличенный на единицу как двоичное число.
4. Если при переходе к очередному символу длина выросла на $k$ битов, к получившемуся числу дописывается $k$ нулей справа.

Ни дерева, ни частот, ни правила разрешения ничьих при этом не нужно – только список длин. Вот что получается для нашего слова:

Проследим по строкам. А – единственная с длиной 1, ей достаётся 0. Дальше длина прыгает до трёх: прибавляем единицу (0 + 1 = 1) и дописываем два нуля – выходит 100, это Б. Остальные получаются простым прибавлением единицы: 101, 110, 111.

Запись не стала длиннее. Длины остались теми же, что у кода с дерева, а объём ленты зависит только от них – всё те же 23 бита. Кодовые слова другие, но из предыдущего блока мы уже знаем, что это нормально.

Условие Фано не ломается. Возьмём короткий код $c$ длины $m$ и любой более длинный код $d$. Первые $m$ битов $d$ – это то самое число, в которое превратился $c$ после прибавления единицы (а может, и нескольких), то есть строго больше $c$. Значит, $c$ не совпадает с началом $d$ и префиксом его быть не может.

Что в итоге едет в файле. Вместо дерева – список длин по фиксированному порядку символов: 1, 3, 3, 3, 3. На практике длина кода не превышает полутора-двух десятков битов, поэтому одну длину можно записать четырьмя-пятью битами вместо целой ветки дерева. Ровно так устроены таблицы Хаффмана в JPEG и в DEFLATE (ZIP, gzip, PNG).

Хаффман – не музейный экспонат, его код прямо сейчас исполняется на любом устройстве, где открывают картинки.

• ZIP, gzip, PNG – все они используют алгоритм DEFLATE, а он состоит из двух этапов: сначала повторяющиеся куски заменяются ссылками на предыдущие вхождения, потом то, что получилось, кодируется по Хаффману.
• JPEG – коэффициенты сжатого изображения на последнем этапе тоже кодируются по Хаффману. Так что кнопка «сохранить как JPEG» запускает и этот алгоритм.
• MP3 – в стандарте зафиксирован набор готовых таблиц Хаффмана; кодировщик выбирает подходящую и пишет в файл только её номер.

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

Честно про границы – иначе останется ощущение, что задача сжатия закрыта в 1951 году.

Целое число битов на символ. Код не может быть короче одного бита. Если один символ занимает 99% текста, по-хорошему ему хватило бы сотых долей бита – но Хаффман обязан выдать целый, и текст из миллиона символов не ужмётся меньше миллиона битов. От этого ограничения свободно арифметическое кодирование: оно кодирует сообщение целиком одним длинным числом и умеет тратить дробное число битов на символ.

Частоты нужно знать заранее. Значит, файл придётся прочитать дважды: сначала посчитать статистику, потом кодировать. Существуют адаптивные варианты, достраивающие дерево по ходу чтения, но они сложнее.

Символы считаются независимыми. Алгоритм видит частоту буквы «ь», но не замечает, что после «ь» почти никогда не идёт «ы». Вся эта информация о связях остаётся неиспользованной – её вылавливают другие алгоритмы, до Хаффмана.

И всё же формулировка «оптимален» остаётся верной – просто с уточнением, которое стоит держать в голове: он оптимален среди посимвольных префиксных кодов. В своём классе его не побить, а к теоретическому минимуму Шеннона (о нём была речь в конце урока 7.1) он подбирается вплотную: для нашего слова этот минимум – около 2,04 бита на символ, а Хаффман дал 2,09.