Перейдем к рассмотрению способов сжатия данных, полученных в результате описанных выше преобразований. Для начала надо разобраться с данными, которые нам необходимо сжать.
Рассмотрим фрагмент данных, типичный для текста, преобразованного посредством 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).
Группа |
Кодируемые |
ран |
ги |
|
|
0 1 2 3 |
0 1 2 4 |
3 5 |
|
6 |
7 |
8 |
128 |
129 |
|
|
255 |
Рис. 5.22. Структурная модель
Ниже, рис. 5.23, приводятся частоты групп для файла bookl при использовании обычного и модифицированного MTF.
Номер группы |
MTF обычный, % |
MTF модифицированный, % |
0 |
49.77 |
51.44 1 |
1 |
15.36 |
14.93 |
2 |
13.19 |
12.41 |
3 |
11.05 |
10.72 |
4 |
8.28 |
8.16 |
5 |
2.14 |
2.13 |
6 |
0.20 |
0.20 |
7 |
0.01 |
0.01 |
8 |
0.00 |
0.00 |
Рис. 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
Размер блока, Кб |
bzip21.01 Размер сжатого файла, байт |
bzip21.01 Время сжатия, с |
YBS О.ОЗе Размер сжатого файла, байт |
YBS О.ОЗе Время сжатия, с |
100 |
270,508 |
0.61 |
255,428 |
0.65 |
200 |
256,002 |
0.66 |
239,392 |
0.66 |
300 |
249,793 |
0.71 |
232,681 |
0.71 |
400 |
243,402 |
0.72 |
225,659 |
0.73 |
500 |
242,662 |
0.73 |
224,782 |
0.74 |
600 |
241,169 |
0.75 |
222,782 |
0.76 |
700 |
237,993 |
0.76 |
218,826 |
0.77 |
800 |
232,598 |
0.77 |
213,722 |
0.77 |
Что касается данных неоднородных, то здесь картина иная. Размер блока надо выбирать таким, чтобы его край приходился на то место, где данные резко меняются. Причем для BWT страшна не сама неоднородность как таковая, а изменение статистики символов, предсказываемых устойчивыми контекстами. Например, нас не должен пугать тот факт, что в начале файла часто встречаются строки "abed", а в конце их место занимают "efgh". Гораздо неприятнее, когда вместо строк "abed" начинают появляться строки "abgh". Это не означает, что файл, в котором наблюдается вторая ситуация, сожмется при помощи BWT-компрессора очень плохо. Но разница в сжатии по сравнению с архиваторами, использующими, например, словарные методы, на таких данных будет не в пользу BWT.
Для иллюстрации зависимости эффективности сжатия неоднородных данных от размера блока сожмем исполнимый файл из дистрибутива компилятора Watcom 10.0, wcc386.exe (536,624 байта).
Размер блока, Кб |
bzip2 1.01 размер сжатого файла, байт |
bzip2 1.01 время сжатия, с |
YBS О.ОЗе размер сжатого файла, байт |
YBS О.ОЗе время сжатия, с |
100 |
309,716 |
0.66 |
279,596 |
0.60 |
200 |
308,668 |
0.66 |
277,312 |
0.61 |
300 |
308,812 |
0.66 |
277,285' |
0.61 |
400 |
309,163 |
0.66 |
277,374 |
0.60 |
500 |
307,131 |
0.66 |
274,351 |
0.60 |
600 |
308,624 |
0.66 |
276,026 |
0.60 |
Переупорядочение символов
В отличие от многих других методов сжатие, основанное на преобразовании Барроуза - Уилера, заметно зависит от лексикографического порядка следования символов. Замечено, что символы, имеющие сходное использование в словообразовании, лучше располагать поблизости.
Возьмем такие часто встречающиеся окончания слов русского языка, как -ый и -ий. Легко заметить, что им в большинстве случаев предшествуют одни и те же символы, например буква "н". Если эти окончания в результате сортировки каким-то образом окажутся в начале соседних строк матрицы перестановок, мы получим в последнем столбце рядом стоящие одинаковые символы.
Этот эффект особенно заметен на текстовых файлах. Для разных языков нюансы выбора лучшего переупорядочения символов могут отличаться, но общее правило таково - все символы надо поделить на 3 лексикографически отдельных группы: гласные, согласные и знаки препинания.
Файл |
Размер архива, байт |
|
bzip2 1.01 |
YBS О.ОЗе |
|
boolcl |
232,598 |
213,722 |
bookl, после переупорядочения символов |
231,884 |
212,975 |
Направление сортировки
Можно сортировать строки слева направо и в качестве результата преобразования использовать последний столбец матрицы отсортированных строк. А можно - справа налево и использовать первый столбец. Как делать лучше с точки зрения степени сжатия?
Первая стратегия подразумевает предсказание символа исходя из того, какие символы за ним следуют, а вторая - исходя из того, какие были раньше. В литературе для обозначения этих двух направлений используются словосочетания "following contexts" и "preceding contexts" соответственно (правосторонние и левосторонние контексты).
Практика показывает, что большинство архиваторов, использующих традиционные BWT и MTF, достигают лучшего сжатия на текстовых данных при использовании правосторонних контекстов. Для данных, имеющих "не лингвистическую" природу, лучше использовать левосторонние контексты. Например, это справедливо для исполнимых файлов.
Для компрессоров, которые не используют MTF, а проблему адаптации кодера к потоку преобразованных данных решают как-то иначе, выбор направления сортировки может быть иным. Например, DC и YBS многие исполнимые файлы, как и текстовые, сжимают лучше при сортировке слева направо.
Проделать самостоятельное сравнение очень просто. Возьмите ваш любимый архиватор и сожмите с его помощью ваш любимый файл. Затем переверните данные этого файла наоборот, сожмите полученное и сравните результаты.
Файл |
Направление сортировки |
Размер сжатого файла, байт |
|
bzip2 1.01 |
YBS О.ОЗе |
||
bookl |
following contexts |
232,598 |
213,722 |
bookl |
preceding contexts |
234,538 |
214,890 |
wcc386.exe |
following contexts |
308,624 |
276,026 |
wcc386.exe |
preceding contexts |
306,020 |
279,198 |
Некоторые программы самостоятельно пытаются определить тип данных и выбрать направление сортировки. Иногда, впрочем, ошибаясь. Простейший способ обмануть такой архиватор - дать ему сжать русский текст.