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

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

Определение 3: Код Хаффмана D={d₁,d₂,_...,d_n} называется каноническим [2], если:
(1) Короткие коды (если их дополнить нулями справа) численно больше длинных,
(2) Коды одинаковой длины численно возрастают вместе с алфавитом.

Далее, для краткости, будем называть канонический код Хаффмана просто каноническим кодом.

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

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

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

Убедимся в том, что свойства (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[], symb[], offs[]. Где 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]=? - т.к. на втором уровне нет листовых узлов.

Теперь приведем алгоритм декодирования (CANONICAL_DECODE) [5]:

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]].

Приведем конкретный пример. Пользуясь изложенным алгоритмом декодируем сообщение Z^/.

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"

1. code = 0, length = 1

2. code = 0 < base[length] = 1
code = 0 << 1 = 0
code = 0 + 0 = 0
length = 1 + 1 = 2
code = 0 < base[length] = 2
code = 0 << 1 = 0
code = 0 + 0 = 0
length = 2 + 1 = 3
code = 0 < base[length] = 2
code = 0 << 1 = 0
code = 0 + 1 = 1
length = 3 + 1 = 4
code = 1 = base[length] = 1

3. symbol = symb[offs[length] = 2 + code = 1 - base[length] = 1] = symb[2] = A

1. code = 1, length = 1

2. code = 1 = base[length] = 1

3. symbol = symb[offs[length] = 7 + code = 1 - base[length] = 1] = symb[7] = H

1. code = 0, length = 1

2. code = 0 < base[length] = 1
code = 0 << 1 = 0
code = 0 + 0 = 0
length = 1 + 1 = 2
code = 0 < base[length] = 2
code = 0 << 1 = 0
code = 0 + 0 = 0
length = 2 + 1 = 3
code = 0 < base[length] = 2
code = 0 << 1 = 0
code = 0 + 0 = 0
length = 3 + 1 = 4
code = 0 < base[length] = 1
code = 0 << 1 = 0
code = 0 + 1 = 1
length = 4 + 1 = 5
code = 1 > base[length] = 0

3. symbol = symb[offs[length] = 0 + code = 1 - base[length] = 0] = symb[1] = F

Итак, мы декодировали 3 первых символа: A, H, F. Ясно, что следуя этому алгоритму мы получим в точности сообщение S.

Это, пожалуй, самый простой алгоритм для декодирования канонических кодов. К нему можно придумать массу усовершенствований. Подробнее о них можно прочитать в [5] и [9].

Поиск по сайту: