Чернега В.С. Сжатие информации в компьютерных сетях. Учебное пособие для вузов

Подождите немного. Документ загружается.

Динамическое кодирование неравномерными кодами

а) б)

Рис.4.7. Модификация дерева после получения второго символа “e” (a)

и после поступления символа “f”

Недостатком такого способа является дополнительный раcход

памяти для хранения конфигурации начального дерева, а также затраты

времени на манипуляции с деревом, на котором отмечены все возможные

символы алфавита, в то время как в сжимаемом сообщении используется

лишь часть из них.

Рис.4.8. Дерево Хаффмена после получения последнего символа сообщения

Оригинальный способ решения этой проблемы был предложен

Д.Кнутом [32]. Его суть состоит в следующем. Все символы используемого

Сжатие информации в компьютерных сетях

алфавита, которые еще не появились на выходе источника, отмечаются на

дереве нулевым узлом. Поэтому, когда символ, подлежащий сжатию,

генерируется впервые, кодер "отмечает" его, вырабатывая префиксную

комбинацию. Вслед за ней на выход поступает код несжатого символа. В

качестве префиксной комбинации используется код, соответствующий

листу нулевого веса. Для кодирования символов, поступивших от

источника впервые, используется не 8-ми разрядная комбинация ASCII-

кода, а минимальный префиксный код, построенный на основании

следующих соображений. Если имеется сообщение, состоящее из m

различных символов а

,..., а

, то число m можно представить в виде целой

степени двойки и целого числа r

m = 2

+ r , (4.1)

где 0  r < 2

. Тогда а

-й символ кодируется (е + 1) ― битовой

комбинацией числа k-1, если 1  k  2r . В противном случае - е-битовой

комбинацией числа k – r –1 . Например, если m = 6, то e = 2 и r = 2, а

символы источника будут отображаться комбинациями:

=> 000; a

=> 001; a

=> 010; a

=> 011; a

=> 10; a

=> 11.

Нетрудно заметить, что полученный код обладает свойством

префикса. Этот код является оптимальным, если символы имеют

одинаковую вероятность.

Пример 4.2.

Построить кодовое дерево и осуществить сжатие динамическим

кодом Хаффмена фразу "АBRACADABRA!". Здесь символ ! означает конец

строки. В качестве алфавита источника использовать только буквы

латинского алфавита.

Перед началом компрессии кодеру и декодеру известен только

размер алфавита и алгоритм кодирования. В данном случае m = 27.

Представим m в форме (4.1), т.е. m = 27 = 2

+ 11. Поскольку A является

первой буквой алфавита, то k = 1. Следовательно, комбинация

префиксного кода, отображающая символ A, будет 00000. Эта комбинация

поступает на выход кодера, а символ A отмечается на кодовом дереве

листом с весом 1, который соединен единичной ветвью с корнем дерева

(рис.4.9,а). Декодер легко расшифровывает первую комбинацию благодаря

префиксным свойствам используемого кода. Лист нулевого веса дерева

отображает оставшиеся символы алфавита. Чтобы не перемещать все

элементы массива после исключения А из списка символов алфавита, он

Динамическое кодирование неравномерными кодами

обменивается местом с последним элементом списка, которым является

знак !.

а) б)

в) г)

Рис.4.9. Пример построения кодовых деревьев для последовательности

“ABRACADABRA”

С поступлением от источника символа В на выход кодера выдается

0 - код нулевого узла, а за ним кодовая комбинация, отображающая В,

которая определяется по формуле (4.1). Поэтому В => 00001. Декодер,

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

Следовательно, за ним будут поступать биты символа, который еще не

подвергался компрессии. Дерево Хаффмена при этом приобретает вид

рис.4.9,б. Буква R является 18-й в латинском алфавите, т.е. k = 18, а

соответствующий ей код - 10001.

В связи с тем, что код нулевого узла дерева равен 00, то символ R

будет закодирован семиразрядной комбинацией 0010001. Кодовое дерево

после его модификации примет вид, показанный на рис.4.9,в. Продолжая

Сжатие информации в компьютерных сетях

процедуру кодирования до завершения строки, получаем набор кодовых

комбинаций, соответствующих поступившим символам:

A => 0; C => 100 00010; A => 0; D => 1100 00011;

A => 0; B => 110; R => 110; A => 0.

Дерево Хаффмена, построенное к этому моменту времени,

изображено на рис.4.9,г. Конечный элемент строки ! будет закодирован

комбинацией 1000 00000.Как видно из рассмотренного примера,

предложенный Д.Кнутом способ, обеспечивает однозначность

декодирования в процессе построения хаффменовского дерева и снижает

количество битов, затрачиваемых на кодирование символов, поступающих

от источника впервые.

4.3. Алгоритм динамического кодирования

Виттера

Дальнейшее усовершенствование алгоритма динамического

кодирования данных неравномерными кодами FGK было предложено

Д.Виттером [42]. Этот алгоритм получил название алгоритма V. При

поиске путей оптимизации процедуры кодирования данных кодом

Хаффмена автор исходил из того, что в новом алгоритме число обменов

узлов в процессе модификации кодового дерева должно ограничиваться

некоторым малым числом (в лучшем случае единицей), а динамическое

хаффменовское дерево должно строиться таким образом, чтобы

минимизировать не только суммарную длину внешнего пути W l

j j



, но

и величины l



, max{l

}. Минимизация высоты дерева Н = max{ l

}

позволит предотвратить образование длинных кодовых комбинаций при

кодировании очередного символа в сообщении. Виттеру в значительной

степени удалось решить поставленную задачу. Разработанный им алгоритм

обладает по сравнению с алгоритмом FGK следующими двумя

преимуществами.

1. Количество обменов узлами, при котором текущий узел

перемещается вверх по кодовому дереву в процессе его модификации,

ограничивается единицей. В алгоритме FGK верхняя граница числа

обменов составляет l

/ 2, где l

- длина кодового слова для z

(k+1)-го

символа до начала процедуры модификации.

Динамическое кодирование неравномерными кодами

2. Алгоритм V минимизирует длину внешнего пути дерева l

гарантирует дерево минимальной высоты Н = max {l

} при условии

минимизации суммарной длины внешнего пути дерева W l

j j



Суть усовершенствования алгоритма V состоит во введении новой

системы нумерации узлов кодового дерева, которая получила название

неявной нумерации (Imрlicit numbering). При неявной нумерации узлы

хаффменовского дерева нумеруются в порядке увеличения по уровням

слева направо и снизу вверх, т.е., узлы более низкого уровня имеют номера

меньше, чем узлы последующего уровня. Важнейшей особенностью

неявной нумерации является соблюдение необходимого условия

построения дерева, которое формулируется следующим образом:

Для каждого веса W

все внешние узлы (листья)

дерева с весом W

должны предшествовать

всем внутренним узлам веса W.

( * )

Нетрудно заметить, что это

условие является одной из

отличительных черт неявной

нумерации по сравнению с

другими алгоритмами.

Нумерация узлов,

производимая согласно

алгоритмому FGK, не всегда

соответствует неявной

нумерации. Так например,

хаффменовское дерево, изо-

браженное на рис.4.3,

соответствует условию неявной

нумерации, в то же время как

нумерация узлов в кодовых

деревьях, показанных на

рис.4.7-4.8, отличается от

неявной тем, что внутренний

узел с весом W=1

предшествует листьям с таким

же весом. Очевидно, что если

на рис.4.8 поменять местами

узлы 3 и 6 , а на рис.4.7 - узлы 5 и 6, то нумерация в модифицированном

дереве будет удовлетворять условию (*).

Для иллюстрации целесообразности применения алгоритма V

покажем на примере результат модификации хаффменовского дерева

Рис.4.10. Пример модификации дерева

Хаффмена по алгоритму Виттера

(этап 1)

Сжатие информации в компьютерных сетях

(рис.4.10 ) в соответствии с неявной нумерацией. Как видно из этого

рисунка кодовое дерево отвечает всем требованиям оптимального

хаффменовского дерева, но порядок расположения узлов одного веса не

соответствует необходимому условию (*) для дерева с неявной

нумерацией. Так внутренний узел с весом 1 расположен между двумя

листами с таким же весом.

Внутренний узел с весом 2 имеет меньше номер, чем лист с весом 2

и т.д. А по условию (*) неявной нумерации для каждого веса W лист с

весом W

должен предшествовать внутреннему узлу с весом W

. Для того,

чтобы листья с весом 1 (рис.4.10) предшествовали внутреннему узлу с

весом 1 необходимо узлы 3 и 5 поменять местами. Не забывайте, что

внутренний узел должен перемещаться со всем образованным им

поддеревом, так как его вес включает веса дочерних узлов. В результате

обмена дерево принимает вид (рис.4.11).

Затем, после перестановки узлов 6 и 7, дерево имеет конфигурацию,

изображенную на рис.4.12. Проводя последовательно аналогичным

образом перемещение узлов, окончательно получим модифицированное

дерево, представленное на рис.4.13. Общее количество битов, затраченных

на кодирование сообщения, для которого построено хаффменовское дерево

(рис.4.10 и рис.4.13) для обоих алгоритмов одинаково, т.е. W l

j j



. Однако

Рис.4.11. Пример модификации дерева Хаффмена по

алгоритму Виттера (этап 2)

Динамическое кодирование неравномерными кодами

длина внешнего пути модифицированного дерева l



уменьшилась с 28

до 22, а его высота Н = max {l

} - с 7 до 4-х.

Рис.4.12. Пример модификации дерева Хаффмена

по алгоритму Виттера (этап 3)

Рис.4.13. Модифицированное по алгоритму Виттера

кодовое дерево Хаффмена

Сжатие информации в компьютерных сетях

Кодовые комбинации для отображения одинаковых символов

одного и того же сообщения будут различны. Так при поступлении от

источника следующего символа f он будет закодирован по алгоритму FGK

словом 111111, а по алгоритму V отображающая его комбинация 1001

будет на два бита короче. Поэтому, если передача продолжится с символов

d,c,g,e,f или с еще не использованных символов, то формируемые кодовые

слова в алгоритме V будут короче, чем в FGK, т.е. стратегия минимизации

внешнего пути и высоты дерева оптимальна при предположении, что

любой появляющийся символ равновероятен.

Второй отличительной чертой алгоритма V является введение

понятия блока эквивалентных узлов. При этом узлы x и y эквивалентны,

если они имеют одинаковый вес и оба являются либо внутренними, либо

внешними. Узел блока, имеющий (при неявной нумерации) самый высокий

номер, называется лидером блока. Блоки упорядочиваются по увеличению

веса, причем блок листьев веса W должен предшествовать блоку

внутренних узлов того же самого веса.

Третья отличительная особенность алгоритма V заключается в

способе модификации дерева после получения очередного символа.

Главной операцией алгоритма по поддержанию условия неявной

нумерации (*) является скольжение и приращение (SlideAnd Increment).

Суть этой операции состоит в том, что узел, объявленный текущим,

обменивается с лидером своего блока и затем скользит в направлении

корня дерева по соседнему блоку, который непосредственно примыкает к

блоку текущего узла. Скольжение продолжается до тех пор, пока текущий

узел не пройдет весь блок и будет установлен во главу этого блока. Затем

осуществляется приращение веса текущего узла и новым текущим узлом

назначается родитель старого текущего узла. Операция скольжения с

приращением продолжается до достижения корня дерева. При этом выбор

родительского узла зависит от того, являлся ли текущий узел листом или

внутренним узлом. Если текущий узел был листом, то новым текущим

узлом становится родитель, с которым оказался связан текущий узел после

завершения скольжения. А в случае, если текущим узлом был внутренний

узел, то новым текущим узлом назначается его родительский узел, с

которым был связан текущий до начала скольжения.

На рис.4.14 приведен пример процедуры Slide AndIncrement. На

рис.4.14а (1) изображена ситуация, когда текущим узлом р является лист с

весом 4, который в процессе обмена стал лидером блока листьев с весом 4.

На рис.4.14б (1) приведен случай, при котором текущим узлом является

внутренний узел с весом 8. Очевидно, что если текущий узел образует

блок, состоящий из одного узла, то этот узел является и текущим и

лидером одновременно. Все узлы в блоке сдвигаются влево на одну

позицию, чтобы освободить ячейку памяти для текущего узла р. В

Динамическое кодирование неравномерными кодами

процессе скольжения узел р занимает в соседнем блоке самую крайнюю

позицию справа, то есть становится лидером блока (Рис.4.14а,б позиция (2

). На позиции (3) обеих рисунков показана ситуация после приращения

веса текущего узла на 1, а на позиции ( 4 ) - новое положение текущего

узла.

Рис.4.14. Модификация кодового дерева путем скольжения и приращения

Алгоритм Виттера динамического сжатия данных сводится к

следующему:

Алгоритм 4.2

Рrocedure Vitteruрdate;

BEGIN

LeafToIncrement:=0; {Установить начальное

значение переменной}

q:= лист дерева, соответствующий символу Z

(k+);

IF (q является 0-м узлом) и (К < N - 1) TНEN

Begin { Специальный случай N1 }

Заменить q на внутренний 0-й узел дерева и

создать два его дочерних узла: левый, нулевой узел и

правый, содержащий символ Z

(k+1);

q:=внутренний, только что созданный узел; {Определить текущий

узел}

LeafToIncrement :=правый дочерний узел текущего узла q

End

Сжатие информации в компьютерных сетях

ELSE Begin

Обменять q с лидером его блока;

IF q образует пару с 0-м узлом TНEN

Begin { Специальный случай N 2}

LeafToIncrement:= q;

q:= родитель q

End

End;

WНILE q не является корнем хаффменовского дерева DO

{Основной цикл; q должно быть лидером этого блока }

SlideAndIncrement (q); {Вызов процедуры

сколжение - приращение}

IF LeafToIncrement < > 0 TНEN

SlideAndIncrement(LeafToIncrement)

END;

;-------------------------------------------------------------

РROCEDURE SlideAndIncrement (р);

Begin

wt:= вес р; {р - текущий узел дерева}

b:= следующий за р-м блок в компонуемом списке;

IF (( р-лист) AND (b-блок внутренних узлов

весом wt))

OR (( р-является внутренним узлом ) AND

(b-является блоком листьев весом wt+1)) TНEN

Begin

Скольжение р во главу блока узлов b;

р-й вес:=wt+1;

IF р является листом TНEN

р:=новый родитель р {родитель р после скольжения}

ELSE р:=прежний родитель р {родитель р до скольжения}

End

End.

СТРУКТУРА ДАННЫХ. При реализации алгоритма V компрессии

сообщений необходимо так организовать структуру данных, чтобы она

позволяла выполнять следующии функции:

- представлять двоичное дерево Хаффмена с положительными

весами в соответствии с необходимым условием неявной нумерации (*);

- сохранять непрерывный список внутренних узлов дерева в

порядке возрастания весов в соответствии с неявной нумерацией;

аналогичный список составляется и для внешних узлов (листьев) дерева;