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

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

¶История

Алгоритм построения оптимального префиксного кода был предложен Дэвидом Хаффманом в 1952 году. Однако оригинальный метод не задавал жёсткого порядка кодовых слов, что приводило к неоднозначности при декодировании, если таблица кодов не передавалась явно. В 1970-х годах для практических задач сжатия (в частности, для архиваторов и кодеков) была разработана концепция канонического кода. Она впервые была формализована в стандарте сжатия данных PKZIP (алгоритм Deflate, 1993 год) и впоследствии закреплена в спецификациях JPEG, MPEG, GZIP и других. Основная цель введения канонической формы — замена полной таблицы кодов компактным представлением, состоящим только из длин кодовых слов.

¶Определение и свойства

Канонический код Хаффмана удовлетворяет следующим условиям:

Префиксность: ни одно кодовое слово не является началом другого.
Оптимальность: код построен по алгоритму Хаффмана и минимизирует среднюю длину кодового слова для заданного распределения вероятностей символов.
Каноничность: кодовые слова одинаковой длины упорядочены по возрастанию их числового значения, а сами длины кодовых слов не убывают при переходе от одного символа к другому.

Формально, если длины кодовых слов для символов алфавита равны \(l_1, l_2, \dots, l_n\) (где \(l_i\) — длина кода для i-го символа), то канонический код строится следующим образом:

Символы сортируются по возрастанию длины кода, а при равной длине — по порядку исходного алфавита (или по частоте).
Первое кодовое слово минимальной длины \(l_{\min}\) получает значение \(0^{l_{\min}}\) (строка из \(l_{\min}\) нулей).
Каждое следующее кодовое слово той же длины получает значение предыдущего, увеличенное на 1.
При переходе к следующей длине \(l' > l\) новое кодовое слово получается путём добавления нулей к двоичной записи числа, равного (предыдущее кодовое слово + 1), сдвинутого влево на \((l' - l)\) бит.

Это гарантирует, что декодирование возможно без явного хранения кодовых слов — достаточно знать только длины кодов для каждого символа.

¶Алгоритм построения

Построение канонического кода Хаффмана включает два этапа:

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

Определяется максимальная длина кода \(L_{\max}\).
Создаётся массив длин кодовых слов для каждого символа.
Символы сортируются по возрастанию длины кода.
Применяется описанный выше алгоритм присвоения кодовых слов.

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

¶Преимущества перед обычным кодом Хаффмана

Основное преимущество канонического кода — компактное представление таблицы кодирования. Для обычного кода Хаффмана требуется передать каждое кодовое слово (например, в виде пары «символ — кодовая строка»), что может занимать десятки и сотни байт. Для канонического кода достаточно передать список длин кодовых слов для каждого символа (обычно 4–8 бит на символ) или даже более эффективную кодировку — например, коды длин по Хаффману (как в Deflate). Это особенно важно для сжатия коротких сообщений, где размер заголовка может превышать размер сжатых данных.

Дополнительные преимущества:

Упрощение декодирования: декодер может восстановить кодовые слова по длинам, используя простой алгоритм, что ускоряет работу.
Совместимость: каноническая форма является стандартом для многих форматов сжатия, что обеспечивает взаимозаменяемость кодеров и декодеров.
Устойчивость к ошибкам: при передаче длин кодов можно использовать помехоустойчивое кодирование, что повышает надёжность.

¶Применение

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

Deflate (форматы ZIP, GZIP, PNG): основной алгоритм сжатия, где канонический код применяется для кодирования литералов, длин повторов и смещений. В спецификации Deflate длины кодовых слов передаются в виде кодов Хаффмана для самих длин.
JPEG: в стандарте сжатия изображений используется канонический код Хаффмана для кодирования DC- и AC-коэффициентов после дискретного косинусного преобразования. В заголовке JPEG передаются таблицы длин кодовых слов.
MP3 (MPEG-1 Audio Layer 3): для кодирования масштабных коэффициентов и битовой информации применяется канонический код Хаффмана, что позволяет снизить битрейт без потери качества.
Brotli: современный алгоритм сжатия, разработанный Google, использует канонический код Хаффмана как часть контекстного моделирования.
Zstandard (Zstd): алгоритм сжатия от Facebook (организация Meta признана экстремистской и запрещена в РФ) использует канонический код Хаффмана для энтропийного кодирования наряду с ANS (асимметричными системами счисления).

¶Пример

Рассмотрим алфавит из 4 символов с частотами: A (50%), B (25%), C (15%), D (10%). Дерево Хаффмана даёт длины кодов: A — 1, B — 2, C — 3, D — 3. Канонический код строится следующим образом:

Сортировка по длине: A (1), B (2), C (3), D (3).
Первое кодовое слово длины 1: «0».
Следующее слово длины 1 отсутствует.
Переход к длине 2: предыдущее кодовое слово «0» + 1 = «1», сдвиг влево на (2-1)=1 бит: «10».
Длина 3: предыдущее кодовое слово «10» + 1 = «11», сдвиг влево на (3-2)=1 бит: «110».
Следующее слово длины 3: «110» + 1 = «111».

Итоговые коды: A — 0, B — 10, C — 110, D — 111. Эти коды удовлетворяют условию префиксности и упорядочены лексикографически.

¶Критика

Несмотря на широкое распространение, канонический код Хаффмана имеет ограничения:

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

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

¶Источники

Д. Хаффман, «A Method for the Construction of Minimum-Redundancy Codes», Proceedings of the IRE, 1952.
RFC 1951 (Deflate Compressed Data Format Specification), 1996.
ITU-T T.81 (JPEG Standard), 1992.
ISO/IEC 11172-3 (MPEG-1 Audio Layer 3), 1993.
J. Ziv, A. Lempel, «A Universal Algorithm for Sequential Data Compression», IEEE Transactions on Information Theory, 1977.
С. В. Абрамов, «Сжатие данных: теория и практика», 2015.

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →