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

Рассмотрим фрагмент данных, типичный для текста, преобразованного посредством BWT. Для примера взят файл bookl из набора "Calgary Corpus" (рис. 5.19).

eteksehendeynkrtdserttnregenskngsgsedeneyswmessrne xgynystslgyegsgstssrhmsstetehselxtptneessthndesddy htksthwtpfdttegedmmhysyresprssneenselgetdemsetse,t reehsetrtteseeeeeesssdeedmnlendeedgtdgttdsgtteeysy tddentnrxsltshtghnteeernsdpwlttensedehsteeswekheee teneeeeseslteenestrngsthsdgeyeyrteetklrdtetteyodth eegeercesyttesedenrtresnyssgttsslsawssygsssrewmsht gt,etssgehnehessssehneesesdnrnekhtrsslthdsseestste nbgeeessesdesyndtrdhpeesehesetsrerhyesdnwtlrrhoses hsetdrptttsdhaynenetyntpgstesknhysftsgssdftgteeedu

Puc. 5.19. Однородный фрагмент

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

ygeldsd,,ttyogdodgdedndygnmotedgwkgodoowtdoddtotet tndmeggkrdsgtohtdegteddrsttttegtddewdddoootdgdntet

ststttstt!uetttdtte-elttetny,hettltgrlttylttnttyrt rtttttttetttttdtttstottttttttttntttttttn,ddtkgnde; ed,d,stefoefssfrsnsstyslw,fnoeadere,rteeynsfofhynn nyoytted,yfnedhddtoldtnyhnnhyrtyryttmeryesfoyedney oymd,sedesgnrrsysnssmydsspdyt'-dssehs,gynsdydgee'о defddeynt,,tdnd,os;sttyysofy-nnetognfetdnyldlewhe-odsttemshsdtsyteny,ngdefs,-offsnntettseyesgleay:es dtsdgllredksyryes,rldosts;dtdeefgghsfrergkdgngkenw

Puc. 5.20. Изменяющийся фрагмент

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

edeeeeeleydeyeeet'eeeleeeeeeeeeeeeeeeeeeeeeeleeeee еееееее!eeeeleeeeeeeeeeeeeeeeeeeeeeeyedeeereeeleee eeeeeeeeeeslyadeeeeeeeeeyeeeeeeeeeeeeeedyereseeeee elueeeeeeyeeeeeelsseseell'eeletenhyalehcesyyseessn s'dlesffao,dffeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeTeeee eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeteeeeeeeeeeeeeeee eeeeeeeeeeaerre,see,eywesldsysdhedeeetaeeesaeeyedo

Puc. 5.21. Фрагмент с преобладанием одного символа

Итак, выделим 3 вида данных:

1) на протяжении всего фрагмента несколько символов имеют постоян­ную частоту;

2) промежуток в фрагменте, когда преобладание одних символов сменя­ется преобладанием других;

3) один из символов встречается намного чаще других.

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

Сжатие при помощи кодирования по алгоритму Хаффмана

Указанные свойства преобразованных данных использует алгоритм, реа­лизованный в архиваторе bzip2 и позднее позаимствованный также разра­ботчиками архиватора IMP.

После преобразований BWT и MTF блок данных делится на равные 50-символьные куски. Полученные куски объединяются в группы по степени близости распределений MTF-рангов. Количество групп зависит от размера файла. Например, для мегабайтового файла таких групп будет шесть.

Группирование кусков выполняется итеративно. Изначально куски при­писываются группам в порядке следования в блоке так, чтобы каждой груп­пе соответствовало примерно равное количество кусков. Для каждой груп­пы строится отдельное дерево Хаффмана. В архив записываются деревья Хаффмана, номер группы для каждого из 50-символьного кусков, а затем все куски сжимаются по алгоритму Хаффмана в соответствии с номером той группы, к которой они относятся.

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

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

Сжатие по алгоритму Хаффмана довольно эффективно, хоть и уступает алгоритмам, в которых реализовано арифметическое сжатие, но зато замет­но быстрее при декодировании.

Алгоритмы, использующие кодирование по методу Хаффмана, довольно эффективны, хоть и уступают алгоритмам, в которых реализовано арифме­тическое сжатие

Структурная и иерархическая модели

Отметим основное свойство таких преобразований, как MTF, DC и IF: на

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

Анализируя перечисленные выше 3 вида фрагментов, можно отметить некоторые особенности, которыми можно воспользоваться при моделиро­вании:

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

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

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

Рассмотрим две модели, обладающие описанными качествами, - струк­турную и иерархическую [18].

Структурная модель. Кодирование символа осуществляется в два эта­па. Сначала кодируется номер группы, к которой этот символ относится. А затем - номер символа внутри группы.

Размеры групп различны. Наиболее частые символь! помещаются в группы, состоящие из небольшого числа символов. Предложенная Петером Фенвиком структурная модель предполагает самостоятельное существова­ние 0-го и 1-го ранга, т. е. каждый из них представляет собой отдельную группу. В следующую (третью по счету) группу помещаются 2-й и 3-й ранг, затем - с четвертого по седьмой и т. д. (рис. 5.22).

Рис. 5.22. Структурная модель

Ниже, рис. 5.23, приводятся частоты групп для файла bookl при исполь­зовании обычного и модифицированного MTF.

Рис. 5.23. Статистика распределения рангов в группах структурной модели

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

Эксперимент [16] показал, что структурная модель позволяет достичь немного лучшего сжатия и, в силу того, что для каждого символа в среднем требуется меньше операций арифметического кодирования, чуть быстрее.

Размер блока

Один из важных вопросов, который встает перед разработчиком архива­тора на основе преобразования Барроуза - Уилера, заключается в выборе размера блока.

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

Процессор Частота шины Оперативная память Жесткий диск Операционная система

Intel Pentium III 840 МГц

140 МГц

256 Мб SDRAM

Quantum FB 4.3 Гб

Windows NT 4.0 Service Pack 3

Что касается данных неоднородных, то здесь картина иная. Размер блока надо выбирать таким, чтобы его край приходился на то место, где данные резко меняются. Причем для BWT страшна не сама неоднородность как та­ковая, а изменение статистики символов, предсказываемых устойчивыми контекстами. Например, нас не должен пугать тот факт, что в начале файла часто встречаются строки "abed", а в конце их место занимают "efgh". Го­раздо неприятнее, когда вместо строк "abed" начинают появляться строки "abgh". Это не означает, что файл, в котором наблюдается вторая ситуация, сожмется при помощи BWT-компрессора очень плохо. Но разница в сжатии по сравнению с архиваторами, использующими, например, словарные мето­ды, на таких данных будет не в пользу BWT.

Для иллюстрации зависимости эффективности сжатия неоднородных данных от размера блока сожмем исполнимый файл из дистрибутива ком­пилятора Watcom 10.0, wcc386.exe (536,624 байта).

Переупорядочение символов

В отличие от многих других методов сжатие, основанное на преобразо­вании Барроуза - Уилера, заметно зависит от лексикографического порядка следования символов. Замечено, что символы, имеющие сходное использо­вание в словообразовании, лучше располагать поблизости.

Возьмем такие часто встречающиеся окончания слов русского языка, как -ый и -ий. Легко заметить, что им в большинстве случаев предшествуют од­ни и те же символы, например буква "н". Если эти окончания в результате сортировки каким-то образом окажутся в начале соседних строк матрицы перестановок, мы получим в последнем столбце рядом стоящие одинаковые символы.

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

Направление сортировки

Можно сортировать строки слева направо и в качестве результата преоб­разования использовать последний столбец матрицы отсортированных строк. А можно - справа налево и использовать первый столбец. Как делать лучше с точки зрения степени сжатия?

Первая стратегия подразумевает предсказание символа исходя из того, какие символы за ним следуют, а вторая - исходя из того, какие были рань­ше. В литературе для обозначения этих двух направлений используются словосочетания "following contexts" и "preceding contexts" соответственно (правосторонние и левосторонние контексты).

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

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

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

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