Передача кодового дерева

Вычисление канонических кодов

Как мы уже неоднократно отмечали, длин кодов достаточно для того чтобы сгенерировать сами коды. Посмотрим, как это можно сделать. Предположим, что мы уже вычислили длины кодов и подсчитали, сколько кодов каждой длины у нас есть. Пусть L -максимальная длина кода, а T_i - количество кодов длины i.

Вычислим S_i - начальное значение кода длины i, для всех i из [1..L]

S_L = 0 (всегда)
S_L-1 = (S_L + T_L) >> 1
S_L-2 = (S_L-1 + T_L-1) >> 1
...
S₁ = 1 (всегда)

Для нашего примера L = 5, T_{1.. 5} = {1, 0, 2,3, 2}.

S₅ = 00000_bin = 0_dec
S₄ = (S₅=0 + T₅=2) >> 1 = (00010_bin >> 1) = 0001_bin = 1_dec
S₃ = (S₄=1 + T₄=3) >> 1 = (0100_bin >> 1) = 010_bin = 2_dec
S₂ = (S₃=2 + T₃=2) >> 1 = (100_bin >> 1) = 10_bin = 2_dec
S₁ = (S₂=2 + T₂=0) >> 1 = (10_bin >> 1) = 1_bin = 1_dec

Видно, что S₅, S₄, S₃, S₁ - в точности коды символов B, A, C, H. Эти символы объединяет то, что все они стоят на первом месте, каждый на своем уровне. Другими словами, мы нашли начальное значение кода для каждой длины (или уровня).

Теперь присвоим коды остальным символам. Код первого символа на уровне i равен S_i, второго S_i + 1, третьего S_i + 2 и т.д.

Выпишем оставшиеся коды для нашего примера:

B = S5 = 00000bin	A = S4 = 0001bin	C = S3 = 010bin	H = S1 = 1bin
F = S5 + 1 = 00001bin	D = S4 + 1 = 0010bin	E = S3 + 1 = 011bin
	G = S4 + 2 = 0011bin

Видно, что мы получили точно такие же коды, как если бы мы явно построили каноническое дерево Хаффмана.

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

Решить эту задачу можно несколькими способами.

1. Самое очевидное решение - сохранить дерево в явном виде (т.е. как упорядоченное множество узлов и указателей того или иного вида). Это самый расточительный и неэффективный способ.

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

3. Наконец, можно использовать одно из свойств канонических кодов. Как уже было отмечено ранее, канонические коды вполне определяются своими длинами. Другими словами, все что необходимо декодеру - это список длин кодов символов. Учитывая, что в среднем длину одного кода для N-символьного алфавита можно закодировать é(log₂(log₂N))ù битами, получим очень эффективный алгоритм. На нем мы остановимся подробнее.

Предположим, что размер алфавита N=256, и мы сжимаем обыкновенный текстовый файл (ASCII). Скорее всего, мы не встретим все N символов нашего алфавита в таком файле. Положим тогда длину кода не встретившихся символов равной нулю. В этом случае сохраняемый список длин кодов будет содержать достаточно большое число нулей сгруппированных вместе. Каждую такую группу можно сжать при помощи RLE кода. Этот алгоритм чрезвычайно прост.

Более того, этот метод можно несколько расширить. Мы можем применить алгоритм RLE не только к группам нулевых длин, но и ко всем остальным. Такой способ передачи кодового дерева является общепринятым и применяется в большинстве современных реализаций.

Дата добавления: 2014-12-16