Если окончание текста источника может быть обнаружено из его контекста, то коды исходного алфавита все находятся в интервале codetype, а максимально воз- можное в этом тексте значение кода будет maxchar. В противном случае, интервал codetype должен быть расширен на один код для описания специального символа "конец файла". Это означает, что maxchar будет на 1 больше значения максималь- ного кода символа исходного текста. Следующая процедура инициализирует дерево кодов. Здесь строится сбаланси- рованное дерево кодов, но на самом деле, каждое начальное дерево будет удовле- творительным до тех пор, пока оно же используется и для сжатия и для разверты- вания.

После того, как каждая буква сжата ( развернута ) с помощью текущей версии дерева кодов, оно должно быть расширено вокруг кода этой буквы. Реализация этой операции показана в следующей процедуре, использующей расширение снизу- вверх:

Чтобы сжать букву исходного текста ее нужно закодировать, используя дере- во кодов, а затем передать. Поскольку процесс кодирования производится при об- ходе дерева от листа к корню, то биты кода записываются в обpатном порядке. Для изменения порядка следования битов процедура compress пpименяет свой стек, биты из которого достаются по одному и передаются процедуре transmit.

Для развертывания буквы необходимо читать из архива следующие друг за дру- гом биты с помощью функции receive. Каждый прочитанный бит задает один шаг на маршруте обхода дерева от корня к листу, определяющем разворачиваемую букву.

Процедуры, управляющие сжатием и развертыванием, просты и представляют со- бой вызов процедуры initialize, за которым следует вызов либо compress, либо expand для каждой обрабатываемой буквы.
Характеристика алгоритма расширяемого префикса.
На практике, расширяемые деревья, на которых основываются коды префикса, хоть и не являются оптимальными, но обладают некоторыми полезными качествами. Прежде всего это скорость выполнения, простой программный код и компактные структуры данных. Для алгоритма расширяемого префикса требуется только 3 мас- сива, в то время как для Л-алгоритма Уитерса, вычисляющего оптимальный адапти- рованный код префикса, - 11 массивов [10]. Предположим, что для обозначения множества символов исходного текста используется 8 бит на символ, а конец фай- ла определяется символом, находящимся вне 8-битового предела, maxchar = 256, и все элементы массива могут содержать от 9 до 10 битов ( 2 байта на большинстве машин)(3). Неизменные запросы памяти у алгоритма расширяемого префикса состав- ляют приблизительно 9.7К битов (2К байтов на большинстве машин). Подобный под- ход к хранению массивов в Л-алгоритме требует около 57К битов (10К байтов на большинстве машин ).
Другие широко применяемые алгоритмы сжатия требуют еще большего простран- ства, например, Уэлч советует для реализации метода Зива-Лемпела [11] исполь- зовать хеш-таблицу из 4096 элементов по 20 битов каждый, что в итоге составля- ет уже 82К битов ( 12К байтов на большинстве машин ). Широко используемая ко- манда сжатия в системе ЮНИКС Беркли применяет код Зива-Лемпела, основанный на таблице в 64К элементов по крайней мере в 24 бита каждый, что в итоге дает 1572К битов ( 196К байтов на большинстве машин ).
В таблица I показано как Л-алгоритм Уиттера и алгоритм расширяющегося пре- фикса характеризуются на множестве разнообразных тестовых данных. Во всех слу- чаях был применен алфавит из 256 отдельных символов, расширенный дополнитель- ным знаком конца файла. Для всех файлов, результат работы Л-алгоритма находит- ся в пределах 5% от H и обычно составляет 2% от H . Результат работы алгорит- ма расширяющегося префикса никогда не превышает H больше, чем на 20%, а иног- да бывает много меньше H .
Тестовые данные включают программу на Си (файл 1), две программы на Паска- ле (файлы 2 и 3) и раннюю редакцию данной статьи (файл 4). Все 4 текстовые фа- йлы используют множество символов кода ASCII с табуляцией, заменяющей группы из 8 пробелов в начале, и все пробелы в конце строк. Для всех этих файлов Л- алгоритм достигает результатов, составляющих примерно 60% от размеров исходно- го текста, а алгоритм расширения - 70%. Это самый худший случай сжатия, наблю- даемый при сравнении алгоритмов.
Два объектых файла М68000 были сжаты ( файлы 5 и 6 ) также хорошо, как и файлы вывода TEX в формате .DVI ( файл 7 ). Они имеют меньшую избыточность, чем текстовые файлы, и поэтому ни один метод сжатия не может сократить их раз- мер достаточно эффективно. Тем не менее, обоим алгоритмам удается успешно сжать данные, причем алгоритм расширения дает результаты, большие результатов работы Л-алгоритма приблизительно на 10%.
Были сжаты три графических файла, содержащие изображения человеческих лиц ( файлы 8, 9 и 10 ). Они содержат различное число точек и реализованы через 16 оттенков серого цвета, причем каждый хранимый байт описывал 1 графическую точ- ку. Для этих файлов результат работы Л-алгоритма составлял приблизительно 40% от первоначального размера файла, когда как алгоритма расширения - только 25% или 60% от H . На первый взгляд это выглядит невозможным, поскольку H есть теоретический информационный минимум, но алгоритм расширения преодолевает его за счет использования марковских характеристик источников.
Последние 3 файла были искусственно созданы для изучения класса источни- ков, где алгоритм расширяемого префикса превосходит ( файлы 11, 12 и 13 ) все остальные. Все они содержат одинаковое количество каждого из 256 кодов симво- лов, поэтому H одинакова для всех 3-х файлов и равна длине строки в битах. Файл 11, где полное множество символов повторяется 64 раза, алгоритм расшире- ния префикса преобразует незначительно лучше по сравнению с H . В файле 12 множество символов повторяется 64 раза, но биты каждого символа обращены, что препятствует расширению совершенствоваться относительно H . Ключевое отличие между этими двумя случаями состоит в том, что в файле 11 следующие друг за другом символы вероятно исходят из одного поддерева кодов, в то время как в файле 12 это маловероятно. В файле 13 множество символов повторяется 7 раз, причем последовательность, образуемая каждым символом после второго повторения множества, увеличивается вдвое. Получается, что файл заканчивается группой из 32 символов "a", за которой следуют 32 символа "b" и т.д. В этом случае алго- ритм расширяемого префикса принимает во внимание длинные последовательности повторяющихся символов, поэтому результат был всего 25% от H , когда как Л-ал- горитм никогда не выделял символ, вдвое более распространенный в тексте отно- сительно других, поэтому на всем протяжении кодирования он использовал коды одинаковой длины.