Алгоритм Хаффмана

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

История

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

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

Алгоритм Хаффмана относится к классу жадных алгоритмов и использует подход «снизу вверх». Он строит дерево кодов, в котором каждый символ исходного алфавита представлен листовой вершиной, а путь от корня к символу задаёт его двоичный код.

Основные понятия

• Префиксный код — код, в котором ни одно кодовое слово не является префиксом другого кодового слова. Это свойство обеспечивает однозначное декодирование без использования разделителей.
• Частота символа — количество вхождений символа в исходные данные (или вероятность его появления).
• Вес вершины — сумма частот всех символов в поддереве данной вершины.

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

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

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

1. Завершение: Когда в очереди остаётся одна вершина, она является корнем построенного дерева Хаффмана.

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

После построения дерева каждому символу присваивается код, соответствующий пути от корня к листу. Обычно левое ребро кодируется как «0», а правое — как «1» (или наоборот, в зависимости от соглашения). Длина кода равна глубине листа в дереве.

Пример работы

Рассмотрим строку «AABBBCCCDDDD». Частоты символов: A — 2, B — 3, C — 3, D — 4.

1. Начальные вершины: A(2), B(3), C(3), D(4).
2. Извлекаем A(2) и B(3). Создаём внутреннюю вершину AB(5). Очередь: C(3), D(4), AB(5).
3. Извлекаем C(3) и D(4). Создаём CD(7). Очередь: AB(5), CD(7).
4. Извлекаем AB(5) и CD(7). Создаём корень ABCD(12). Очередь пуста.

Коды (при условии, что левый потомок — «0», правый — «1»):

• D: 1 (глубина 1)
• C: 01 (глубина 2)
• B: 001 (глубина 3)
• A: 000 (глубина 3)

Исходная строка (12 символов) занимает 12 × 8 = 96 бит (в ASCII). Сжатая строка занимает: 4×1 + 3×2 + 3×3 + 2×3 = 4 + 6 + 9 + 6 = 25 бит. Коэффициент сжатия — около 3,84:1.

Свойства алгоритма

Оптимальность

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

Ограничения

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

Разновидности и модификации

Адаптивный алгоритм Хаффмана

В адаптивной версии (алгоритм Фоллера — Галлагера — Кнута) дерево Хаффмана строится динамически по мере обработки данных. Частоты символов обновляются после каждого прочитанного символа, и дерево перестраивается. Это позволяет сжимать потоковые данные без предварительного анализа.

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

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

n-арный код Хаффмана

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

Применение

Алгоритм Хаффмана широко используется в различных областях компьютерных наук и цифровых технологий:

• Сжатие файлов: В форматах PKZIP (алгоритм Deflate, комбинирующий LZ77 и кодирование Хаффмана), Gzip, Bzip2.
• Изображения: В формате JPEG (кодирование коэффициентов дискретного косинусного преобразования), PNG (фильтрация и кодирование Хаффмана для фильтрованных данных).
• Аудио и видео: В стандартах MP3, AAC, H.264 (как часть энтропийного кодирования).
• Передача данных: В протоколах факсимильной связи (Group 3 и Group 4).
• Архиваторы: 7-Zip, RAR, WinZip.

Связь с другими методами

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

Интересные факты

• Дэвид Хаффман разработал алгоритм в возрасте 25 лет, работая над курсовым проектом. Он рассматривал это как альтернативу сдаче выпускного экзамена.
• Первоначально алгоритм не привлёк большого внимания, но позже стал одним из самых цитируемых результатов в теории информации.
• В 1998 году Хаффман получил медаль Ричарда Хэмминга за вклад в теорию информации.

Источники

• Huffman, D. A. «A Method for the Construction of Minimum-Redundancy Codes.» Proceedings of the IRE, 1952.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. «Introduction to Algorithms.» MIT Press, 2009.
• Cover, T. M., Thomas, J. A. «Elements of Information Theory.» Wiley, 2006.
• Salomon, D. «Data Compression: The Complete Reference.» Springer, 2007.