Оптимальное хранение словаря в алгоритме Хаффмана

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

Постановка задачи

Пусть у нас есть алфавит [math]\Sigma = \{a_1, a_2, \cdots, a_n\}[/math], [math]|\Sigma| = n[/math], и код [math]c[/math], сопоставляющий каждому символу [math]a_i[/math] его код [math]c_i[/math].

Нужно придумать эффективное представление кода [math] c [/math] в памяти.

Простое решение

Заметим, что [math]\forall i: |c_i| \le n[/math]. Дополним все коды до длины [math] n [/math] нулями и запишем их друг за другом. Также необходимо передать [math] n [/math]. При условии, что [math] n [/math] не превышает [math] 2^{32} - 1 [/math] получаем [math] 32 + n^2 [/math] дополнительных бит на передачу префиксного кода.

Чтобы декодировать полученную информацию о коде, достаточно сначала узнать [math]n[/math] и записать в префиксное дерево коды всех символов. Построив соответствующее дерево, можно заметить, что некоторые вершины имеют одного ребенка — такие вершины получены в результате дополнения нашего оптимального кода до [math]n[/math] бит нулями. Все такие вершины можно просто удалить из дерева, и мы получим оптимальный префиксный код, который мы передавали.

Пример

Для примера возьмем слово "миссисипи". Тогда код [math] c [/math] будет выглядеть следующим образом:

Символ	и	м	п	с
Код	0	100	101	11

При помощи нашего алгоритма [math] c [/math] будет закодирован как:

0000 1000 1010 1100

Построим префиксное дерево по полученному коду:

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

Эффективное решение

Построим префиксное дерево, соответствующее нашему коду [math]c[/math]. Наша задача состоит из двух подзадач: передача структуры этого дерева и передача информации для различения листьев.

Передача структуры дерева

Обойдем дерево, используя обход в глубину. Каждый раз, проходя по ребру запишем одну из букв [math] L [/math], [math] R [/math] или [math] U [/math], в зависимости от того, куда по ребру мы прошли ([math]L[/math] - в левого ребенка, [math]R[/math] - в левого ребенка, [math]U[/math] - в родителя). Эта информация поможет нам восстановить дерево.

Построим обход дерева Хаффмана для слова "миссисипи":

LURLLURUURUU

Первая модификация

Заметим, что на самом деле мы можем объединить ребра типа [math]L[/math] и [math]R[/math] в ребро типа [math]D[/math], которое значит, что мы спускаемся вниз, а в которого ребенка — в левого или в правого, можно определить на месте.

Модифицируем наш обход:

DUDDDUDUUDUU

Вторая модификация

Модифицируем значение команды [math]U[/math]. Пусть теперь символ [math]U[/math] значит, что мы поднимаемся к предку текущей вершины, пока мы — правый ребенок или пока не достигли корня, и если мы, остановившись, пришли из левого сына вершины, перейдем по ребру в правого ребенка. После такой модификации записывая каждый символ мы ровно по одному ребру проходим в первый раз.

Конечный вариант кодировки дерева:

DUDDUUU

Распишем подробнее:

D	Спускаемся влево
U	Поднимаемся и спускаемся вправо
D	Спускаемся влево
D	Спускаемся влево
U	Поднимаемся и спускаемся вправо
U	Поднимаемся, поднимаемся и спускаемся вправо
U	Поднимаемся до корня

Оценим используемое количество памяти. Так как в нашем дереве [math] n [/math] листьев, то в нем [math] 2 \cdot n - 2 [/math] (это легко показать из алгоритма Хаффмана, в нем [math] n - 1 [/math] итерация и на каждой в дерево добавляется по 2 ребра), а символов в нашей записи будет [math] 2 \cdot n - 1 [/math], так как на каждое ребро приходится по символу плюс последний, терминальный, [math] U [/math].

Передача информации для восстановления листьев

Сопоставим каждому символу алфавита равномерный код [math]c'[/math] длины [math] \lceil log_{2} \rceil n[/math] - его порядковый номер в алфавите, записанный в двоичной системе счисления. Тогда, если выписать подряд коды [math]c'[/math] для всех символов в том порядке, в котором обход в глубину посещает соответствующие им листы, несложно восстановить, какому символу какой код [math]c[/math] соответствует.

Используемая память

Итого, задача решена с использованием [math]n \lceil log_{2} \rceil n + 2n - 1[/math] бит.

Ссылки

• Алгоритм Хаффмана
• Обход в глубину