Программа была пропущена, а в качестве исходных данных было использовано ее собственное короткое предисловие. Результаты отпечатаны ниже и снабжены номерами строк, чтобы было легче на них ссылаться. В строках 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, обеспечивают правильное хранение новой структуры данных. Чтобы создать новую версию программы сжатия, в соответствующие места нашей программы помещаются вставки, которые приведены ниже. Отметим, что для облегчения этого процесса массив вставок снабжен необходимыми комментариями.
Можно рассчитывать, что при использовании поиска до первого совпадения во время построения словаря сравнений будет меньше, а более сложная процедура добавления новых гнезд может занять при этом большее время. Тем не менее, из табл. 30.1 видно, что, несмотря на меньшее число сравнений при поиске в упорядоченном словаре, как время построения словаря, так и время кодирования текста увеличивается. Следует, однако, отметить, что для сравнений в первоначальной программе можно обойтись лишь дешевыми проверками длин цепочек, в то время как при поиске в упорядоченном словаре все сравнения требуют дорогих операций сопоставления цепочек. Чтобы повысить эффективность программы, надо бы, конечно, что-то предпринять. Но с другой стороны, проведенная переделка программы иллюстрирует важный принцип отладки. Если структура программы заменяется на функционально эквивалентную, то результаты при тех же исходных данных должны оставаться неизменными. На фактический процесс сжатия организация словаря влиять не должна, только параметры сжатия должны сказываться на содержании словаря. Следовательно, убеждаясь, что результаты работы программы с простым линейным поиском и с поиском до первого совпадения совершенно одинаковы (за исключением временной статистики), мы проверяем правильность изменений в подпрограммах, оперирующих со словарем. Это является также контролем на отсутствие ошибок в других частях программы: если бы в какой-нибудь другой подпрограмме был ляпсус, то он вполне мог бы проявиться в программах работы со словарем. А если уж результаты остаются постоянными после того, как подключается правильная программа поиска до первого совпадения, не исключено (но вовсе и не обязательно), что скрытых ошибок, влияющих на словарь, нет.