НА

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

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

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

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

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

СМ

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

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

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

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

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

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

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

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

Характеристики степени сжатия компрессора, приведенные в табл. 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 требуется совпадение первого¹ (последнего обработанного), второго и четвертого символов, то строки "абсд" и "аасд" являются одним и тем же разбросанным контекстом "аХсд", где 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).

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

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

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

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

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

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

Алгоритм нахождения значений параметров ЕТ, 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

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

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

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

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

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

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

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

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