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

Алгоритм построения словаря

В приводимом алгоритме предполагается, что построение словаря производится с помощью некоторой выборки из текста, подлежащего сжатию. Для алгоритма существенны все литеры текста, и если табуляция, концы строк и другие аналогичные элементы имеют значение, то в тексте должны присутствовать соответствующие управляющие литеры. Предполагается, что в начале работы словарь пуст. В начальный момент переменная last match содержит пустую цепочку, а переменная last count имеет значение, равное нулю.

1. Ищем в головной части входного текста возможно более длинную цепочку match, совпадающую с каким-нибудь гнездом словаря. Если переменная match пустая, засылаем в нее первую литеру входного текста, помещаем в свободное гнездо словаря и устанавливаем начальное значение счетчика этого нового гнезда равным единице. Если цепочка match не пустая, увеличиваем на единицу счетчик соответствующего гнезда словаря. Содержимое счетчика этого гнезда записываем в count.

2. Если либо count, либо last count меньше значения порога укрупнения гнезд, то переходим к шагу 4. Порог укрупнения определяется как отношение максимально допустимого объема словаря к числу оставшихся в данный момент свободных гнезд.

3. Образуем новое гнездо словаря путем объединения цепочек last match и match. Поскольку данное гнездо словаря возникло впервые, засылаем в его счетчик единицу. Можно применить и другие стратегии.

4. Если в словаре остались свободными менее двух гнезд, производим чистку, удаляя все гнезда с частотами меньше медианы частот. При этом, если окажется, что исключилось гнездо, содержащее match, устанавливаем count равным нулю.

5. Вычеркиваем match из начала входного текста. Если текст исчерпан, то алгоритм работу заканчивает — выход. В противном случае помещаем last match в match, пересылаем last count в count и возвращаемся к шагу 1.

Оглавление книги