Код Хаффмана: как студент случайно изобрёл идеальное сжатие

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

Дэвид Хаффман не знал, что задача считается нерешённой. Если бы знал — возможно, не стал бы и пытаться.

Проблема: буквы встречаются по-разному часто

В обычном тексте каждый символ кодируется одинаковым числом бит. Но буква «о» встречается в русском в сотни раз чаще, чем «ъ». Тратить на редкую «ъ» столько же бит, сколько на частую «о», — расточительство. Идея переменной длины кода стара (азбука Морзе уже так устроена: частое «E» — одна точка, редкое «Q» — длинная последовательность). Вопрос был в другом: как построить гарантированно лучший такой код?

Загвоздка: коды не должны путаться

Если «о» = 0, а «а» = 01, то получив поток 001, декодер не поймёт: это «оа» или «оо…»? Нужно префиксное свойство: ни один код не должен быть началом другого. Тогда поток битов читается однозначно, без разделителей. Префиксные коды удобно рисовать как дерево: спуск налево — бит 0, направо — бит 1, а символы висят только на листьях. Раз символ только в листе, его код никогда не окажется префиксом чужого.

Жадная идея Хаффмана

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

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

Самые редкие символы сливаются первыми, значит, оказываются глубже всех — и получают самые длинные коды. Частые всплывают наверх и получают короткие. Это жадный алгоритм: на каждом шаге делаем локально лучший выбор и доказуемо приходим к глобальному оптимуму — что для жадных стратегий редкость.

import heapq
from collections import Counter

def huffman_codes(text):
    freq = Counter(text)
    # куча: (вес, уникальный_id, узел); узел = символ или [левый, правый]
    heap = [(w, i, ch) for i, (ch, w) in enumerate(freq.items())]
    heapq.heapify(heap)
    counter = len(heap)
    while len(heap) > 1:
        w1, _, n1 = heapq.heappop(heap)   # два самых лёгких
        w2, _, n2 = heapq.heappop(heap)
        heapq.heappush(heap, (w1 + w2, counter, [n1, n2]))
        counter += 1
    codes = {}
    def walk(node, prefix=""):
        if isinstance(node, str):
            codes[node] = prefix or "0"
        else:
            walk(node[0], prefix + "0")   # налево — 0
            walk(node[1], prefix + "1")   # направо — 1
    walk(heap[0][2])
    return codes

text = "абракадабра"
codes = huffman_codes(text)
for ch in sorted(codes):
    print(f"{ch!r}: {codes[ch]}")

bits = sum(len(codes[c]) for c in text)
print(f"Хаффман: {bits} бит против {len(text) * 8} бит при 8 бит/символ")

Насколько это хорошо

Запустите код: слово «абракадабра» (11 символов, обычно 88 бит) ужмётся до двух с небольшим десятков бит. Чем сильнее перекос частот, тем больше выигрыш. Теоретический предел задаёт энтропия Шеннона — минимальное среднее число бит на символ:

$$H = -\sum_{i} p_i \log_2 p_i$$

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

Где он живёт прямо сейчас

Код Хаффмана — не музейный экспонат. Он внутри формата DEFLATE (а значит, в ZIP, gzip и каждой веб-странице, что приходит к вам сжатой), в финальной стадии JPEG и в MP3. Каждый раз, открывая архив или картинку, вы запускаете алгоритм, который родился из нежелания студента сдавать экзамен.

Мораль

История Хаффмана — про пользу незнания границ. Профессор Роберт Фано (сам соавтор близкого, но неоптимального метода Шеннона — Фано) годами искал доказуемо лучший код. Студент, не отягощённый знанием, что «это сложно», зашёл с другой стороны — снизу вверх — и нашёл. Иногда свежий взгляд бьёт многолетний опыт именно потому, что не знает, где принято останавливаться.