Можно, однако, для каждого гнезда иметь свой порог. В другом варианте может быть у одного гнезда постоянный порог, а у другого — порог, являющийся функцией средней частоты гнезд. Аналогично может варьироваться начальная частота укрупненного гнезда, причем при любом способе начальная частота задается большой исходя из условия повышения шансов на сохранение данного гнезда при чистке.
Точно так же может быть видоизменен образ действий при исключении гнезд словаря во время его чистки. Можно выбрасывать неизменную часть низкочастотных гнезд (используя медиану, устанавливающую эту часть равной половине). Можно исключать все гнезда с частотами, меньшими некоторой, кратной средней частоте. Или же можно вычеркивать все гнезда с частотами, меньшими заданной, и эту процедуру осуществлять до тех пор, пока словарь не будет достаточно вычищен. Сочетание различных способов укрупнения и чистки гнезд характеризуется особым показателем исключаемости. В некоторых вариантах оставляются цепочки, которые часто встречаются в одной части текста и реже в других; в иных случаях предпочтение отдается цепочкам, равномерно разбросанным по тексту. Какому показателю исключаемости отдать предпочтение, зависит от используемых особенностей как словаря, так и текста.
В алгоритме кодирования употребляются диграфы, начинающиеся с не используемых во входном тексте литер. Однако, если набор диграфов кончился, а словарь еще не доделан, можно использовать триграфы и т. д. Коль скоро частоты гнезд словаря известны, их можно употребить для организации взвешенного кодирования переменной длины. Этот способ будет дороже при декодировании (почему не при кодировании?), зато обеспечит даже более высокую степень сжатия текста.
Литература
Мэйн, Джеймс (Маупе A., James Е. В.). Information Compression by Factorising Common Strings. Comput. J., 18, 2, pp. 157–160, 1975.
Этот этюд представляет собой в основном переформулировку работы Мэйна и Джеймса. Надо заметить, что наш алгоритм более прозрачен, а их работа содержит ряд существенных результатов.
Кнут (Knuth D. E.). The Art of Computer Programming, Volume 3/Sorting and Searching. Addison-Wesley, Reading, MA, 1973. [Имеется перевод: Кнут Д. Искусство программирования для ЭВМ, Т. 3. Сортировка и поиск. — M.i Мир, 1978.]
Хотя чтение любой части книги Кнута доставляет массу удовольствия, представляется, что обсуждаемому вопросу наиболее соответствует материал разд. 6.2 о дереве поиска.
