Поскольку оба основных алгоритма (построение словаря и кодирование текста) уже разработаны, нам необходимо рассмотреть теперь, какими вспомогательными программами их надо снабдить. Прежде всего, отметим, что в обоих алгоритмах введенный текст просматривается слева направо и при сравнениях его на совпадение со словарем важны лишь несколько ближайших рядом стоящих литер. Это значит, что как для построения словаря, так и для кодирования можно применить одну и ту же программу ввода и что нам не следует заботиться о деталях доступа к входному потоку, поскольку программа ввода всегда выдает литеры для проведения сравнений или признак конца файла. Во-вторых, в обоих алгоритмах требуется поиск цепочки в словаре, но ни один из алгоритмов не должен зависеть от метода поиска. Поэтому и здесь алгоритмы могут быть снабжены общей обслуживающей программой, и по-прежнему нет необходимости уточнять детали. В-третьих, алгоритму кодирования потребуется хотя бы одна литера, нигде во вводимом тексте не используемая и выступающая в качестве управляющего кодирующего знака. Вместо того чтобы выбрать некую литеру до прочтения текста, можно в программе ввода отслеживать все поступающие на вход литеры и для кодирования употребить любую не встретившуюся. Процедура построения словаря, написанная на XPL, показана на рис. 30.1 [63]
Здесь уместно кое-что пояснить. Процедура написана на XPL — языке, в достаточной степени похожем как на Паскаль, так и на PL/I, так что его легко понять (подтверждение того факта, что разобраться в специализированном языке, как правило, весьма несложно). Применительно к нашей задаче XPL обладает рядом достоинств, в том числе наличием в языке цепочек в качестве встроенного типа данных и удобных управляющих структур. Недостаток языка заключен, в частности, в том, что единственным видом структурированных данных являются одномерные статические массивы.
Язык содержит и редко встречающиеся средства— оператор конкатенации цепочек || и функцию SUBSTR, употребляемую для выделения из имеющейся цепочки подцепочки.[64] Программа ввода FILL.INPUT.BUFFER (заполнение входного буфера) загружает входной буфер, если он оказывается пустым, и выдает пустую цепочку в случае, когда вводимый файл исчерпан. Если вводить больше нечего, происходит выход из программы BUILD.DICTIONARY (построение словаря). Заметим, что сравнить длину цепочки с нулем и проверять, не пустая ли она,— это одно и то же, но в данном случае первое предпочтительнее, поскольку в XPL операция LENGTH весьма эффективна. Посмотрите теперь как выглядит процедура ввода (рис. 30.2).
Программы ввода и вывода используют встроенные функции и всегда читают или печатают цепочки. На самом же деле PRINT (печать) является макрокомандой, внутри которой и скрыта работа вывода. Программа FILL.INPUT.BUFFER при необходимости распечатывает буфер ввода и, кроме того, регистрирует данные о каждой встретившейся литере. Функция BYTE при использовании ее в выражении преобразует выбранную из цепочки литеру в целое число таким образом, чтобы можно было ее использовать в арифметических операциях. В нашем случае литеры употребляются для индексирования логического вектора CHARACTERISED (встречаемость литер), в котором регистрируются все встретившиеся литеры. Кроме того, BYTE употребляется в BUILD.ENCODING.TABLE (формирование таблицы кодировок) для обратного превращения целых чисел в литеры; таким образом, BYTE выполняет те же функции, что и ORD и CHAR в Паскале.
В качестве структуры хранения информации в словаре выберем сначала простую неупорядоченную таблицу, в которой будет осуществляться линейный поиск. Такую структуру можно будет запросто отладить, хотя она, по-видимому, окажется мучительно неэффективна. Но как только у нас все заработает, можно попытаться ускорить поиск. В каждом гнезде словаря будут четыре поля: цепочка литер, частота гнезда во время построения словаря, кодировка, присвоенная этой цепочке, и счетчик обращений к ней при сжатии текста. Эти поля запоминаются в соответствующих четырех массивах, описанных в строках 66—73 главной программы (вот тут-то начинает давать о себе знать ограниченность структур данных в XPL). Первое полноценное гнездо всегда имеет номер 0, а последнее — DICTIONARY.TOP (вершина словаря). Максимальный размер словаря задает макро DICTIONARY.SIZE (размер словаря). При поиске требуется лишь полный просмотр всех гнезд словаря; новые гнезда могут добавляться в конец таблицы. При исключении низкочастотных гнезд на их место переписываются высокочастотные гнезда; читателю надлежит убедиться самому, что при работе цикла, описанного в строках 261—270, информация не теряется. Ниже программа приведена полностью, причем программы работы со словарем описаны в строках 195—296. Обратите внимание, что вычисление параметров, влияющих на степень сжатия, разнесено по самостоятельным подпрограммам, приведенным в строках 154—193, что позволяет с легкостью их отыскать и заменить. Мы предпочли здесь удобство в ущерб эффективности: в окончательной рабочей версии желательно исключить подпрограммы вычисления параметров, а требуемые функции переписать прямо в тех местах, где они должны использоваться.
63
Номера строк в этой процедуре те же, что и в полной программе, приведенной на стр. 265—275 (см.ниже)
64
Если переменная V — цепочка или выражение, тогда SUBSTR (V, S, L) есть подцепочка V, начинающаяся с S-й литеры (первая литера цепочки имеет номер нуль) и содержащая L байтов. Если аргумент L опущен, будет выдан весь остаток цепочки V, начиная с S-й позиции. Функция LENGTH выдает в качестве значения число литер в аргументе. В строке 332 процедуры BUILD.DICTIONARY используется SUBSTR вместе с LENGTH для того, чтобы исключить сличенную цепочку MATCH из начала INPUT.BUFFER (буфер ввода).