Урок #3. Алгоритм Хаффмана: оптимальное префиксное кодирование

Введение

Представьте, что вам нужно передать другу длинную телеграмму или сохранить на дискете текстовый файл объёмом в несколько мегабайт. Каждая буква занимает ровно один байт (8 бит). Но все ли символы встречаются в тексте одинаково часто? Очевидно, нет. Буквы «о», «е», «а» используются постоянно, а буквы «ф», «щ», «ъ» — крайне редко. Использовать для них одинаковое количество битов — значит тратить драгоценное пространство впустую.

В середине XX века Дэвид Хаффман, будучи аспирантом Массачусетского технологического института, задался вопросом: как присвоить символам коды переменной длины так, чтобы общая длина сообщения стала минимальной? При этом критически важно было соблюсти условие префиксности: ни один короткий код не должен быть началом другого кода. Если бы код буквы «А» был 01, а код буквы «Б» — 011, декодер при получении последовательности 011… не смог бы понять, встретилась ли ему буква «А» с последующим символом, начинающимся на 1, или это была одна буква «Б».

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

Где это применяется сегодня

• Форматы изображений без потерь: PNG использует цепочку фильтров и алгоритм DEFLATE, внутри которого работает Хаффман.
• Архиваторы: ZIP, GZ, ARJ.
• Мультимедиа: ранние стандарты JPEG (кодирование коэффициентов ДКП) и MP3 используют модифицированные деревья Хаффмана.
• Системы связи: групповое кодирование каналов для снижения вероятности ошибки.

Идея и механика алгоритма

Чтобы построить дерево Хаффмана, нам нужна статистика — таблица частот встречаемости каждого символа в исходном сообщении.

Идея метода (жадная стратегия). Мы будем действовать от обратного. Самые редкие символы должны получить самые длинные коды, а самые частые — самые короткие. На каждом шаге мы берём два самых редких элемента, объединяем их в один новый узел, частота которого равна сумме частот этих элементов, и возвращаем его в общую кучу. Мы повторяем это до тех пор, пока не останется один корень. Это классический пример жадного алгоритма, который на каждом локальном шаге делает оптимальный выбор (объединяет наименее вероятные элементы), что в итоге приводит к глобальному оптимуму.

Пример: фраза «ПИТОН НА ЗАДНЕЙ ПАРТЕ»

Таблица частот символов:

Начальная очередь: [ И(1), О(1), З(1), Д(1), Й(1), Р(1), П(2), Т(2), Е(2), Н(3), _(3), А(3) ]

Жадное слияние по шагам

1. Берём два минимума: И(1) и О(1). Объединяем в ИО(2).
2. Берём два минимума: З(1) и Д(1). Объединяем в ДЗ(2).
3. Берём два минимума: Й(1) и Р(1). Объединяем в ЙР(2).
4. Берём два минимума: П(2) и Т(2). Объединяем в ПТ(4).
5. Берём два минимума: Е(2) и ИО(2). Объединяем в ЕИО(4).
6. Берём два минимума: ДЗ(2) и ЙР(2). Объединяем в ДЗЙР(4).
7. Берём два минимума: Н(3) и _(3). Объединяем в Н_(6).
8. Берём два минимума: А(3) и ПТ(4). Объединяем в АПТ(7).
9. Берём два минимума: ЕИО(4) и ДЗЙР(4). Объединяем в ДЕЗИЙОР(8).
10. Берём два минимума: Н_(6) и АПТ(7). Объединяем в АНПТ(13).
11. Берём два минимума: ДЕЗИЙОР(8) и АНПТ(13). Объединяем в АДЕЗИЙНОПРТ(21) — корень.

Дерево Хаффмана

Чтобы получить код символа, нужно пройти путь от корня дерева до этого символа. Каждое движение влево добавляет к коду 0, каждое движение вправо — 1. Число под именем узла — сумма частот символов в его поддереве.

Коды Хаффмана

Средняя длина кода: (3·3 + 3·3 + 3·3 + 3·2 + 4·2 + 4·2 + 4·1 + 4·1 + 4·1 + 4·1 + 4·1 + 4·1) / 21 ≈ 3,24 бита на символ вместо стандартных 8 бит (1 байт). Коэффициент сжатия для этого текста — около 2,5×.

Почему это оптимально?

Оптимальность базируется на двух вещах:

1. Свойство оптимального поддерева. Два символа с наименьшими частотами обязательно должны находиться на максимальной глубине дерева и иметь общего родителя. Если бы это было не так, мы могли бы поменять их местами с более глубокими узлами и уменьшить общую стоимость.
2. Жадный выбор. Задача построения дерева обладает свойством оптимальной подструктуры. Решение всей задачи состоит из оптимальных решений её подзадач (объединения пар). Операция слияния двух узлов сводит задачу размера n к задаче размера n−1 с сохранением свойств оптимальности.

Практика, подводные камни и вариации

Проблема передачи дерева

Алгоритм Хаффмана сжимает данные великолепно, но только если декодер знает ту же самую таблицу частот (или готовое дерево). Как её передать? Если передавать саму таблицу, она может весить больше, чем сжатый файл (особенно для маленьких сообщений). Решения:

1. Для больших файлов накладные расходы на передачу таблицы пренебрежимо малы.
2. Существуют канонические коды Хаффмана. Вместо хранения полных кодов достаточно передать отсортированный список длин кодов и сами символы. Этого хватает, чтобы детерминированно восстановить структуру кодирования.
3. Для очень коротких сообщений выгоднее использовать статические предопределённые таблицы (как в семействе алгоритмов Deflate).

Статический vs Динамический Хаффман

Классический алгоритм называется статическим: мы сначала читаем всё сообщение, считаем частоты, строим дерево, затем кодируем. Это требует двух проходов по данным и наличия всего файла в памяти. В потоковых протоколах (модемы, стриминг видео) используется адаптивный динамический Хаффман. Дерево перестраивается «на лету» после каждого считанного символа. Начальное дерево содержит пустой алфавит (или специальный символ ESC для обозначения новых знаков). Декодер выполняет ровно те же операции обновления дерева, что и кодировщик, поэтому они всегда остаются синхронны.

Типичные ошибки при реализации

• Нестабильная сортировка при равных частотах. Если ваша структура данных не определяет строго поведение при равенстве весов, кодировщик и декодер могут построить разные деревья. Решение — добавлять уникальный идентификатор узла как второй ключ сравнения.
• Забытый случай одного символа. Если во всём файле встречается только буква «Я», дерево не должно упасть с ошибкой; оно должно породить код (обычно 0).
• Переполнение счётчиков частот в динамическом варианте (вес корня может превысить лимит целого числа).

Связь с энтропией Шеннона

Энтропия Шеннона устанавливает теоретический предел сжатия без потерь для источника с заданными вероятностями. Хаффман почти вплотную приближается к физическому пределу эффективности, проигрывая идеалу менее одного бита на весь символ (в среднем по всему сообщению этот хвост становится ничтожным).

Что лучше Хаффмана?

• Арифметическое кодирование и ANS (Asymmetric Numeral Systems). Позволяют достичь длины, сколь угодно близкой к энтропии, кодируя сразу целые блоки символов. Сегодня ANS является стандартом де-факто в современных компрессорах (например, в формате Zstandard).
• Кодирование длин серий (RLE). Специализированный метод для данных с длинными повторами (например, простых чёрно-белых факсов).

Заключение

Алгоритм Хаффмана — это фундаментальная классика Computer Science. Он элегантен, интуитивно понятен и демонстрирует красоту жадных алгоритмов и теории графов. Хотя в чистом виде он постепенно уступает место более мощным статистическим методам (ANS, PPM), его модификации лежат в основе практически любого современного архиватора и кодека. Понимание работы с бинарными деревьями, очередями с приоритетом и префиксными свойствами необходимо любому системному программисту.