Структуры и алгоритмы обработки данных


Применение бинарных деревьев для сжатия информации - часть 2


Алгоритм распаковки кода можно сформулировать следующим образом.

Распаковка

1. i:=0, j:=0;

2. если i>n, то стоп строка распакована, иначе i:=i+1;

3. node:= root;

4. если b(i)=0, то node:=left(node), иначе node:=right(node)

5. если left(node)=0 и right(node)=0, то j:=j+1, s(j):= str(node), перейти к шагу 2, иначе i:=i+1, перейти к шагу 4

В алгоритме корень дерева обозначен как root, а Left(node) и right(node) обозначают левый и правый потомки узла node.

pic4_15.gif (2233 bytes)

Рис. 4.15. Процесс распаковки кода

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

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




Начало  Назад  Вперед



Книжный магазин