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

30. Сжатые строки, или... ПРОГРАММА УПЛОТНЕНИЯ ТЕКСТОВ

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

• Насколько сложны алгоритмы, необходимые для выполнения сравнений в словаре, какова сложность структур данных?

• Как долго придется со всем этим возиться?

• Работа алгоритма определяется наборами параметров. Как эти параметры выбрать?

• В какой степени коэффициент сжатия зависит от вариаций в уплотняемом тексте?

• Ради экономии памяти расходуется процессорное время. Когда можно считать, что овчинка стоит выделки?

• Вообразим, что в первой версии программы все уже ясно и она работает правильно, хотя и не очень эффективно. Какие переделки позволят поднять ее производительность?

• Можно ли в исходном проекте предусмотреть возможность внесения изменений и дополнений без больших переделок?

• И наконец, сколько времени стоит потратить на эту задачу, чтобы считать, что она выполнена достаточно хорошо?

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

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

У каждого писателя своя манера подготовки к работе. Некоторым надо протрезветь, а кое-кому выпить, одни встают в 4 утра, другие поднимаются на ночь; некоторым необходима тишина, а другим требуется шумная веселая обстановка, а есть и такие, которые обходятся остроотточенным карандашом и традиционным блокнотом. Программисты — те же писатели, и им требуется найти удобный для себя распорядок и уютную окружающую обстановку. Прежде чем приступить к решению задачи о сжатии текста, хотелось бы предложить несколько рецептов, как сделать процесс программирования более приятным и плодотворным. Нас такая методика вполне устраивает, и вы уж по крайней мере испробуйте ее, прежде чем вернетесь к своей собственной.

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

Многие программисты работают так: набросают на обороте старого конверта несколько строк программы и мчатся к терминалу, чтобы поскорее их набрать и пропустить. А все остальное время занимаются тем, что вставляют в программу там и сям заплатки, и конечный результат их труда смотрится так, словно ужасный доктор Франкенштейн впопыхах прооперировал Шалтая-Болтая. На самом деле, немаловажный вклад в повышение читабельности вносит самодисциплина, одним из способов воспитания которой служат бланки для записи программ. Свободные художники, о которых упоминалось выше, часто с пренебрежением взирают на программистов, которые работают, заполняя клеточки на бланках, и, тем не менее, бланки оказывают сильное стабилизирующее влияние на манеру работы и во много раз облегчают разработку и использование метода ступенчатой записи программ. Кроме того, программу, написанную на бланках, можно отдать на перфорацию. Причем, как ни приятно освободиться от нудной работы, намного важнее, что девушки из перфораторной прочитают программу и проверят правильность пробивки. Поэтому многие описки никогда не попадут в машину, да и лишний глаз — вовсе не помеха.

Теперь о борьбе с предрассудком. Старайтесь писать свои программы чернилами. Большинство институтских преподавателей программирования будет говорить, что не надо бояться допустить ошибку в программе (это-то достаточно справедливо) и что ластик может стать вашим самым мощным инструментом. К несчастью, ластик может оказаться чересчур мощным. Ведь коль скоро ошибки так просто исправить, значит, пока не совершишь очередную, можно особенно тщательно и не думать. В том же случае, когда вы пишете чернилами, ошибки обходятся дороже, в особенности из-за того, что измазанный переправленный бланк могут однажды на пробивку не принять. Из-за никчемных ошибок придется переписывать целую страницу. Неудача вынудит вас писать медленнее и глубже задумываться над каждой строкой; время, потраченное на написание, окупится при тестировании и отладке программы. Даже если у вас есть редактор текстов, который поощряет или навязывает правильный стиль программирования, все равно следует испробовать эти последние две рекомендации. Запись программы необходимо тщательно продумывать, а опыт показывает, что от электрических полей, окружающих терминалы компьютера, в наших мыслях нередко возникают короткие замыкания.

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

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

Эти предложения годятся, очевидно, не для любых программ и не во всех случаях. Многие системы программирования снабжены целым арсеналом средств, помогающих в процессе разработки программ. Пренебрегать этими возможностями было бы глупо и расточительно. Они особенно полезны при создании программ одноразового использования и для контроля хода работ в больших проектах. Однако мы не можем не предостеречь вас самым серьезным образом: машина не должна мешать вам принимать решения. Чарующая песня компьютера «Доверься мне — я все решу» соблазнила многих программистов и привела к крушению их замыслов.

Поскольку оба основных алгоритма (построение словаря и кодирование текста) уже разработаны, нам необходимо рассмотреть теперь, какими вспомогательными программами их надо снабдить. Прежде всего, отметим, что в обоих алгоритмах введенный текст просматривается слева направо и при сравнениях его на совпадение со словарем важны лишь несколько ближайших рядом стоящих литер. Это значит, что как для построения словаря, так и для кодирования можно применить одну и ту же программу ввода и что нам не следует заботиться о деталях доступа к входному потоку, поскольку программа ввода всегда выдает литеры для проведения сравнений или признак конца файла. Во-вторых, в обоих алгоритмах требуется поиск цепочки в словаре, но ни один из алгоритмов не должен зависеть от метода поиска. Поэтому и здесь алгоритмы могут быть снабжены общей обслуживающей программой, и по-прежнему нет необходимости уточнять детали. В-третьих, алгоритму кодирования потребуется хотя бы одна литера, нигде во вводимом тексте не используемая и выступающая в качестве управляющего кодирующего знака. Вместо того чтобы выбрать некую литеру до прочтения текста, можно в программе ввода отслеживать все поступающие на вход литеры и для кодирования употребить любую не встретившуюся. Процедура построения словаря, написанная на XPL, показана на рис. 30.1 [63]

Здесь уместно кое-что пояснить. Процедура написана на XPL — языке, в достаточной степени похожем как на Паскаль, так и на PL/I, так что его легко понять (подтверждение того факта, что разобраться в специализированном языке, как правило, весьма несложно). Применительно к нашей задаче XPL обладает рядом достоинств, в том числе наличием в языке цепочек в качестве встроенного типа данных и удобных управляющих структур. Недостаток языка заключен, в частности, в том, что единственным видом структурированных данных являются одномерные статические массивы.

Язык содержит и редко встречающиеся средства— оператор конкатенации цепочек || и функцию SUBSTR, употребляемую для выделения из имеющейся цепочки подцепочки.[64] Программа ввода FILL.INPUT.BUFFER (заполнение входного буфера) загружает входной буфер, если он оказывается пустым, и выдает пустую цепочку в случае, когда вводимый файл исчерпан. Если вводить больше нечего, происходит выход из программы BUILD.DICTIONARY (построение словаря). Заметим, что сравнить длину цепочки с нулем и проверять, не пустая ли она,— это одно и то же, но в данном случае первое предпочтительнее, поскольку в XPL операция LENGTH весьма эффективна. Посмотрите теперь как выглядит процедура ввода (рис. 30.2).

Программы ввода и вывода используют встроенные функции и всегда читают или печатают цепочки. На самом же деле PRINT (печать) является макрокомандой, внутри которой и скрыта работа вывода. Программа FILL.INPUT.BUFFER при необходимости распечатывает буфер ввода и, кроме того, регистрирует данные о каждой встретившейся литере. Функция BYTE при использовании ее в выражении преобразует выбранную из цепочки литеру в целое число таким образом, чтобы можно было ее использовать в арифметических операциях. В нашем случае литеры употребляются для индексирования логического вектора CHARACTERISED (встречаемость литер), в котором регистрируются все встретившиеся литеры. Кроме того, BYTE употребляется в BUILD.ENCODING.TABLE (формирование таблицы кодировок) для обратного превращения целых чисел в литеры; таким образом, BYTE выполняет те же функции, что и ORD и CHAR в Паскале.

В качестве структуры хранения информации в словаре выберем сначала простую неупорядоченную таблицу, в которой будет осуществляться линейный поиск. Такую структуру можно будет запросто отладить, хотя она, по-видимому, окажется мучительно неэффективна. Но как только у нас все заработает, можно попытаться ускорить поиск. В каждом гнезде словаря будут четыре поля: цепочка литер, частота гнезда во время построения словаря, кодировка, присвоенная этой цепочке, и счетчик обращений к ней при сжатии текста. Эти поля запоминаются в соответствующих четырех массивах, описанных в строках 66—73 главной программы (вот тут-то начинает давать о себе знать ограниченность структур данных в XPL). Первое полноценное гнездо всегда имеет номер 0, а последнее — DICTIONARY.TOP (вершина словаря). Максимальный размер словаря задает макро DICTIONARY.SIZE (размер словаря). При поиске требуется лишь полный просмотр всех гнезд словаря; новые гнезда могут добавляться в конец таблицы. При исключении низкочастотных гнезд на их место переписываются высокочастотные гнезда; читателю надлежит убедиться самому, что при работе цикла, описанного в строках 261—270, информация не теряется. Ниже программа приведена полностью, причем программы работы со словарем описаны в строках 195—296. Обратите внимание, что вычисление параметров, влияющих на степень сжатия, разнесено по самостоятельным подпрограммам, приведенным в строках 154—193, что позволяет с легкостью их отыскать и заменить. Мы предпочли здесь удобство в ущерб эффективности: в окончательной рабочей версии желательно исключить подпрограммы вычисления параметров, а требуемые функции переписать прямо в тех местах, где они должны использоваться.

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

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

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

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

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

Должно быть, эта глава совершенно не похожа на проект, выполненный на пять с плюсом. Над самой программой можно бы было потрудиться и побольше, особенно над комментариями. Немало среди них путаных и бесполезных. В результате напечатанная программа еще на полпути к завершению, и вы можете полюбоваться, на что похожи ваши собственные недоделанные программы. Вернитесь назад и еще раз разберите программу, задаваясь при этом мысленным вопросом: «А как бы можно было вылизать данную строку (комментарий, процедуру), чтобы достичь кристальной ясности?» И после того, как вы, ехидничая по поводу чужих способностей, закончите, посмотрите, положа руку на сердце, нельзя ли ваши рекомендации применить к вашим собственным программам. Желательно, чтобы законченный проект включал в себя также наглядное доказательство правильности алгоритмов, дополнительную печать и хотя бы несколько рекомендаций по повышению эффективности словаря. Составление программы заняло около восьми часов, а отладка — около четырех. Причем из четырех часов отладки два ушло на устранение обычных описок и на наведение красоты печати. Остальные два часа отладки были посвящены тому, чтобы добавить «+1» в 91-ю строку измененного файла. Одна эта маленькая коварная ошибка вызвала массу трудностей и полностью нарушила режим работы программы поиска в упорядоченном словаре. В конце концов, ошибка была обнаружена после того, как мы объяснили всю программу другому программисту. Придерживаясь принципа беспристрастности, он не разделял нашего превратного толкования программы и моментально обнаружил «ляп». Кроме того, около часа было затрачено на вставку и отладку временных переменных (средства подсчета времени в эксплуатирующейся у нас системе развиты в недостаточной степени) и порядка четырех часов на жонглирование параметрами.