Этюды для программистов

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

Выбор параметров

Конструированием словаря управляют четыре параметра: размер словаря, порог укрупнения гнезд, начальное значение счетчика укрупненных гнезд и порог исключения гнезд. Выбор, который мы сделали, может показаться несколько странным. Размер словаря определяет макро DICTIONARY.SIZE и задается в нашем случае равным 100 (не забудьте, что массивы в XPL начинаются с нулевого индекса), а начальное значение счетчика в гнезде — посредством функции FIRST.COUNT. (начальный счетчик)— устанавливается равным единице. Укрупнение гнезд производится в случае, когда каждое из них имеет частоту не меньше, чем DICTIONARY.SIZE/(DICTIONARY.SIZE — DICTIONARY.TOP + 1) + 1, т. е. когда частоты обоих гнезд больше величины, обратно пропорциональной свободному пространству словаря. При этом мы исходили из представления (которое не слишком-то хорошо себя оправдало), что, когда словарь почти заполнен, записать новое гнездо должно быть труднее. Исходя из вида приведенного выражения, мы называем порог укрупнения гнезд завышенным порогом укрупнения. Исключение гнезд осуществляется в случае, если их частоты по крайней мере не больше средней частоты,— предполагается, что она является приближенным значением медианы. Чтобы установить, в какой степени такой выбор параметров действительно необоснован, изменим каждый из них, кроме размера словаря, и положим их значение равным пяти.

Таблица 30.2. Небольшое исследование влияния параметров

В табл. 30.2 отражены результаты обработки обоих файлов. Из таблицы видно, что как порог укрупнения, так и порог исключения оказались неудачными. Вполне возможно, что завышенный порог укрупнения не позволяет объединить и поместить в таблицу достаточное число укрупненных гнезд и, кроме того, быть может, средняя частота, взятая в качестве порога исключения, является плохим приближением медианы, что приводит к ликвидации слишком большого числа гнезд. Все это — лишь очень поверхностное исследование, и надо бы собрать еще дополнительный материал. Однако нас заест тоска раньше, чем программа станет более эффективной.

Заключительные замечания