Код Хаффмана: редкое длинным, частое коротким

Если ты умеешь построить дерево Хаффмана руками, посчитать цену как сумму произведений и объяснить обмен листьев, листай до «Теперь сам».

Как думаешь, сколько бит на символ

В тексте сто символов, и среди них только шесть разных: A встречается 45 раз, D - 16, B - 13, C - 12, E - 9, F - 5.

Шесть символов - значит трёх бит на символ хватает (2³ = 8), и весь текст занимает 300 бит. Вопрос: можно ли меньше, если не требовать, чтобы все коды были одной длины? И если можно - то насколько, и какой код взять?

На что это похоже

Телеграф и азбука Морзе. Самая частая буква английского языка E получила самый короткий код - одну точку, а редкие Q и Z - по четыре знака. Морзе расставил длины на слух, по толщине ящиков с литерами в типографии. Хаффман в 1952 году сделал то же самое, но доказуемо оптимально - и, в отличие от Морзе, без разделителей между буквами: префиксное свойство само отмечает, где слово кончилось.

Механизм: префиксный код, цена и алгоритм

ПОЧЕМУ КОД ОБЯЗАН БЫТЬ ПРЕФИКСНЫМ

пусть A = 0, B = 01, C = 1. Код B начинается с кода A - это не префиксный код.
Запись 001 разбирается ДВУМЯ способами:
    0 | 01    = A, B
    0 | 0 | 1 = A, A, C
и выбрать между ними нельзя - информации для этого нет

если ни одно слово не начало другого, разбор однозначен и идёт слева направо
без всяких разделителей: читаем биты, пока не совпали с каким-то словом

Оговорка на будущее: не всякий непрефиксный код неоднозначен. Убери из примера C - и код {A = 0, B = 01} станет разбираться однозначно, хотя префиксным не будет; просто разбирать его придётся не за один проход слева направо. Префиксность - удобное ДОСТАТОЧНОЕ условие: она даёт мгновенный разбор, и платить за неё нечем - среди префиксных кодов есть оптимальный по длине.

КОД = ДВОИЧНОЕ ДЕРЕВО

символы - в ЛИСТЬЯХ; путь от корня - это слово кода (влево 0, вправо 1)
листья не имеют потомков ⇒ ни одно слово не префикс другого (это и есть префиксность)

ЦЕНА = Σ f_i · d_i      f_i - частота символа, d_i - глубина его листа
                        это ровно число бит во всём закодированном тексте

АЛГОРИТМ ХАФФМАНА

положить все символы в очередь с приоритетом по частоте
пока в очереди больше одного узла:
    достать ДВА САМЫХ РЕДКИХ узла x, y
    создать узел z с частотой f(x) + f(y), детьми x и y
    положить z обратно в очередь
последний оставшийся узел - корень

цена: n−1 слияний, каждое два извлечения и одна вставка → Θ(n·log n)

ПОЧЕМУ ЭТО ВЕРНО - ДВА ШАГА

1. два самых редких символа можно сделать БРАТЬЯМИ на максимальной глубине
   (обмен листьев - разбор ниже)
2. после слияния остаётся та же задача с n−1 символом,
   где новый символ имеет частоту f(x) + f(y)

Правило

Префиксный код - код, в котором ни одно слово не является началом другого. Он позволяет декодировать слева направо без ожидания следующих битов после конца слова и равносилен двоичному дереву с символами в листьях. Однозначность без разделителей сама по себе ещё не требует префиксности, как показал пример {0,01} выше. Цена кода равна Σ f_i · d_i - сумме произведений частоты на глубину. Алгоритм Хаффмана строит оптимальный префиксный код снизу вверх: n−1 раз взять два самых редких узла и заменить их одним с суммарной частотой. Цена - Θ(n·log n) на очереди с приоритетом. Доказательство безопасности шага - обмен листьев: любой оптимальный код можно перестроить так, чтобы два самых редких символа стали братьями на самой большой глубине, не увеличив цену. Не единственны ни сами коды (ветви можно менять местами), ни даже НАБОР ДЛИН: на частотах 1, 1, 1, 1, 2 два законных прогона Хаффмана дают профили глубин (1, 3, 3, 3, 3) и (2, 2, 2, 3, 3), и у обоих цена 14. Единственна только ЦЕНА.

Разбор: строим дерево на шести символах

Частоты из начала урока: A:45, D:16, B:13, C:12, E:9, F:5.

шаг 1: самые редкие - F(5) и E(9)         → узел FE(14)
       очередь: A45, D16, B13, C12, FE14

шаг 2: самые редкие - C(12) и B(13)       → узел CB(25)
       очередь: A45, D16, FE14, CB25

шаг 3: самые редкие - FE(14) и D(16)      → узел FED(30)
       очередь: A45, CB25, FED30

шаг 4: самые редкие - CB(25) и FED(30)    → узел CBFED(55)
       очередь: A45, CBFED55

шаг 5: A(45) и CBFED(55)                  → корень(100)

Получились такие глубины: A - 1, B, C, D - 3, E, F - 4. Считаем цену:

A: 45 · 1 = 45
B: 13 · 3 = 39
C: 12 · 3 = 36
D: 16 · 3 = 48
E:  9 · 4 = 36
F:  5 · 4 = 20
                 итого 224 бита

Против 300 бит у трёхбитного кода - экономия 25%. И посмотри, что сделала жадность: самый частый символ получил ОДИН бит, а два самых редких - по четыре. Средняя длина - 2.24 бита на символ.

для сравнения: теоретический предел - ЭНТРОПИЯ частот
    H = − Σ p_i · log₂ p_i,   где p_i = f_i / (сумма всех частот)
здесь p = 0.45, 0.16, 0.13, 0.12, 0.09, 0.05  и  H = 2.22 бита на символ

Хаффман даёт 2.24 - он не хуже энтропии больше чем на 1 бит на символ, и обычно
разрыв куда меньше

Энтропия - мера «неожиданности» источника: чем ровнее частоты, тем она больше (при шести РАВНЫХ частотах вышло бы log₂ 6 = 2.585), чем сильнее перекос - тем меньше. Короче энтропии в среднем не бывает ни один код, это теорема Шеннона. Хаффман подходит к ней вплотную и проигрывает лишь потому, что длины кодов целые, а −log₂ p обычно нет.

Один шаг стоит разобрать отдельно - третий. Посмотри, что лежит в очереди перед ним: FE(14), D(16), CB(25), A(45) - из шести исходных символов отдельно остались два, D и A, остальные уже спрятаны внутри двух созданных узлов. Два самых редких здесь - узел FE(14) и символ D(16), то есть созданный узел участвует наравне с исходным символом и даже оказывается РЕДЬШЕ его.

очередь перед каждым шагом:
шаг 1:  F5, E9, C12, B13, D16, A45        → сливаем F + E
шаг 2:  C12, B13, FE14, D16, A45          → сливаем C + B
шаг 3:  FE14, D16, CB25, A45              → сливаем FE + D   ← созданный узел с символом
шаг 4:  CB25, FED30, A45                  → сливаем CB + FED
шаг 5:  A45, CBFED55                      → корень

Именно так жадность «забывает», откуда взялся узел: дальше он участвует как обычный элемент со своей частотой. Если реализовать очередь неправильно - например, сравнивать только исходные символы, - алгоритм молча даст неоптимальный код.

Разбор: обмен листьев, почему два самых редких - братья

Утверждение. Пусть x, y - два символа с НАИМЕНЬШИМИ частотами.
Тогда существует оптимальный префиксный код, в котором x и y -
братья и лежат на максимальной глубине.

Доказательство (обмен листьев).
    Пусть T - оптимальное дерево. Возьмём в нём пару братьев a, b
    на МАКСИМАЛЬНОЙ глубине (такая пара есть: самый глубокий лист
    обязан иметь брата, иначе его можно поднять и улучшить код).

    Поменяем местами x и a. Что стало с ценой:
        цена меняется на (f_a − f_x)·(d_x − d_a)
        f_x <= f_a  (x - из двух самых редких)
        d_x <= d_a  (a на максимальной глубине)
    значит произведение <= 0: цена НЕ ВЫРОСЛА.

    Так же поменяем y и b. Снова цена не выросла.
    Дерево осталось префиксным кодом (мы переставили листья),
    цена не выросла, а T было оптимальным ⇒ новое дерево тоже оптимально,
    и в нём x, y - братья на максимальной глубине.                     ∎

Проверь знак руками: если f_x < f_a, а d_x < d_a, то мы переносим РЕДКИЙ символ глубоко, а ЧАСТЫЙ - наверх; это ровно то, что уменьшает Σ f·d. Поэтому в неравенстве стоит «не выросла», а в строгом случае цена даже падает - но для доказательства достаточно нестрогого.

Вторая половина - оптимальность подзадачи: после слияния x и y в узел z с частотой f_x + f_y цена дерева связана с ценой меньшего дерева простым соотношением:

цена(T) = цена(T') + f_x + f_y

где T' - дерево на n−1 символе (вместо x, y стоит z). Прибавка f_x + f_y одна и та же для ЛЮБОГО дерева, поэтому минимум одного соответствует минимуму другого - значит оптимальное решение подзадачи даёт оптимальное решение целой. Это и замыкает индукцию.

Что ломается без этого

Первое: считать однозначность и префиксность одним свойством. Непрефиксный код может быть однозначным, но простой декодер по дереву до первого листа к нему не подходит. У неоднозначного кода разные последовательности символов вообще могут давать одну битовую строку. Второе: вытаскивать из очереди по одному разу вместо двух или забыть положить новый узел обратно - дерево получится, но неоптимальное. Третье: сравнивать в очереди только исходные символы, не учитывая созданные узлы: именно на этом шаге алгоритм обычно и ломают. Четвёртое: считать, что код Хаффмана единственный: при равных частотах и при выборе, какую ветвь назвать нулём, кодов много, а ЦЕНА у всех оптимальных одна. Пятое: думать, что Хаффман достигает энтропии: он не хуже её плюс один бит на символ, и на сильно неравномерных частотах (один символ с вероятностью 0.99) разрыв заметен - там применяют арифметическое кодирование. Шестое: применять Хаффмана к данным с зависимостями между символами (текст, где после q почти всегда u): он учитывает только частоты поодиночке, а остальное - работа моделей и преобразований вроде LZ.

Зачем это в работе

Хаффман стоит внутри форматов, которыми ты пользуешься каждый день: DEFLATE (а значит gzip, zip, PNG) кодирует Хаффманом выход LZ77Разбирается в разделе 17, глава «Сжатие - RLE, Хаффман, LZ77, арифметическое»: LZ77: ссылка назад вместо повтора, в JPEG им кодируются коэффициенты после квантования, в MP3 - спектральные значения. В HTTP/2 заголовки сжимаются HPACK - это код Хаффмана с заранее зафиксированной таблицей частот, построенной по статистике реальных заголовков; фиксированная таблица тут не компромисс, а решение: она экономит передачу самой таблицы. И это общий практический сюжет: канонический код Хаффмана передают не деревом, а ДЛИНАМИ кодов - по длинам, которые ВЫБРАЛ кодировщик, декодер восстанавливает дерево однозначно, - иначе накладные расходы на описание кода съедят выигрыш на коротких данных.

Теперь сам

Частоты: a:1, b:1, c:2, d:3, e:5. Построй код Хаффмана и посчитай его цену.

шаг 1: a(1) + b(1)       → ab(2)      очередь: c2, ab2, d3, e5
шаг 2: c(2) + ab(2)      → cab(4)     очередь: d3, cab4, e5
шаг 3: d(3) + cab(4)     → dcab(7)    очередь: e5, dcab7
шаг 4: e(5) + dcab(7)    → корень(12)

глубины:  e - 1,  d - 2,  c - 3,  a - 4,  b - 4

цена = 5·1 + 3·2 + 2·3 + 1·4 + 1·4 = 5 + 6 + 6 + 4 + 4 = 25 бит

e = 0      d = 10      c = 110      a = 1110      b = 1111

префиксность: ни одно слово не начинается с другого        ✓
цена:  5·1 + 3·2 + 2·3 + 1·4 + 1·4 = 25                    ✓
слово «decade» (d,e,c,a,d,e) → 10 0 110 1110 10 0 - 13 бит