Опрос

Какой архиватор наиболее эффективный?:

Новички

Виктор Васильев
Юрий Антонов
Сергей Андреевич
Генадий
Avanasy

Компрессоры и архиваторы, использующие контекстное моделирование

НА

Программа НА явилась, пожалуй, первым публично доступным архива­тором, использующим контекстное моделирование. Не исключено, что НА стал бы очень популярным архиватором, если бы его автор, Гарри Хирвола (Hirvola), не прекратил работать над проектом.

В НА реализованы алгоритм семейства LZ77 и алгоритм типа РРМ.

Алгоритм РРМ представляет собой хорошо продуманную модификацию классического РРМС. Метод ОВУ является априорным и основывает оцен­ку ухода из КМ на количестве имеющихся в ней символов с небольшой час­тотой. LOE не производится, последовательность спуска с КМ высоких по­рядков является обычной. Максимальный порядок КМ равен четырем, ми­нимальный- минус единице. Для организации поиска КМ применяются хеш-цепочки. Хеширование осуществляется по символам контекста и его длине.

Результаты тестирования на CalgCC, представленные в табл. 4.8, полу­чены для версии 0.999с. Сжатие файлов осуществлялось с помощью метода 2 программы, который как раз и соответствует РРМ.

Архиватор разрабатывался для работы в MS DOS, и размер используе­мой памяти ограничен примерно 400 Кб, что, вообще говоря, мало для мо­дели 4-го порядка, поэтому сжатие можно существенно улучшить за счет увеличения объема доступной памяти.

СМ

СМ Булата Зиганшина (Ziganshin) является компрессором, применяю­щим блочно-адаптивное контекстное моделирование.

Алгоритм работы кодера следующий. Читается блок входных данных, по умолчанию до 1 Мб, и на основании его статистики строится модель задан­ного порядка N. Модель сохраняется в компактном виде в выходном файле, после чего с ее использованием кодируется сам считанный блок данных. За­тем, если еще не весь входной файл обработан, производятся аналогичные действия для следующего блока и т. д.

Идея построения модели заключается в следующем:

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

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

Дерево оставшихся КМ записывается в выходной файл, при этом описа­ния символов и их частот в определенных КМ сжимаются на основании ин­формации КМ-предков.

Оценка вероятности ухода из КМ при кодировании самих данных зави­сит от количества ее дочерних КМ, удаленных при "прочистке" модели. Собственно алгоритм оценки вероятности символов не отличается от клас­сического РРМ.

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

Характеристики степени сжатия компрессора, приведенные в табл. 4.8, были получены при запуске программы с параметрами -о4 и -ml0000000, т. е. был задан порядок N = 4, а максимальный объем памяти для хранения модели был увеличен с 5 Мб, используемых по умолчанию, до 10 Мб, что обеспечило отсутствие переполнения при обработке всех файлов CalgCC.

RK И RKUC

С точки зрения коэффициента сжатия разрабатываемый Малькольмом Тейлором (Taylor) архиватор RK является одним из лучших среди сущест­вующих на момент написания этой книги. Но достигается это не столько за счет очень хорошего РРМ-компрессора, сколько благодаря большому коли­честву применяемых техник предварительного преобразования данных, по­зволяющих значительно улучшить сжатие файлов определенных типов. Именно грамотно реализованный препроцессинг и позволяет показывать RK стабильно хорошие результаты при сжатии таких типовых данных, как объектные файлы, файлы ресурсов, документы MS Word и таблицы MS Ex­cel, тексты на английском языке.

В RK реализовано два алгоритма: статистический типа РРМ и словарный типа Зива - Лемпела. В качестве РРМ-компрессора в RK применяется об­легченный вариант программы RKUC, созданной также Тейлором.

С учетом сказанного мы исключили RK из таблицы сравнения контекст­ных компрессоров по степени сжатия (табл. 4.8).

RKUC реализует контекстное моделирование с максимальным порядком 16. Порядок КМ может быть равен 16, 12, 8, 5, ..., 0 и, вероятно, -1. Иначе говоря, в RKUC используется отличающийся от классического механизм выбора порядка следующей КМ в случае ухода. В дополнение к этому в за­висимости от параметров вызова программы может выполняться LOE.

Еще одна из опций компрессора разрешает использовать при оценке ве­роятности статистику, накопленную для разбросанных (sparse) контекстов, или бинарных (binary) в терминологии автора компрессора. Идея заклю­чается в том, что несколько обычных контекстов одинаковой длины могут считаться одним контекстом, если в определенных позициях их символы одинаковы. Например, если для контекстов длины 4 требуется совпадение первого1 (последнего обработанного), второго и четвертого символов, то строки "абсд" и "аасд" являются одним и тем же разбросанным контекстом "аХсд", где X - любой символ. Таким образом, техника разбросанных кон­текстов заключается в объединении информации, собираемой для несколь­ких классических контекстов. Применение этого механизма часто позволяет заметно улучшить сжатие блоков данных с регулярной структурой.

В RK.UC применяется улучшенный вариант адаптивной ОВУ по методу Z.

При тестировании использовался RKUC версии 1.04, который запускал­ся с параметрами -mlO -о 16 -х -Ь, т. е. использовалась модель 16-го порядка, ограниченная 10 Мб памяти, и были включены механизмы LOE и разбро­санных контекстов. Если отказаться от использования разбросанных кон­текстов, то степень сжатия текстовых файлов улучшается примерно на 1 %, а бинарных (Geo, Objl, Obj2) - ухудшается на несколько процентов.

PPMN

Компрессор PPMN разработан Максимом Смирновым (Smirnov) в экс­периментальных целях. Основная цель разработки состояла в создании РРМ-компрессора, обеспечивающего степень сжатия на уровне компрес­соров, использующих разновидности алгоритма PPMZ, и значительно более высокую скорость кодирования при меньших ограничениях на объем ис­пользуемой памяти.

В PPMN реализован алгоритм РРМ с ограниченным порядком контек­стов. Максимальный порядок N модели равен 7, но также реализованы ва­рианты модели с "псевдопорядками" 8 и 9, при которых каждой КМ(Л0, N = = 8-9, в действительности может соответствовать несколько контекстов по­рядка N. Иначе говоря, осуществляется смешивание статистики, набираемой для нескольких похожих контекстов.

Для ОВУ используется адаптивный механизм, который можно рассмат­ривать как упрощенный метод Z. Используется только один тип контекста ухода, поля которого определяются:

■ порядком КМ;

■ количеством просмотров КМ;

■ количеством символов в КМ;

■ последним обработанным символом;

Символы контекста обычно нумеруются справа налево, поэтому первый сим­вол контекста соответствует последнему обработанному.

■ I -битовым флагом, указывающим на то, что при кодировании строки по­следних обработанных символов заданной длины L = 16 ни разу не про­исходил уход.

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

Как и в компрессоре RKUC, последовательность выбора порядка кон­текстной модели в случае ухода отличается от классической - часть поряд­ков просто не используется. Например, при N - 5 РРМ-модель состоит из контекстных моделей 5, 3, 2, 1, 0, -1 порядков, поэтому в случае ухода из КМ(5) рассматривается КМ(3). Такой прием позволяет ускорить обработку, а уменьшение степени сжатия либо незначительно, либо, наоборот, наблю­дается ее увеличение.

Как уже упоминалось ранее, в PPMN используется масштабирование счетчика последнего встреченного символа. Улучшению сжатия неоднород­ных файлов также способствует ограничение на количество КМ порядков 1 и 2, приводящее к интенсивному обновлению этих КМ - статистика не используемых дольше всего контекстов просто удаляется.

В PPMN применяется упрощенный способ наследования информации: при добавлении символа в КМ(о) начальное значение его счетчика опреде­ляется частотой символа в той КМ(с^), к > О, в которой он был закодиро­ван. Механизм инкремента счетчиков соответствует обычному исключению при обновлении.

По аналогии с НА в качестве структуры данных для доступа к КМ ис­пользуются хеш-цепочки. Для ускорения поиска контекстных моделей каж­дый символ KM(N) имеет внешний указатель на КМ(Л0, соответствующую следующему символу обрабатываемого потока.

PPMN содержит механизмы предварительной обработки текстов на анг­лийском и русском языках и исполнимых файлов для процессоров типа Intel х86 (см. гл. 7). Кроме того, имеются средства кодирования таблиц 8-, 16- и 32-битовых элементов, а также кодирования длин повторов (RLE). Пара­метры SEE, механизмов наследования информации и обновления счетчиков настроены на обеспечение наилучшей степени сжатия в режиме обработки текстов с использованием средств препроцессинга.

В табл. 4.8 указаны результаты тестирования PPMN версии 1.00 beta 1 в режиме сжатия без использования предварительной обработки (опция -da компрессора). Порядок модели равнялся 6 (опция -об), а ее размер был ограничен 20 Мб.

PPMd и PPMonstr

Программы PPMd и PPMonstr Дмитрия Шкарина (Shkarin) реализуют разработанные им же алгоритмы РРМП и cPPMII (complicated PPM1I, т. е. "усложненный" РРМП) [1]. Оба компрессора используют механизм насле­дования информации. В PPMd применяется адаптивный метод ОВУ SEE-dl, а в PPMonstr - SEE-d2. Кроме этого отличия, в PPMonstr реализовано не­сколько дополнительных приемов улучшения сжатия, основными из кото­рых являются отложенное наследование и улучшение точности предска­зания наиболее вероятных символов.

РРМП является одним из алгоритмов, используемых в архиваторе RAR версии 3.

В тестировании были использованы версии Н компрессоров. PPMd за­пускался с опцией -о8, a PPMonstr- с опцией -ol, что соответствует моде­лям 8-го и 64-го порядка. Максимальный размер модели был ограничен 20 Мб (параметр -ш20) в обоих случаях, что предотвратило сброс статисти­ки модели, осуществляемый при полном заполнении выделенного объема памяти.

PPMY

PPMY является экспериментальным компрессором, разрабатываемым Евгением Шелвиным (Shelwien). Данная программа относится к немного­численному классу компрессоров, использующих полное смешивание.

При обработке каждого символа производится смешивание оценок рас­пределений вероятностей из КМ всех доступных порядков от некоторого N до -1. Величина N ограничивается сверху значением одного из параметров программы. Если позволяет данное ограничение, то в качестве КМ макси­мального порядка выбирается КМ с самым длинным контекстом, ранее встречавшимся по крайней мере один раз. Компрессор осуществляет моде­лирование на уровне байтов, поэтому КМ(-1) содержит счетчики для всех 256 возможных символов; значение каждого счетчика равно единице. Кроме счетчиков встречаемых в ее контексте символов, каждая КМ(о) содержит еще две переменные:

■ число символов в контексте; будем обозначать здесь как J[esc\o); приня­тое обозначение характеристики обусловлено тем, что ее значение сов­падало бы с количеством уходов из КМ(о), если бы мы имели дело с обычным алгоритмом РРМ;

■ число случаев, когда вероятность обрабатываемого символа в данной
КМ(о) была максимальной по сравнению с прочими контекстными мо­
делями; обозначим как Opt{p).

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

где До)- общее количество просмотров соответствующей КМ(о); ЕТ, vfm\ w(Ј) - некоторые параметры.

Коэффициентам Ц^'х) и Wjp" можно дать такую упрощенную интер­претацию:

ЦА"С) _ это вероятность того, что символ присутствует в текущей

КМ(о), или, в терминах классического РРМ, вероятность того, что ухода не будет;

ЦЛ°рП - это вероятность того, что именно данная КМ(о) имеет макси­
мальную оценку вероятности текущего символа.

Алгоритм нахождения значений параметров ЕТ, w(opl), w(Ј), обеспечи­вающий хороший коэффициент сжатия, был получен эмпирическим путем, и результаты вычислений сведены в таблицы. Для каждой КМ(о) величины параметров выбираются из соответствующей таблицы по адресу, опреде­ляемому значением пары {о, N).

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

В табл. 4.8 приведены результаты сжатия набора файлов CalgCC для PPMY версии ЗЬ. Кодер запускался с опцией /о64.

Производительность на тестовом наборе Calgary Compression Corpus

Все рассмотренные компрессоры и архиваторы были протестированы на наборе CalgCC, описанном в Введении в подразд. "Сравнение алгоритмов по степени сжатия". Для сравнения добавлены характеристики тривиально­го компрессора Dummy, на примере которого мы объясняли идею РРМ.

В таблице указаны степени сжатия отдельных файлов набора, средняя степень сжатия, общее время кодирования Ткод и декодирования Тдек. Сред­няя степень вычислялась как средняя не взвешенная по размеру файлов сте­пень сжатия. Для Ткоя и T^ за единицу принято время сжатия всего CalgCC компрессором PPMd. Чтобы внести ясность, заметим, что единица пример­но соответствует скорости кодирования 700 Кб/с для ПК с процессором ти­па Pentium III 733 МГц.

Таблица 4.8

Dummy

CM

HA

PPMY

RKUC

PPMN

PPMd

PPMonstr

Bib

2.31

3.01

4.12

4.55

4.55

4.57

4.62

4.76

bookl

2.22

2.99

3.27

3.72

3.62

3.64

3.65

3.74

book2

2.12

3.19

3.74

4.35

4.30

4.31

4.35

4.49

Geo

1.68

1.74

1.72

1.74

2.12

1.96

1.84

1.92

News

1.92

2.52

3.05

3.60

3.57

3.58

3.62

3.74

objl

1.76

1.69

2.19

2.09

2.25

2.32

2.26

2.29

obj2

1.94

2.32

3.07

3.46

3.79

3.65

3.62

3.79

Paper 1

2.08

2.37

3.39

3.59

3.51

3.59

3.65

3.74

Paper2

2.20

2.61

3.43

3.67

3.57

3.62

3.67

3.77

Pic

9.41

9.30

10.00

10.26

10.67

11.01

10.53

11.43

Progc

2.06

2.27

3.36

3.51

3.45

3.54

3.60

3.70

Progl

2.40

3.07

4.68

5.30

5.37

5.26

5.44

5.76

Progp

2.36

2.99

4.71

5.33

5.30

5.19

5.26

5.76

Trans

2.28

2.96

5.23

6.35

6.40

6.17

6.35

6.84

Итого

2.62

3.07

4.00

4.39

4.46

4.46

4.46

4.70

T

»Ю1Л

0.5

2.4

3.0

14.6

6.5

1.9

1.0

2.3

T

0.6

0.8

3.1

15.6

6.7

2.0

1.0

2.4

Другие архиваторы и компрессоры

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

■ BOA, автор Ян Саттон (Sutton);

■ ARHANGEL, автор Юрий Ляпко (Lyapko);

■ LGHA, являющийся реализацией архиватора НА на языке Ассемблера, выполненной Юрием Ляпко;

■ UHARC, автор Уве Херклоц (Herklotz);

■ XI, автор Стиг Валентини (Valentini),

а также компрессор PPMZ, автор Чарльз Блум (Bloom).