Кодирование Хаффмана

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

История

Алгоритм был предложен Дэвидом Хаффманом в 1952 году в его докторской диссертации в Массачусетском технологическом институте. Изначально Хаффман работал над курсовым проектом под руководством Роберта Фано, который предлагал студентам найти оптимальный код с минимальной избыточностью. Фано и Клод Шеннон ранее разработали метод кодирования (код Шеннона — Фано), но он не всегда давал оптимальный результат. Хаффман, разочаровавшись в подходе преподавателей, нашёл собственное решение, основанное на построении бинарного дерева снизу вверх. Результат оказался настолько эффективным, что работа была опубликована в журнале Proceedings of the IRE под названием «A Method for the Construction of Minimum-Redundancy Codes».

В 1970-х и 1980-х годах алгоритм стал широко применяться в системах передачи данных и хранения информации. Он лёг в основу многих форматов сжатия, включая PKZIP (алгоритм Deflate), JPEG, MP3 и факсимильную связь. В 1990-х годах появились адаптивные версии, такие как алгоритм Хаффмана с динамическим деревом, не требующие предварительной передачи таблицы кодов.

Принцип работы

Алгоритм Хаффмана состоит из двух основных этапов: построение дерева Хаффмана и генерация кодов. Для работы требуется знание частоты (вероятности) появления каждого символа в исходных данных.

Построение дерева Хаффмана

1. Формирование списка узлов. Каждый символ исходного алфавита представляется как листовой узел дерева, которому присваивается вес, равный частоте символа.
2. Слияние двух узлов с наименьшим весом. Из списка выбираются два узла с минимальными весами. Они объединяются в новый внутренний узел, вес которого равен сумме весов дочерних узлов. Один из дочерних узлов помечается как «0», другой — как «1» (или наоборот).
3. Повторение шага 2. Новый узел добавляется в список, а два исходных удаляются. Процесс повторяется до тех пор, пока в списке не останется единственный корневой узел.

В результате образуется бинарное дерево, где каждый лист соответствует символу, а путь от корня к листу определяет его кодовое слово.

Генерация кодов

Код для каждого символа получается путём обхода дерева от корня к соответствующему листу. Последовательность битов (0 или 1) на рёбрах пути составляет кодовое слово. Например, если символ «A» с высокой частотой оказывается на глубине 2, его код может быть «00», а редкий символ «Z» — на глубине 6, с кодом «111010».

Декодирование

Декодирование выполняется путём последовательного чтения битов сжатого потока и движения по дереву от корня. При достижении листа выводится соответствующий символ, и процесс продолжается с корня для следующего символа. Благодаря префиксному свойству декодирование однозначно и не требует синхронизации.

Виды кодирования Хаффмана

Статическое кодирование

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

Адаптивное (динамическое) кодирование

Адаптивное кодирование не требует предварительного анализа данных. Дерево строится и обновляется в процессе чтения потока. Изначально все символы имеют одинаковый вес, а по мере появления новых символов веса корректируются, и дерево перестраивается. Этот подход используется в некоторых реализациях для потокового сжатия, но сложнее в реализации и может быть медленнее.

Каноническое кодирование Хаффмана

Каноническая форма кода Хаффмана предполагает упорядочивание кодовых слов по длине и лексикографическому порядку. Такая форма упрощает передачу таблицы кодов и ускоряет декодирование (например, с использованием таблиц поиска). Канонический вариант используется в алгоритме Deflate и формате JPEG.

Свойства и характеристики

• Оптимальность. Код Хаффмана является оптимальным среди всех префиксных кодов для заданного распределения вероятностей (с точностью до целого числа битов на символ). Средняя длина кода не превышает энтропию источника более чем на 1 бит.
• Префиксность. Ни одно кодовое слово не является началом другого, что позволяет декодировать поток без разделителей.
• Неравномерность. Длина кода обратно пропорциональна частоте символа.
• Однозначность декодирования. При корректном построении дерева декодирование всегда однозначно.

Ограничения

• Алгоритм требует знания частот символов, что может быть накладным для потоковых данных.
• При равномерном распределении вероятностей (например, все символы встречаются одинаково часто) код Хаффмана не даёт сжатия и может даже увеличить размер из-за таблицы.
• Для достижения высокой степени сжатия требуется большой объём данных, чтобы статистика была репрезентативной.

Применение

Кодирование Хаффмана используется в различных областях сжатия данных:

• Архиваторы: PKZIP, WinRAR, 7-Zip (в составе алгоритма Deflate).
• Графика: формат JPEG (в сочетании с дискретным косинусным преобразованием), PNG (после фильтрации и сжатия Deflate).
• Аудио: формат MP3 (на этапе кодирования коэффициентов), FLAC (сжатие без потерь).
• Факсимильная связь: стандарты Group 3 и Group 4 (кодирование модифицированного Хаффмана для чёрно-белых изображений).
• Телекоммуникации: кодирование сообщений в протоколах передачи данных.

Пример

Рассмотрим строку «AABBBCCCC». Частоты символов: A — 2, B — 3, C — 4. Построение дерева:

1. Узлы: A(2), B(3), C(4).
2. Слияние A и B: узел AB(5) с потомками A(0) и B(1).
3. Слияние AB(5) и C(4): корень (9) с потомками C(0) и AB(1).
4. Коды: C — 0, A — 10, B — 11.

Исходная строка (9 символов) при равномерном кодировании (2 бита на символ) занимает 18 бит. Код Хаффмана: C(0) — 4 бита, A(10) — 4 бита, B(11) — 6 бит, всего 14 бит. Сжатие составило ~22 %.

Критика и альтернативы

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

Источники

• Huffman, D. A. «A Method for the Construction of Minimum-Redundancy Codes». Proceedings of the IRE, vol. 40, no. 9, 1952, pp. 1098–1101.
• Cover, T. M., Thomas, J. A. «Elements of Information Theory». 2nd ed., Wiley, 2006.
• Salomon, D. «Data Compression: The Complete Reference». 4th ed., Springer, 2007.
• Sayood, K. «Introduction to Data Compression». 5th ed., Morgan Kaufmann, 2017.