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

просмотр. После того как частоты встречаемости гнезд словаря стабилизируются, вводим таблицу кодировок и, взяв исходный текст, полностью его кодируем.

В предложенной схеме есть два невыясненных момента: каким образом происходит укрупнение гнезд словаря и как осуществляется его чистка? Укрупнение двух гнезд словаря производится в случае, когда одно из них следует в тексте непосредственно за другим и частоты обоих гнезд превышают некоторое пороговое значение. При этом, чтобы новое гнездо словаря не подвергалось ближайшей чистке, ему может быть приписана начальная частота несколько выше обычной. Таким образом, если в словаре уже имеются, например, цепочки КОН и ТАКТ, то при условии, что содержимое их счетчиков достаточно велико, может образоваться новое гнездо словаря, содержащее цепочку КОНТАКТ. Что лее касается чистки словаря, то существует простой способ — удалять все те гнезда, значения счетчиков которых меньше среднего. Можно действовать и иначе — выбрасывать все гнезда, частота которых ниже медианы частот. Годятся и другие, подобные этому способы.

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

В приводимом алгоритме предполагается, что построение словаря производится с помощью некоторой выборки из текста, подлежащего сжатию. Для алгоритма существенны все литеры текста, и если табуляция, концы строк и другие аналогичные элементы имеют значение, то в тексте должны присутствовать соответствующие управляющие литеры. Предполагается, что в начале работы словарь пуст. В начальный момент переменная 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.

Кодирование и декодирование

Как только построение словаря завершилось, необходимо составить таблицы для кодирования и декодирования. Образуем все возможные диграфы, начинающиеся с литеры, которая нигде в тексте не используется. Исключим из словаря все гнезда, состоящие из одной или двух литер (их уплотнение экономии дать не может). Упорядочим оставшиеся цепочки по частоте встречаемости. Поставим в соответствие гнездам словаря полученные выше кодирующее диграфы, начиная с гнезд, имеющих наибольшую частоту. Формирование таблицы кодировок завершается по исчерпании гнезд словаря или набора диграфов.

Процесс кодирования текста подобен процедуре построения словаря. На каждом этапе головная часть входного текста проверяется на совпадение в возможно большем числе позиций с гнездами словаря. Совпавшая цепочка заменяется в тексте соответствующим кодирующим диграфом, и начало просмотра входного текста сдвигается на длину выделенной цепочки. Если же в словаре не найдено нужного гнезда, в выходной текст просто переносится первая литера из головной части входного текста и начало просмотра перемещается вправо на одну позицию. Декодирование осуществляется путем простой замены кодирующих диграфов их эквивалентами из словаря.

Тема. Напишите программу, реализующую описанные выше алгоритмы построения словаря, кодирования и декодирования. Проверьте программу на достаточно больших фрагментах текста на естественном языке и языке программирования. Коэффициент сжатия данного куска текста определяется как частное от деления суммы длин сжатого текста и словаря на дайну исходного текста. Проведите небольшое исследование зависимости коэффициента сжатия от какого-нибудь из следующих параметров: языка уплотняемого текста; объема используемой для упражнения выборки из текста; длины словаря при его построении; имеющегося количества кодирующих диграфов или применимости словаря, полученного на основании одного текста, для другого текста на том же языке.

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

Другим примером является выбор структуры словаря на этапах его создания и кодирования. Если гнезда словаря расположить в случайном порядке, то при проверках на совпадение необходимо проходить весь словарь. Однако при такой структуре появляющиеся новые гнезда добавляются просто в конец словаря. Небольшое усложнение могло бы заключаться в группировке гнезд словаря по их длинам. Тогда поиск мог бы осуществляться в направлении от самых длинных групп к коротким и прекращаться при первом же удачном сравнении. Если каждую группу еще и лексикографически упорядочить, то можно было бы воспользоваться вместо линейного поиска внутри группы двоичным поискам, экономя таким образом время. Но зато добавление в словарь новых гнезд становится в этом случае более сложным, так как для любого нового гнезда потребуется место, скорее всего, где-то в середине группы. Не исключено, что самой выгодной структурой для организации поиска окажется какая-либо разновидность дерева. Разыскиваемую цепочку словаря могла бы тогда составить последовательность букв по пути от корня дерева к его листьям, или, иначе говоря, в узлах некоего подобия двоичного дерева поиска могли бы располагаться соответствующие строки словаря. В то же время при составлении словаря деревья потребуют намного большей обработки, нежели описанные выше более простые структуры.

Инструментовка. Вследствие разнообразия структур данных, используемых в готовой программе, исходный язык должен обладать хорошими средствами описания данных. В этом плане можно рекомендовать Паскаль, Алгол-68 и PL/I. Можно было бы предложить сначала написать программу на Сноболе, опираясь на заложенные в этом языке средства сопоставления с образцом, а затем переписать готовую программу на каком-нибудь более эффективном при массовых расчетах языке. При использовании этого пути необходимо быть внимательными и избегать употребления таких средств Снобола, которые трудно воспроизвести на другом языке.

Длительность исполнения. Одному исполнителю на 3 недели.

Развитие темы. В описанной модели имеются три области свободы: критерий укрупнения гнезд, критерий исключения низкочастотных гнезд словаря и система их кодирования. Рассматривая их по-порядку, начнем с критерия укрупнения гнезд. Для того чтобы могло произойти