В качестве структуры хранения информации в словаре выберем сначала простую неупорядоченную таблицу, в которой будет осуществляться линейный поиск. Такую структуру можно будет запросто отладить, хотя она, по-видимому, окажется мучительно неэффективна. Но как только у нас все заработает, можно попытаться ускорить поиск. В каждом гнезде словаря будут четыре поля: цепочка литер, частота гнезда во время построения словаря, кодировка, присвоенная этой цепочке, и счетчик обращений к ней при сжатии текста. Эти поля запоминаются в соответствующих четырех массивах, описанных в строках 66—73 главной программы (вот тут-то начинает давать о себе знать ограниченность структур данных в XPL). Первое полноценное гнездо всегда имеет номер 0, а последнее — DICTIONARY.TOP (вершина словаря). Максимальный размер словаря задает макро DICTIONARY.SIZE (размер словаря). При поиске требуется лишь полный просмотр всех гнезд словаря; новые гнезда могут добавляться в конец таблицы. При исключении низкочастотных гнезд на их место переписываются высокочастотные гнезда; читателю надлежит убедиться самому, что при работе цикла, описанного в строках 261—270, информация не теряется. Ниже программа приведена полностью, причем программы работы со словарем описаны в строках 195—296. Обратите внимание, что вычисление параметров, влияющих на степень сжатия, разнесено по самостоятельным подпрограммам, приведенным в строках 154—193, что позволяет с легкостью их отыскать и заменить. Мы предпочли здесь удобство в ущерб эффективности: в окончательной рабочей версии желательно исключить подпрограммы вычисления параметров, а требуемые функции переписать прямо в тех местах, где они должны использоваться.
Программа была пропущена, а в качестве исходных данных было использовано ее собственное короткое предисловие. Результаты отпечатаны ниже и снабжены номерами строк, чтобы было легче на них ссылаться. В строках 67—71 показана таблица кодировок. При таком коротком текстовом файле нет ничего удивительного, что словарь получился маленьким. Сжатие составляет лишь 0.973 отчасти из-за того, что строки текста в основных комментариях не раздуты за счет тех самых пробелов, которые столь милы сердцу большинства программ сжатия. Тем не менее, имеются некоторые любопытные моменты, о чем свидетельствует строка 62. Обратите внимание, что сжатия «D F» не произошло, поскольку другое сжатие слопало «D» еще раньше. То, что получилось, помещено на следующей странице.
Как предрекалось выше, линейный поиск в словаре не очень-то эффективен. Когда текст всей исходной программы был взят в качестве исходных данных, для его сжатия на машине со средним быстродействием потребовалось 127 с, что страшно долго для файла в 500 строк.
Таблица 30.1. Сравнение двух алгоритмов организации словаря
Заметьте, что, для того чтобы гарантировать при поиске в словаре отыскание самой длинной из цепочек, совпадающих с началом текста на входе, необходимо просмотреть все гнезда словаря. А вот если гнезда словаря расположить в порядке от самых длинных к самым коротким, поиск можно было бы прекратить при первом же удачном сравнении, ибо волей-неволей найденная цепочка была бы самой длинной из всех возможных. Причем процедуру поиска можно было бы не менять, и выбрасывание низкочастотных гнезд не нарушило бы порядок следования цепочек — от длинных к коротким. Однако при заведении нового гнезда необходимо все более короткие цепочки сдвинуть в таблице на одну позицию вниз. Чтобы определить, где производить вставку, мы ввели массив LENGTH.VECTOR (массив длин), i-я компонента которого указывает на гнездо словаря, в котором начинаются цепочки длиной i литер (если таковые есть) или короче (если нет ни одной цепочки длиной i). В случае если цепочки длиной i литер или меньше отсутствуют, значение LENGTH.VECTOR(I) равно значению DICTIONARY.TOP + 1. Программы, приведенные на с. 278—280, обеспечивают правильное хранение новой структуры данных. Чтобы создать новую версию программы сжатия, в соответствующие места нашей программы помещаются вставки, которые приведены ниже. Отметим, что для облегчения этого процесса массив вставок снабжен необходимыми комментариями.
