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

Материал из Викиконспекты
Версия от 00:46, 4 января 2014; Zakhar Voit (обсуждение | вклад) (Новая страница: «== Способ хранения информации об оптимальном префиксном коде == При передаче информации ...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Способ хранения информации об оптимальном префиксном коде

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

Пусть у нас есть алфавит [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]\forall i: |c_i| \le n[/math], поэтому мы можем, используя [math]32 + n^2[/math] бит передать всю необходимую информацию: сначала передадим число [math]n[/math] - размер алфавита (для этого можно использовать, к примеру, [math]32[/math] бита, предполагая, что размер алфавита не превышает [math]2^{32} - 1[/math]), а потом [math]n[/math] блоков по [math]n[/math] бит: для каждого символа в алфавите (в отсортированном порядке) передадим его код, дополненный до [math]n[/math] бит нулями в конце записи.

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


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

Будем решать подзадачу о передаче структуры дерева последовательными оптимизациями.

Для начала заметим, что в дереве [math]n[/math] листьев, откуда следует, что в нем [math]2n - 2[/math] ребра. Доказать это просто из самого алгоритма Хаффмана: в нем [math]n - 1[/math] фаза, и на каждой фазе удаляются ровно два ребра.

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

Затратим мы [math]2\cdot(2n - 2) \cdot 2[/math] бита — [math]2\cdot(2n - 2)[/math] раз мы пройдем по ребрам, [math]2[/math] бита — на хранение информации о типе ребра.

Второй способ: заметим, что на самом деле мы можем объединить ребра типа [math]L[/math] и [math]R[/math] в ребро типа [math]D[/math], которое значит, что мы спускаемся вниз, а в которого ребенка — в левого или в правого, можно определить на месте. Таким образом требуемый объем памяти снижается до [math]2\cdot(2n - 2)[/math], так как мы до сих пор по каждому ребру проходим дважды, но уже на хранение информации о ребре требуется лишь один бит.

Третий способ: модифицируем значение команды [math]U[/math]. Пусть теперь символ [math]U[/math] значит, что мы поднимаемся к предку текущей вершины, пока мы — правый ребенок или пока не достигли корня, и если мы, остановившись, пришли из левого сына вершины, перейдем по ребру в правого ребенка. Несложно заметить, что мы корректно обойдем все дерево, а так же при обработке каждого символа (как [math]U[/math], так и [math]D[/math]) мы ровно по одному ребру проходим в первый раз. Значит, длина строки — [math]2n - 2 + 1 = 2n - 1[/math] (по каждому ребру проходим один раз, а так же последний [math]U[/math] дает возможность понять, что мы обошли все дерево, и служит терминальным символом).

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

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