НА
Программа НА явилась, пожалуй, первым публично доступным архиватором, использующим контекстное моделирование. Не исключено, что НА стал бы очень популярным архиватором, если бы его автор, Гарри Хирвола (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 Excel, тексты на английском языке.
В 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).