←предыдущая следующая→
1 2 3 4 5 6 7
ниже листьев, поэтому значения индексов
между 1 и maxchar включительно будут применены для обозначения ссылок на внут-
ренние узлы, когда как значения индексов между maxchar + 1 и 2 * maxchar + 1
включительно - ссылок на листья. Заметим что корень дерева всегда находится в
1-ой ячейке и имеет неопределенного родителя. Cоотвествующая листу буква может
быть найдена вычитанием maxchar + 1 из его индекса.
Если окончание текста источника может быть обнаружено из его контекста, то
коды исходного алфавита все находятся в интервале codetype, а максимально воз-
можное в этом тексте значение кода будет maxchar. В противном случае, интервал
codetype должен быть расширен на один код для описания специального символа
"конец файла". Это означает, что maxchar будет на 1 больше значения максималь-
ного кода символа исходного текста.
Следующая процедура инициализирует дерево кодов. Здесь строится сбаланси-
рованное дерево кодов, но на самом деле, каждое начальное дерево будет удовле-
творительным до тех пор, пока оно же используется и для сжатия и для разверты-
вания.
procedure initialize;
var
i: downindex;
j: upindex;
begin
for i := 2 to twicemax do
up[i] := i div 2;
for j := 1 to maxchar do begin
left[j] := 2 * j;
right[j] := 2 * j + 1;
end
end { initialize };
После того, как каждая буква сжата ( развернута ) с помощью текущей версии
дерева кодов, оно должно быть расширено вокруг кода этой буквы. Реализация
этой операции показана в следующей процедуре, использующей расширение снизу-
вверх:
procedure splay( plain: codetype );
var
c, d: upindex { пары узлов для полуобоpота };
a, b: downindex { вpащаемые наследники узлов };
begin
a := plain + succmax;
repeat { обход снизу вверх получередуемого дерева }
c := up[a];
if c # root then begin { оставляемая пара }
d := up[c];
{ перемена местами наследников пары }
b := left[d];
if c = b then begin b := right[d];
right[d] := a;
end else left[d] := a;
if a = left[c] then left[c] := b;
else right[c] := b;
up[a] := d;
up[b] := c;
a := d;
end else a := c { управление в конце нечетным узлом };
until a = root;
end { splay };
Чтобы сжать букву исходного текста ее нужно закодировать, используя дере-
во кодов, а затем передать. Поскольку процесс кодирования производится при об-
ходе дерева от листа к корню, то биты кода записываются в обpатном порядке.
Для изменения порядка следования битов процедура compress пpименяет свой стек,
биты из которого достаются по одному и передаются процедуре transmit.
procedure compress( plain: codetype );
var
a: downindex;
sp: 1..succmax;
stack: array[upindex] of bit;
begin
{ кодирование }
a := plain + succmax;
sp := 1;
repeat { обход снизу вверх дерева и помещение в стек битов }
stack[sp] := ord( right[up[a]] = a );
sp := sp + 1;
a := up[a];
until a = root;
repeat { transmit }
sp := sp - 1;
transmit( stack[sp] );
until sp = 1;
splay( plain );
end { compress };
Для развертывания буквы необходимо читать из архива следующие друг за дру-
гом биты с помощью функции receive. Каждый прочитанный бит задает один шаг на
маршруте обхода дерева от корня к листу, определяющем разворачиваемую букву.
function expand: codetype;
var
a: downindex;
begin
a := root;
repeat { один раз для каждого бита на маршруте }
if receive = 0 then a := left[a]
else a := rignt[a];
until a > maxchar;
splay( a - succmax );
expand := a - succmax;
end { expand };
Процедуры, управляющие сжатием и развертыванием, просты и представляют со-
бой вызов процедуры initialize, за которым следует вызов либо compress, либо
expand для каждой обрабатываемой буквы.
Характеристика алгоритма расширяемого префикса.
На практике, расширяемые деревья, на которых основываются коды префикса,
хоть и не являются оптимальными, но обладают некоторыми полезными качествами.
Прежде всего это скорость выполнения, простой программный код и компактные
структуры данных. Для алгоритма расширяемого префикса требуется только 3 мас-
сива, в то время как для Л-алгоритма Уитерса, вычисляющего оптимальный адапти-
рованный код префикса, - 11 массивов . Предположим, что для обозначения
множества символов исходного текста используется 8 бит на символ, а конец фай-
ла определяется символом, находящимся вне 8-битового предела, maxchar = 256, и
все элементы массива могут содержать от 9 до 10 битов ( 2 байта на большинстве
машин)(3). Неизменные запросы памяти у алгоритма расширяемого префикса состав
ляют приблизительно 9.7К битов (2К байтов на большинстве машин). Подобный под-
ход к хранению массивов в Л-алгоритме требует около 57К битов (10К байтов на
большинстве машин ).
Другие широко применяемые алгоритмы сжатия требуют еще большего простран-
ства, например, Уэлч советует для реализации метода Зива-Лемпела исполь-
зовать хеш-таблицу из 4096 элементов по 20 битов каждый, что в итоге составля-
ет уже 82К битов ( 12К байтов на большинстве машин ). Широко используемая ко-
манда сжатия в системе ЮНИКС Беркли применяет код Зива-Лемпела, основанный на таблице в 64К элементов по крайней мере в 24 бита каждый, что в итоге дает
1572К битов ( 196К байтов на большинстве машин ).
В таблице I показано как Л-алгоритм Уиттера и алгоритм расширяющегося пре-
фикса характеризуются на множестве разнообразных тестовых данных. Во всех слу-
чаях был применен алфавит из 256 отдельных символов, расширенный дополнитель
ным знаком конца файла. Для всех файлов, результат работы Л-алгоритма находит-
ся в пределах 5% от H и обычно составляет 2% от H . Результат работы алгорит-
ма расширяющегося префикса никогда не превышает H больше, чем на 20%, а иног
да бывает много меньше H .
Тестовые данные включают программу на Си (файл 1), две программы на Паска-
ле (файлы 2 и 3) и произвольный текстовый файл (файл 4). Все текстовые файлы
используют множество символов кода ASCII с табуляцией, заменяющей группы
из 8 пробелов в начале, и все пробелы в конце строк. Для всех этих файлов Л-
алгоритм достигает результатов, составляющих примерно 60% от размеров исходно-
го текста, а алгоритм расширения - 70%. Это самый худший случай сжатия, наблю-
даемый при сравнении алгоритмов.
Два объектых файла М68000 были сжаты ( файлы 5 и 6 ) также хорошо, как и
файлы вывода TEX в формате .DVI ( файл 7 ). Они имеют меньшую избыточность
←предыдущая следующая→
1 2 3 4 5 6 7