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

Как можно было заметить из предыдущего раздела, код Хаффмана не единственен. Мы можем подвергать его любым трансформациям без ущерба для эффективности при соблюдении всего двух условий: коды должны остаться префиксными и их длины не должны измениться.

Определение 3: Код Хаффмана D={d₁,d₂,_...,d_n} называется каноническим, если:

1. Короткие коды если их дополнить нулями справа численно больше длинных,
2. Коды одинаковой длины численно возрастают вместе с алфавитом.

Определение 4: Бинарное дерево, соответствующее каноническому коду Хаффмана, будем называть каноническим деревом Хаффмана.

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

Исходное дерево Хаффмана	Каноническое дерево Хаффмана
ROOT /\ 0 1 / \ /\ H / \ / \ / \ 0 1 / \ / \ / \ / \ /\ /\ 0 1 0 1 / \ / \ C /\ /\ E 0 1 0 1 / \ / \ A D /\ G 0 1 / \ F B	ROOT /\ 0 1 / \ /\ H / \ / \ 0 1 / \ / \ / \ /\ /\ / \ / \ 0 1 0 1 / \ / \ / \ / \ /\ /\ C E 0 1 0 1 / \ / \ /\ A D G 0 1 / \ B F

Выпишем канонические коды для всех символов нашего алфавита в двоичной и десятичной форме. При этом сгруппируем символы по длине кода.

B=00000bin=0dec	A=0001bin=1dec	C=010bin=2dec	H=1bin=1dec
F=00001bin=1dec	D=0010bin=2dec	E=011bin=3dec
	G=0011bin=3dec

Убедимся в том, что свойства (1) и (2) из определения 3 выполняются:

Рассмотрим, к примеру, два символа: E и G. Дополним код символа E =011_bin=3_dec = 5-3 = 2 нулями справа: E ^/=011 00_bin=12_dec, аналогично получим G ^/=0011 0_bin=6_dec.

Видно, что E ^/> G ^/. Рассмотрим теперь три символа: A, D, G. Все они имеют код одной длины. Лексикографически A < D < G. В таком же отношении находятся и их коды: 1<2<3.

Далее заметим, что порядковый номер любого листового узла, на занимаемом им уровне, численно равен коду соответствующего ему символа. Это свойство канонических кодов называют числовым (Numerical property).

Поясним вышесказанное на примере. Рассмотрим символ C. Он находится на 3^муровне (имеет длину кода 3). Его порядковый номер на этом уровне равен 2 (учитывая два нелистовых узла слева), т.е. численно равен коду символа C. Теперь запишем этот номер в двоичной форме и дополним его нулевым битом слева (т.к. 2 представляется двумя битами, а код символа C тремя): 2_dec=10_bin=>0 10_bin. Мы получили в точности код символа C.

Таким образом, мы пришли к очень важному выводу: канонические коды вполне определяются своими длинами. Это свойство канонических кодов очень широко используется на практике.

Теперь вновь закодируем сообщение S, но уже при помощи канонических кодов:

Z^/="0001 1 00001 00000 1 010 011 1 011 1 010 011 0001 1 0010 010 011 011 1 1 1 010 1 1 1 0010 011 0011 1 0011 0011 011 1 010 1 1"

Т.к. мы не изменили длин кодов, размер закодированного сообщения не изменился: |S^/|=|Z^/|=89 бит.

Теперь декодируем сообщение Z^/, используя свойства канонических кодов.

Построим три массива:

base[i] - количество нелистовых узлов на уровне i;

symb[] - перестановка символов алфавита, отсортированная по двум ключам: первичный - длина кода, вторичный - лексикографическое значение;

offs[i] - индекс массива symb[], такой что symb[offs[i]] первый листовой узел (символ) на уровне i.

В нашем случае: base[0..5]={-, 1, 2, 2, 1, 0}, symb[0..7]={B, F, A, D, G, C, E, H}, offs[0..5]={-, 7, -, 5, 2, 0}.

Приведем несколько пояснений. base[0]= - и offs[0]= - не используются, т.к. нет кодов длины 0, а offs[2]=? - т.к. на втором уровне нет листовых узлов.

Теперь приведем алгоритм декодирования:

1. code = следующий бит из потока, length = 1
2. Пока code < base[length]
   code = code << 1
   code = code + следующий бит из потока
   length = length + 1
3. symbol = symb[offs[length] + code - base[length]]

Другими словами, будем вдвигать в переменную code бит за битом из входного потока, до тех пор, пока code < base[length]. При этом на каждой итерации будем увеличивать переменную length на 1 (т.е. продвигаться вниз по дереву). Цикл в (2) остановится когда мы определим длину кода (уровень в дереве, на котором находится искомый символ).

Предположим, что цикл в (2), после нескольких итераций, остановился. В этом случае выражение (code - base[length]) по сути порядковый номер искомого узла (символа) на уровне length. Первый узел (символ), находящийся на уровне length в дереве, расположен в массиве symb[] по индексу offs[length]. Но нас интересует не первый символ, а символ под номером (code - base[length]). Поэтому индекс искомого символа в массиве symb[] равен (offs[length] + (code - base[length])). Иначе говоря, искомый символ symbol=symb[offs[length] + code - base[length]].

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