Как Хаффман строит оптимальный код
Хаммин представляет кодирование Хаффмана как жадный алгоритм, который строит префиксный код с минимальной средней длиной. Ключевая идея: строить дерево снизу вверх, всегда объединяя два символа с наименьшей вероятностью.
Прямой проход (построение)
1. Отсортируйте все символы по вероятности, от высшей к низшей.
2. Возьмите два символа с наименьшей вероятностью. Объедините их в новый мета-символ с вероятностью = сумма двух.
3. Вставьте мета-символ в его отсортированную позицию.
4. Повторяйте, пока не останется два символа.
5. Присвойте 0 и 1 двум оставшимся символам.
Обратный проход (назначение кодов)
Отмените слияния в обратном порядке: при каждом разделении два объединённых символа получают те же префиксные биты, что и их объединённый родитель, плюс дополнительный 0 (один дочерний) или 1 (другой дочерний). Присвоение 0/1 произвольно — любое из них верно.
Почему это оптимально: если бы какой-то другой код имел меньшую среднюю длину L', применение того же прямого сокращения в конечном итоге привело бы к двум символам со средней длиной менее 1 бита — невозможно для 2-символьного кода. Противоречие.
Трассировка алгоритма
Пример из Хаммина: четыре символа A, B, C, D с p(A)=0.5, p(B)=0.25, p(C)=0.125, p(D)=0.125.
Прямой проход:
Шаг 1: Отсортировано: A(0.5), B(0.25), C(0.125), D(0.125). Два наименьших: C, D.
Шаг 2: Объедините CD с p=0.25. Новый список: A(0.5), B(0.25), CD(0.25).
Шаг 3: Два наименьших: B(0.25), CD(0.25). Объедините BCD с p=0.5.
Шаг 4: Остаются два символа: A(0.5), BCD(0.5). Присвойте A=0, BCD=1.
Обратный проход:
BCD → B получает 10, CD получает 11. CD → C получает 110, D получает 111.
Финальный код: A=0 (l=1), B=10 (l=2), C=110 (l=3), D=111 (l=3).
L = 0.5·1 + 0.25·2 + 0.125·3 + 0.125·3 = 1.75 бит.
Множественные правильные коды Хаффмана
Хаммин отмечает два источника неуникальности:
1. Произвольное присвоение 0/1. При каждом разделении вы можете присвоить 0 любому дочернему узлу. Обмен 0 и 1 везде дает другой код с идентичным L.
2. Разрешение ничьей. Когда два узла имеют равную вероятность, любой может быть размещён 'выше' (объединен первым). Различные решения разрешения ничьей могут привести к структурно различным деревьям — 'длинные' vs 'кустистые' — с одинаковым L, но различными распределениями длин кодов.
Длинные vs кустистые
Длинное дерево (асимметричное): один символ на каждом уровне глубины (структура, похожая на Фибоначчи). Длины кодов сильно варьируются: один символ получает короткий код, остальные каскадом переходят к более длинным кодам.
Кустистое дерево (сбалансированное): символы равномерно распределены на уровнях глубины. Длины кодов группируются рядом со средним значением. Более низкая дисперсия.
Рекомендация Хаммина: когда есть выбор, предпочитайте кустистое дерево. Одинаковый L, но меньшая дисперсия длин кодов → более равномерное время декодирования → меньшие требования к буферу в приложениях реального времени.
Вычисление дисперсии длины кода
Дисперсия длин кодов: Var = E[l²] − (E[l])²
Для кода {A=0 l=1, B=10 l=2, C=110 l=3, D=111 l=3} с p=[0.5, 0.25, 0.125, 0.125]:
E[l] = L = 1.75
E[l²] = 0.5·1² + 0.25·2² + 0.125·3² + 0.125·3² = 0.5 + 1.0 + 1.125 + 1.125 = 3.75
Var = 3.75 − 1.75² = 3.75 − 3.0625 = 0.6875
Альтернативный кустистый код для равновероятных символов использует все коды длины 2: L=2, Var=0.
Выигрыш сжатия в зависимости от распределения символов
Правило Хаммина: кодирование Хаффмана окупается только когда вероятности символов существенно различаются.
Равные вероятности. Если все 2^k символов имеют равную вероятность 1/2^k, Хаффман производит блочный код: каждый символ получает длину k. L = H = k. Никакого выигрыша над простым блочным кодом.
Асимметричные вероятности. Если один символ доминирует (p >> 1/2^k для остальных), Хаффман присваивает ему очень короткий код (длина 1 или 2), резко снижая L.
Код с запятой (термин Хаммина). Когда каждая вероятность превышает 2/3 от оставшейся суммы, Хаффман естественно производит: p(s1)→0, p(s2)→10, p(s3)→110, ..., вплоть до двух кодов равной длины в конце. Это 'код с запятой': следующий 0 после серии 1s работает как запятая.
Хаммин отмечает: сжатие данных в реальном мире (резервная копия, архивирование файлов) может сократить хранилище более чем на половину, когда источник имеет асимметричные вероятности — английский текст является главным примером.
Хаффман vs блочный код: числовое сравнение
Второй пример Хаммина: p(s1)=1/3, p(s2)=1/5, p(s3)=1/6, p(s4)=1/10, p(s5)=1/12, p(s6)=1/20, p(s7)=1/30, p(s8)=1/30.
Блочный код: 8 символов → 3 бита каждый → L_block = 3.
Хаммин вычисляет код Хаффмана и сообщает L_Huffman ≈ 2.58 битов.
Сбережения: (3 − 2.58)/3 ≈ 14% сжатие над блочным кодированием.
Когда вероятности символов сильно различаются (1/3 vs 1/30 здесь, отношение 10:1), кодирование переменной длины окупается значительно.
Самокомпилирующиеся программы
Хаммин заканчивает главу 11 потрясающей идеей: кодер Хаффмана может кодировать себя. Дерево декодирования (которое говорит декодеру, как читать сжатое сообщение) передается вместе со сжатыми данными. Получатель не нуждается в предварительном знании кода.
Кодер: дискретизирует данные, оценивает вероятности, строит код Хаффмана, кодирует дерево декодирования как заголовок, затем кодирует данные.
Декодер: читает заголовок для восстановления дерева, затем декодирует данные с его помощью.
Точка зрения Хаммина: весь этот конвейер может работать как функция библиотеки без вмешательства человека. Вы вызываете её, она автоматически сжимает и распаковывает. Современные форматы архивирования (ZIP, gzip, bzip2) реализуют ровно этот шаблон.
Глубокий принцип: интеллект находится в алгоритме, не в фиксированной таблице кодов. Алгоритм адаптируется к любым данным, которые он получает. Это шаблон, который Хаммин видит во всех великих инженерных системах: адаптируемость встроена, не приклеена.