Код Хаффмана

Как по частотам символов построить префиксный код с минимально возможной средней длиной — оптимальный код Хаффмана.

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

В прошлом уроке мы выяснили: частым символам выгодно давать короткие коды. Но как выбрать длины оптимально? Назначать «на глаз» рискованно — получится префиксный, но не самый короткий код. Дэвид Хаффман в 1952 году придумал алгоритм, который строит гарантированно оптимальный префиксный код. Никакой другой посимвольный префиксный код не даст меньшую среднюю длину.

Это основа реальных форматов: коды Хаффмана входят в JPEG, PNG (через deflate), ZIP, gzip, MP3. Понимать их устройство полезно и для экзамена, и для общей грамотности.

Что мы оптимизируем

Пусть символ $i$ встречается с вероятностью (частотой) $p_i$ и получает код длиной $l_i$ бит. Средняя длина кода — это сколько бит в среднем тратится на один символ:

$$ L = \sum_{i} p_i \, l_i $$

Чем меньше $L$, тем компактнее сжатый текст. Цель Хаффмана — минимизировать $L$. Снизу её ограничивает энтропия Шеннона $H = -\sum p_i \log_2 p_i$ (минимальное среднее число бит в принципе). Хаффман подбирается к этой границе вплотную: всегда $H \le L \lt H + 1$.

Жадный алгоритм слияния

Алгоритм работает с деревом, которое растёт снизу вверх:

1. Каждый символ — отдельный узел с весом, равным его частоте.
2. Выбираем два узла с наименьшими весами и сливаем их в новый узел. Его вес — сумма весов детей. Левому ребру приписываем 0, правому — 1.
3. Новый узел возвращаем в общую кучу узлов вместо двух слитых.
4. Повторяем шаги 2–3, пока не останется один узел — корень дерева.
5. Код символа — последовательность битов на пути от корня к его листу.

Логика «жадности»: самые редкие символы должны оказаться глубже всех (длинные коды), поэтому их сливаем первыми — они уходят в глубину дерева. Частые символы вливаются последними и остаются ближе к корню (короткие коды).

Пошаговый пример

Закодируем слово, где частоты такие: А — 5, Б — 2, В — 1, Г — 1 (всего 9 символов).

Получилось дерево:

          (9)
         0/  \1
        А    (4)
            0/  \1
            Б   (2)
               0/  \1
               В    Г

Считываем коды по путям от корня: А=0, Б=10, В=110, Г=111. Средняя длина (частоты делим на 9):

$$ L = \frac{5}{9}\cdot 1 + \frac{2}{9}\cdot 2 + \frac{1}{9}\cdot 3 + \frac{1}{9}\cdot 3 = \frac{5 + 4 + 3 + 3}{9} = \frac{15}{9} \approx 1{,}67 \text{ бита} $$

Равномерный код потребовал бы 2 бита на символ. Хаффман даёт ~1,67 — экономия около 17%. Всё сообщение из 9 символов займёт 15 бит вместо 18.

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

Почему жадность даёт именно оптимум? Ключевая идея: в оптимальном префиксном коде два самых редких символа обязаны быть самыми длинными и при этом братьями (сидеть на одной глубине под общим родителем). Интуиция: если бы редкий символ имел код короче частого, обмен их кодами уменьшил бы $L$ — значит исходный код не был оптимальным. А раз два самых редких символа всегда сливаются в пару, можно заменить их одним «суперсимволом» с суммарной частотой и решать задачу меньшего размера — ровно это и делает алгоритм на каждом шаге.

Реализуем построение кодов на Python. Для выбора двух минимумов удобна куча (heapq) из стандартной библиотеки.

import heapq
from collections import Counter

def huffman_codes(freq):
    # freq: {символ: частота}. Куча из узлов (вес, id, поддерево).
    heap = [[w, i, [sym, ""]] for i, (sym, w) in enumerate(freq.items())]
    heapq.heapify(heap)
    counter = len(heap)
    while len(heap) > 1:
        lo = heapq.heappop(heap)   # наименьший вес
        hi = heapq.heappop(heap)   # следующий
        for pair in lo[2:]:
            pair[1] = "0" + pair[1]   # левая ветка = 0
        for pair in hi[2:]:
            pair[1] = "1" + pair[1]   # правая ветка = 1
        heapq.heappush(heap, [lo[0] + hi[0], counter] + lo[2:] + hi[2:])
        counter += 1
    return {sym: code for sym, code in sorted(heap[0][2:])}

freq = {"А": 5, "Б": 2, "В": 1, "Г": 1}
codes = huffman_codes(freq)
for sym, code in codes.items():
    print(sym, "=", code)

total = sum(freq.values())
L = sum(freq[s] * len(codes[s]) for s in freq) / total
print("Средняя длина:", round(L, 3), "бита/символ")

Вывод:

А = 1
Б = 00
В = 010
Г = 011
Средняя длина: 1.667 бита/символ

Биты вышли другими, чем у дерева, которое мы рисовали вручную (там было А=0, Б=10, …): порядок слияния узлов с равными весами в куче иной. Но длины кодов те же (1, 2, 3, 3), и средняя длина совпала с расчётом $15/9 \approx 1{,}667$. Это нормально — про неоднозначность сейчас.

Неоднозначность и канонические коды

При равных весах выбор «какие именно два узла слить» может отличаться, поэтому конкретные коды бывают разными у разных реализаций. Но средняя длина $L$ всегда одна и та же — она оптимальна. На практике, чтобы декодеру не пересылать само дерево, используют канонические коды Хаффмана: фиксируют только длины кодов, а сами биты восстанавливают по соглашению.

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

• Сливают частые символы вместо редких. На каждом шаге берём ровно два наименьших веса, иначе оптимум не получится.
• Забывают про сам код дерева. Чтобы декодировать, получателю нужны коды (или частоты/длины). В оценке размера это иногда учитывают.
• Считают, что код единственный. При равных частотах деревья и коды могут различаться, но средняя длина одинакова.
• Путают сумму $\sum p_i l_i$ с $\sum l_i$. Средняя длина — взвешенная по частотам, а не простое среднее длин кодов.

Итоги

• Код Хаффмана — оптимальный посимвольный префиксный код: минимальная средняя длина $L = \sum p_i l_i$.
• Алгоритм жадный: на каждом шаге сливаем два узла с наименьшими весами, строя дерево снизу вверх.
• Редкие символы уходят глубоко (длинные коды), частые остаются у корня (короткие).
• Граница снизу — энтропия: $H \le L \lt H + 1$.
• Коды могут различаться при равных частотах, но средняя длина всегда оптимальна.
• Хаффман лежит в основе ZIP, gzip, JPEG, PNG, MP3.