Препроцессинг текстов

В последние несколько лет приобрели популярность и были существен­но развиты методы предварительной обработки текстовой информации. В настоящее время специализированный препроцессинг текстов, позво­ляющий заметно улучшить сжатие, используется в таких архиваторах, как ARHANGEL, JAR, RK, SBC, UHARC, в компрессорах DC, PPMN.

Использование словарей

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

Можно выделить несколько стратегий построения словаря. По способу построения словари бывают:

■ статическими, т. е. заранее построенными и полностью известными как препроцессору, так и постпроцессору;

■ полуадаптивными, когда словарь выбирается из нескольких заранее сконструированных и известных препроцессору и постпроцессору или достраивается, при этом один из имеющихся словарей берется за основу;

■ адаптивными, т. е. целиком создаваемыми специально для сжимаемого файла (блока) данных на основании его анализа.

В качестве фраз обычно используются [4]:

■ целые слова;

■ последовательности из двух символов (биграфы);

■ пары букв, фонетически эквивалентных одному звуку;

■ пары букв согласная - гласная или гласная - согласная;

■ последовательности из и символов (и-графы).

Как правило, существует огромное количество последовательностей, ко­торые в принципе могут стать фразами, поэтому необходимо применять ка­кие-то критерии отбора. Обычно в словарь добавляются:

■ последовательности, чаще всего встречающиеся в сжимаемом тексте или в текстах определенного класса;

■ одни из самых часто используемых последовательностей, удовлетворяю­щие некоторым ограничениям;

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

Словарь п-графов

Судя по всему, наибольшее распространение в современных архивато­рах и компрессорах получила стратегия статического словаря, состоящего из последовательностей букв длины от 2 до небольшого числа п (обычно 4-5). В большинстве случаев размер словаря равен примерно 100 таким фра­зам. К достоинствам данного типа словаря можно отнести:

■ малый размер;

• отсутствие жесткой привязки к определенному языку;

■ обеспечение существенного прироста степени сжатия;

■ простота реализации.

Небольшой размер словаря обусловлен двумя причинами:

■ это упрощает кодирование фраз словаря;

■ дальнейшее увеличение размера словаря улучшает сжатие лишь незна­чительно (справедливо для BWT и в меньшей степени для LZ) либо даже вредит в большинстве случаев (справедливо для РРМ).

Обычно тексты представлены в формате "plain text", когда 1 байт соот­ветствует одному символу. Так как размер словаря мал, то в качестве ин­декса фраз выступают неиспользуемые или редко используемые значения байтов. Например, если обрабатывается текст на английском языке, то по­явление не-ASCII байтов со значением 0x80 и больше маловероятно. По­этому мы можем заместить все биграфы "th" на число 0x80. Если байт 0x80 все же встретится в обрабатываемых данных, то он может быть передан как пара (<флаг исключения^ <0х80>), где флаг исключения может быть равен, например, OxFF. Это обеспечивает однозначность восстановления текста постпроцессором.

Упражнение. Каким образом будет передан байт, равный самому флагу ис­ключения?

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

Например, для английского языка хорошо работает словарь, представ­ленный в табл. 7.1. В него входят 45 последовательностей длины 2 (бигра-фов), 25 последовательностей длины 3 (триграфов) и 16 последовательно­стей длины 4 (тетраграфов). Список отсортирован в примерном порядке убывания полезности фраз (внутри каждой группы л-графов - слева направо и сверху вниз).

Таблица 7.1

Биграфы	Триграфы	Тетраграфы
th er in ou an en	the ing and	ight self
еа or 11 is on ar	for ess ver	ward this
st gh ed ее от oo	was igh ous	have been
ow ss ur Id at sh	our eil een	able nder
id sa ic tr al it	had ich ugh	ttle with
as ir ec ul ly et -	her out his	ound reat
ai ch ot it av im	ead ard ome	that what
ol to qu	est ght rom	fromther
	ith

Пример

Строка

he took his vorpal sword in hand

будет преобразована в последовательность:

he <to>ok <his> v<or>p<al> sw<or>d <in> h<and>

В угловых скобках показаны я-графы, заменяемые на их индекс в словаре.

Сначала отображаются тетраграфы (в разбираемой строке их нет), затем триграфы и в самую последнюю очередь биграфы.

Рассмотрим пример реализации простейшей словарной замены для анг­лийских текстов. Пусть словарь состоит только из 10 биграфов, в качестве кодов биграфов используются не-ASCII байты со значениями 128-137, ис­ключительные ситуации не отслеживаются, т. е. предполагается, что во входном файле отсутствуют не-ASCII символы.

const int BIGRAPH_NUM = 10;

const char blist [BIGRAPH_NUM][3] = {

"th", "er", "in", "ou", "an",

"en", "ea", "or", "ll", "is" }; /♦предполагаем, что bnum - глобальная переменная и

инициализируется нулями; в этом массиве будем хранить коды

биграфов */ unsigned char bnum [256][256];

int code = 128;

for (int i = 0; i < BIGRAPHNUM; i++){ //заполним bnum

bnum [ blist[i][0] ] [ blist[i][l] ] = code++;

}

int cl, c2;

cl = DataFile.ReadSymbol();

while ( cl != EOF ) {

c2 = DataFile.ReadSymbol(); if ( c2 == EOF ) {

PreprocFile.WriteSymbol (cl); break; }

if (bnum[cl][c2]){

//такой биграф имеется в словаре, произведем замену PreprocFile.WriteSymbol (bnum[cl][c2]); cl = DataFile.ReadSymbol(); }else{

PreprocFile.WriteSymbol (cl); cl = c2; } }

Для русского языка неплохие результаты показывает словарь, описан­ный в табл. 7.2. Заметим, что словарь для русских текстов имеет меньший размер, чем для английских.

Таблица 7.2

Биграфы	Триграфы	Тетраграфы
то ст ов ен по аз ак ер ол ор	ств был при	лько врем
он ел ет ам от ом ас ан ин ск	про ере ого	тобы огда
на за ар ик пр ев ив ит ил ед	ост ись енн	азал олып
ем ть ал ат ав ся ее об од ос	вет	еред отор
ис ог им ег ич сь

За счет описанной словарной замены достигается значительное улучше­ние сжатия текстов (табл. 7.3). В качестве тестового файла был использован роман на английском языке "Three men in a boat (to say nothing of the dog)" ("Трое в лодке, не считая собаки"), электронный вариант которого занимал около 360 Кб в исходном виде. Отказ от сравнения с помощью больших текстовых файлов Bookl и Воок2, входящих в состав стандартного набора CalgCC, был обусловлен тем, что они являются не вполне типичными тек­стами. Первый файл содержит значительное количество опечаток, а вто­рой - большой объем служебной информации о форматировании текста.

Таблица 7.3

Архиватор	Тип метода сжатия	Размер архива исходного . файла, байт	Размер архива обработанного файла	Улучшение сжатия %
Bzip2, вер. 1.00	BWT	109736	107904	1.7
WinRAR, вер. 2.71	LZ77	130174	126026	3.2
НАа2, вер. 0.999с	РРМ	108443	106831	1.5

Заметим, что в случае Bzip2 и НА сжатие могло быть улучшено. С одной стороны, коэффициент сжатия алгоритма BWT зависит от номеров симво­лов в алфавите, а нами не делалось никаких попыток переупорядочить бо­лее подходящим образом ASCII-символы и номера добавленных нами фраз. С другой стороны, НА использует небольшой объем памяти и часть накап­ливаемой в РРМ-модели статистики периодически выбрасывается, что ухудшает предсказание и, соответственно, сжатие.

Эффективность использования и-графового словаря с другим составом фраз совместно с BWT архиваторами оценена в [2].

Обычно применение и-графового словаря улучшает сжатие компрессо­ров, использующих РРМ или BWT, на 2%.

Степень сжатия компрессоров на базе методов Зива - Лемпела может быть заметно улучшена за счет увеличения размера словаря препроцессора и использования фраз большей длины. В принципе фразы могут включать не только буквы, но и пробелы, что, кстати, приводит к ухудшению сжатия в случае BWT или РРМ.

Словарь LIPT

В качестве примера словаря, в котором фразами являются слова, рас­смотрим схему Length Index Preserving Transformation (LIPT) - преобразова­ние с сохранением индекса длины [1]. В словарь включаются самые часто используемые слова, определяемые исходя из анализа большого количества текстов на заданном языке и, возможно, определенной тематики. Под сло­вом здесь понимается последовательность букв, ограниченная с двух сторон символами, не являющимися буквами ("не-букв"). Весь словарь делится на части (подсловари). В зависимости от своей длины L, слово попадает в часть словаря с номером i. В пределах подсловаря фразы отсортированы в поряд­ке убывания частоты, т. е. самое часто используемое слово имеет мини­мальный индекс 0. Каждое слово исходной последовательности, которому соответствует какая-та фраза словаря, кодируется следующим образом:

флаг

длина слова (номер подсловаря)

индекс в подсловаре

В качестве алфавита для записи длины слова и индекса авторами алго­ритма предлагается использовать алфавит языка. Например, если мы рабо­таем с английским языком, то "а" соответствует 1, "Ь" - 2, ..., "z" - 26, "А" -27, ..., "Z" - 52 и далее "аа" - 53, "ab" - 54... Нулевой индекс явным обра­зом не передается. Если, допустим, слово "mere" имеет индекс 29 в своем подсловаре 4, то оно будем преобразовано так (для большей доходчивости различные части кода фразы выделены подчеркиванием):

"mere" -> "<флаг^_С". Если индекс равен 56, то отображение будет таким:

"mere" -» "<фла1>_<1_а<Г.

Индекс указан как "ad", поскольку он записывается в позиционной системе счисления и первая буква соответствует старшему порядку. Конец последо­вательности, передающей индекс, нет нужды указывать явно, поскольку ес­ли мы рассматриваем "mere" как слово, то оно должно ограничиваться ка­кой-то "не-буквой", которая и станет маркером конца записи индекса.

Если слово отсутствует в словаре, то оно без изменений копируется в файл преобразованных данных.

Эксперименты показывают, что для различных алгоритмов сжатия вы­годнее использовать разные алфавиты длины слова и индекса. Также иногда имеет смысл использовать иной принцип разбиения словаря. Рассмотрим результаты сжатия текста "Three men in a boat (to say nothing of the dog)" для следующих трех алгоритмов LIPT:

1) алгоритма 1 - практически соответствует авторскому, но алфавит огра­ничен только строчными английскими буквами;

2) алгоритма 2 - алфавиты длины слова и индекса отличаются от алфа­вита букв и не пересекаются между собой;

3) алгоритма 3 - словарь разбивается на подсловари не только по крите­рию длины фраз, но и по соответствию слова определенной части ре­чи¹; используются такие же алфавиты, что и в алгоритме 3.

Словарь LIPT был построен на основании анализа примерно 50 Мб анг­
лийских текстов различного характера. Общий объем словаря составил око­
ло S3 тыс. фраз, или 480 Кб. Для реализации алгоритма 3 примерно 11.6 ты­
сяч. слов был присвоен атрибут принадлежности к определенной части ре­
чи, например "the" - артикль и т. д. Классификация была очень груба -
использовалось всего лишь 9 категорий. Если слово могло относиться к не­
скольким частям речи, то выбиралась самая часто употребляемая форма
(понятно, здесь был определенный произвол). Слова, не получившие такого
лексического атрибута, трактовались как существительные. Схема кодиро-
вания для алгоритма 3 имела вид:______

флаг

часть речи

длина слова

индекс в подсловаре

Например:

"теге" -> "<флагХприлагательноехдлина = 4хиндекс>", где индекс определяет положение фразы в подсловаре 4-буквенных прила­гательных.

Результаты эксперимента приведены в табл. 7.4.

Таблица 7.4

Архива­тор	Тип мето­да сжа­тия	Алгоритм LIPT 1		Алгоритм LIPT 2		Алгоритм LIPT 3
		Размер архива, байт	Улуч­шение сжатия	Размер архива, байт	Улуч­шение сжатия	Размер архива, байт	Улуч­шение сжатия, %
Bzip2, вер. 1.00	BWT	102797	6.3	100106	8.8	101397	7.6
WinRAR, вер. 2.71	LZ77	118647	8.9	122118	6.2	125725	3.4
НАа2, вер. 0.999с	РРМ	100342	7.5	98838	8.9	98173	9.5

Таким образом, для LZ77 лучше всего подходит обычный алгоритм LIPT. Очевидно, что LZ77 плохо использует корреляцию между строками и основной выигрыш достигается за счет уменьшения длин совпадения и ве­личин смещений. Алгоритм 2 можно признать компромиссным вариантом. Для РРМ-компрессоров имеет смысл использовать алгоритм 3.

Преобразование заглавных букв

Заглавные буквы существенно увеличивают число встречающихся в тек­сте последовательностей и, соответственно, приводят к ухудшению сжатия по сравнению с тем случаем, если бы их не было вообще. Способ частично­го устранения этого неприятного явления очевиден. Если слово начинается с заглавной буквы, то будем преобразовывать его так, как показано на рис. 7.1 [2].

флаг

первая буква, преобразованная в строчную

оставшаяся часть слова

Рис. 7.1. Преобразованный вид слова, начинавшегося с заглавной буквы

При этом под словом понимается последовательность букв, ограничен­ная с двух сторон "не-буквами".

Например, если в качестве флага используется байт 0x00, то преобразо­вание может иметь вид:

"_Если_" ■> "_<0х00>если_"

Для BWT- и РРМ-компрессоров отмечается улучшение сжатия, если по­сле флага вставляется пробел, т. е. когда результат преобразования имеет вид типа "_<0х00>_если_". Невыгодно преобразовывать слова, состоящие только из одной заглавной буквы.

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

флаг 2 последовательность букв слова, преобразованных в строчные

Если в роли флага 2 выступает байт 0x01, то справедлив такой пример отображения:

"_АЛГОРИТМЫ_" -> "_<0х01>алгоритмы_".

Как уже указывалось, добавление пробела после флагов улучшает сжа­тие BWT- и РРМ-компрессоров.

Может показаться, что описанный алгоритм вносит избыточность за счет использования флага даже в тех случаях, когда в нем нет особой необходи­мости. Если текущее слово является первым встреченным после точки, вос­клицательного или вопросительного знака, то его начальная буква наверня­ка является заглавной и флаг излишен. Естественно, для обеспечения пра­вильности декодирования необходимо одно из двух:

■ особо обрабатывать ситуации, когда первая буква все-таки строчная, на­пример использовать специальный флаг, сигнализирующий об исключении;

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

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

В табл. 7.5 описывается эффект от использования преобразования за­главных букв для архиваторов различных типов на примере сжатия уже упоминавшегося электронного варианта книги "Three men in a boat (to say nothing of the dog)".

Чтобы продемонстрировать роль вставки пробела после флагов, мы рас­смотрели два алгоритма предварительной обработки. Алгоритм 1 преобразует:

■ слова, начинающиеся с заглавной буквы, но далее состоящие из одной или
более строчных, в соответствии с правилом, изображенным на рис. 7.1;

* слова из двух и более символов, содержащие только заглавные буквы, в соответствии с правилом, приведенным на рис. 7.2.

Алгоритм 2 использует эти же два отображения, но добавляет после фла­гов пробел.

Таблица 7.5

Архиватор	Тип метода сжатия	Алгоритм 1		Алгоритм 2
		Размер архива, байт	Улучшение сжатия, %	Размер архива, байт	Улучшение сжатия, %
Bzip2, вер. 1.00	BWT	108883	0.8%	108600	1.0%
WinRAR, вер. 2.71	LZ77	128351	1.4%	128563	1.2%
НА а2, вер. 0.999с	РРМ	107285	1.1%	107137	1.2%

Добавление пробела заметно улучшило сжатие для алгоритма BWT, бла­гоприятно повлияло на эффективность РРМ, но сказалось отрицательно в случае LZ77.

Модификация разделителей

Текст содержит не только буквы, но и символы-разделители. Разделите­ли бывают:

■ естественными - это знаки препинания, пробелы;

■ связанными с форматированием текста - символы конца строки (СКС), символы табуляции.

Символы-разделители в большинстве случаев плохо предсказываются на основании контекстно-зависимой статистики. Особенно плохо предсказы­ваются символы конца строки, т. е. пара символов {перевод каретки, пере­вод строки} CR/LF или символ перевода строки LF.

Коэффициент сжатия BWT- и РРМ-компрессоров может быть улучшен, если преобразовать знаки препинания и СКС, выделив их из потока букв. Наиболее эффективным и простым способом модификации является добав­ление пробела перед этими разделителями [2]. Например:

"очевидно," -> "очевидно_,",

при этом:

"очевидно_," -> "очевидно ,".

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

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

■ уменьшается количество используемых контекстов и, следовательно, увеличивается точность накапливаемой статистики;

■ пробел сжимается часто сильнее, чем соответствующий знак препинания или СКС, и при этом предоставляет несколько лучший с точки зрения точности предсказания контекст для последующего разделителя. Укажем несколько способов повышения производительности схемы:

■ в случае СКС пробел в большинстве случае выгодно добавлять и после символа (-ов) конца строки; при этом лучше воздержаться от преобразо­вания, если первый символ новой строки не является ни буквой, ни про­белом;

■ сжатие обычно улучшается в среднем, если не делается преобразование знаков препинания, за которыми не следует ни пробел, ни СКС;

■ не следует вставлять пробел перед знаком препинания, если предыду­щий символ не является ни буквой, ни пробелом.

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

В целом эффект от модификации разделителей менее стабилен, чем от сло­варной замены или перевода заглавных букв в строчные. Выигрыш практиче­ски всегда достигается главным образом за счет преобразования СКС и состав­ляет 1-2 %. В случае BWT преобразование знаков препинания дает неустойчи­вый эффект, лучше обрабатывать таким образом только СКС.

Результаты сжатия различными архиваторами преобразованного текста книги "Three men in a boat (to say nothing of the dog)" приведены в табл. 7.6.

Таблица 7.6

Архиватор	Тип метода сжатия	Размер архива обработанного файла, байт	Улучшение сжатия, %
Bzip2, вер. 1.00	BWT	108864	0.8
WinRAR, вер. 2.71	LZ77	130835	-0.5
НА а2, вер. 0.999с	РРМ	106582	1.7

Данные табл. 7.6 подтверждают, что использование описанного преобра­зования в сочетании с методов LZ77 бессмысленно.

Специальное кодирование символов конца строки

Как уже отмечалось, СКС плохо сжимаются сами и ухудшают сжатие окружающих их символов.

Очевидно, что если бы мы заменили СКС на пробелы, то сжатие текстов улучшилось бы существенным образом. Этого можно достигнуть, искусст­венно разбив исходный файл на два блока: собственно текст, в котором СКС заменены на пробелы, и сведения о расположении СКС в файле, т. е. фактически информация о длинах строк. Если в расположении СКС имеется достаточно строгая регулярность, то сумма размеров сжатого блока преоб­разованного текста и сжатого блока длин строк будет меньше размера архи­ва исходного файла [2].

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

Одним из возможных способов задания длины строки является количе­ство пробелов, лежащих между предыдущим и текущим СКС. Например:

Строка	Длина строки в пробелах
Twas_brill»g,_and_the_slithy_toves	5
Did_gyre_and_gimble_in_the_wabe;	6
All_mimsy_were_the_borogoves,	4
And_the_mome_raths_outgrabe.	4

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

Постпроцессор получит два блока данных:

Блок	Данные блока /
Текст	Twas_brillig,_and_the_slithy_toves_ \ Did_gyre_and_gimble_in_the_wabe;_ All_mimsy_...
Длины строк	5,6,...

Так как постпроцессору известно, что первая строка содержит 5 пробе­лов, то он заменит 6-й по счету пробел на СКС:

"...toves_Did..." -> "...toves<CKODid..."

Для следующей строки он заменит на СКС 7-й пробел и т. д. Таким образом текст будет полностью реконструирован.

Укажем несколько способов повышения степени сжатия.

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

Эксперименты показывают, что можно заменять на пробелы не все СКС, а только соответствующие достаточно длинным строкам. Зачастую это спо­собствует повышению общей степени сжатия. При этом, однако, появляется проблема определения, при каких же именно длинах строк выгодно "запус­кать" преобразование. В компрессоре PPMN используется следующий спо­соб нахождения порога, при превышении которого длиной L строки вклю­чается преобразование СКС. Величина L принимается за постоянную на протяжении обработки всего файла. Для вычисления L анализируется дос­таточно большой блок (до 32 Кб) исходного файла и собирается информа­ция о количестве (частоте) строк с определенной длиной L, измеряемой в символах. В подавляющем большинстве случаев частоты длин строк мак­симальны в районе наибольшей наблюдаемой длины Z,_ma=t строк, а затем достаточно резко падают с уменьшением L. Поэтому, двигаясь от L_m(tt к нуле­вой длине, находим сначала максимум частоты, а затем, продолжая умень­шать L, ищем пороговое значение. Порог принимается равным L, для кото­рой частота впервые становится меньше средней частоты длин строк. С другой стороны, в качестве порога целесообразно выбирать точку, в кото­рой произошло многократное падение частоты, что характерно для текстов со строгим выравниванием по ширине.

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

На рис. 7.3 изображено распределение частот длин строк, полученное для первых 32 Кб текста "Three men in a boat (to say nothing of the dog)". Видно, что Z,_mat = 73, максимум частоты находится в точке L = 72, а порог равен 65 символам, поскольку при этом частота впервые становится меньше средней частоты, если считать от точки L = 72.

58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 длина строки в символах (L)

-Частота строк такой длины •

•Средняя частота длин строк

Рис. 7.3. Распределение частот длин строк, полученное для первых 32 Кб текста "Three men in a boat (to say nothing of the dog)"

В качестве примера укажем в табл. 7.7 результаты сжатия тремя выбран­ными нами архиваторами преобразованного текста "Three men in а boat (to say nothing of the dog)". Длина строк измерялась в пробелах, преобразовыва­лись только СКС в строках с длиной 65 символов и более. Длины строк сжимались с помощью арифметического кодера на основании их безуслов­ных частот. Размер закодированного описания длин получился равным 793 байтам, и это число добавлялось к размеру архива обработанного файла при сравнении эффективности преобразования относительно разных мето­дов сжатия (BWT, LZ77, РРМ).

Таблица 7.7

Архиватор	Тип мето­да сжатия	Размер архи­ва исходного файла, байт	Размер архива обрабо­танного файла плюс размер описания длин строк, байт	Улучшение сжатия, %
Bzip2, вер. 1.00	BWT	109736	106069	3.3
WinRAR, вер. 2.71	LZ77	130174	126042	3.2
НАа2, вер. 0.999с	РРМ	108443	105018	3.2

Видно, что специальное кодирование СКС выгодно использовать в соче­тании с любым универсальным методом сжатия.

Оценка общего эффекта от использования предварительной обработки

До сих мы рассматривали различные методы препроцессинга текстов не­зависимо друг от друга. Естественно, что практический интерес требует их одновременного использования. Получим ли мы при этом увеличение сжа­тия равным сумме улучшений, обеспечиваемых каждым способом препро­цессинга по отдельности? Ответ на этот вопрос дают табл. 7.8 и 7.9, в кото­рых приведены результаты сжатия текста "Three men in a boat (to say nothing of the dog)", преобразованного с помощью последовательного при­менения четырех техник:

■ специального кодирования СКС;

■ преобразования заглавных букв;

■ модификации разделителей;

■ словарной замены л-графов (словарь из табл. 7.1).

Таблица 7.8

Архива­тор	Тип ме­тода сжатия	Размер архива исходного файла, байт	Размер архива обработанного файла плюс размер описания длин строк, байт	Улучше­ние сжа­тия, %	Улучшение сжатия без выполнения модифика­ции раздели­телей, %
Bzip2, вер. 1.00	BWT	109736	103047	6.1	6.0
WinRAR, вер. 2.71	LZ77	130174	120632	7.3	7.8
НАа2, вер. .999с	РРМ	108443	99788	8.0	7.3

В табл. 7.9 ожидаемое улучшение сжатия вычислялось как сумма улуч­шений для всех четырех типов препроцессинга относительно размера архи­ва исходного непреобразованного файла (см. табл. 7.3,7.5,7.6, 7.7).

Таблица 7.9

Архиватор	Тип метода сжатия	Улучшение сжатия, %	Ожидаемое улучшение сжатия, %
Bzip2, вер. 1.00	BWT	6.1	6.8
WinRAR, вер. 2.71	LZ77	7.3	7.1
НА а2, вер. 0.999с	РРМ	8.0	7.6

Из таблиц видно, что для НА и, в меньшей степени, WinRAR, проявился даже положительный кумулятивный эффект от применения нескольких ал­горитмов предварительной обработки. Это достаточно странный на первый взгляд результат, так как чем совершеннее алгоритм сжатия, тем меньший выигрыш должно давать использование дополнительных механизмов, что, собственно, мы и наблюдаем в случае архиватора BZIP2. До некоторой сте­пени это можно объяснить тем, что после преобразования заглавных букв большее количество л-графов может быть заменено на соответствующие им индексы словаря, что уменьшает разнообразие используемых строк и спо­собствует увеличению сжатия. Возможно, сочетание словарной замены со специальным кодированием СКС настолько уменьшает общее количество строк, сжимаемых с помощью словаря LZ77, при одновременном уменьше­нии их фиктивной длины, что это компенсирует падение общего процента улучшения сжатия. Вставка пробелов или замена СКС на пробелы умень­шает количество контекстов и соответственно уменьшает размер РРМ-модели, поэтому НА, ограниченный всего лишь примерно 400 Кб памяти, может использовать для оценки большее количество статистики, что улуч­шает сжатие. Судя по всему, реализация BWT и сопутствующих методов в BZIP2 и принципиальные особенности алгоритма блочной сортировки не позволили BWT "воспользоваться" ситуацией так же эффективно, как LZ77 и РРМ.

Рассмотрим, что произойдет при использовании LIPT вместо словарной замены и-графов. В табл. 7.10 представлены результаты сжатия преобразо­ванного текста, полученного с помощью трех упоминавшихся техник пре­процессинга с последующим использованием LIPT, алгоритм 2 (см. "Ис­пользование словарей" в начале подразд. "Препроцессинг текстов").

Таблица 7.10

Архиватор	Тип ме­тода сжатия	Размер ар­хива исход­ного файла, байт	Размер архива обработанного файла плюс раз­мер описания длин строк, байт	Улуч­шение сжатия, %	Ожидае­мое улучше­ние сжа­тия, %
Bzip2, вер. 1.00	BWT	109736	93882	14.4	12.9
WinRAR, вер. 2.71	LZ77	130174	114566	12.0	10.1
НАа2, вер. 0.999с	РРМ	108443	94191	13.1	14.9

И опять мы видим, что различные способы препроцессинга дополняют друг друга, обеспечивая рост степени сжатия. Хотя теперь ситуация до не­которой степени поменялась: увеличение сжатия больше ожидаемого для BWT и LZ77, а в случае РРМ наблюдается эффект "насыщения". Отметим, что использованная схема предварительной обработки далеко не самая луч­шая, если ее предполагается использовать совместно с LZ-компрессором. В этом случае за счет упоминавшихся модификаций можно повысить сте­пень сжатия еще на несколько процентов.

Вывод. Одновременное применение рассмотренных способов предвари­тельной обработки текстов позволяет улучшить сжатие на 5-8 % в случае простой словарной схемы препроцессинга и на 12-15 % при использовании громоздкого словаря.