Обзор классических алгоритмов контекстного моделирования

LOEMA

Судя по всему, впервые алгоритм контекстного моделирования был реа­лизован в 1982 г. Робертсом (Roberts) [2]. Автор назвал свой алгоритм Local Order Estimation Markov Analysis (марковский анализ посредством оценива­ния локального порядка). В LOEMA используется полное смешивание оце­нок КМ различного порядка, при этом веса представляют собой значения уровня доверия к оценке в том смысле, как это понимается в математиче­ской статистике. Сравнение степени сжатия LOEMA с другими алгоритма­ми затруднено, так как, с одной стороны, программа, реализующая алго­ритм, не стала публично доступной и, с другой стороны, файлы, на которых Роберте доказывал эффективность своего подхода, также недоступны. Имеются сторонние отчеты, по которым LOEMA обеспечивает компрессию примерно на уровне РРМС (см. табл. 4.9) при значительно меньшей скоро­сти, что выглядит вполне правдоподобно. Судя по всему, LOEMA Робертса позволял только оценивать, но не сжимать, т. е. выполнял исключительно статистическое моделирование.

DAFC

Алгоритм Double-Adaptive File Compression (дважды адаптивное сжатие файлов), разработанный Лэнгдоном (Langdon) и Риссаненом (Rissanen) в 1983 г., сыграл серьезную роль в развитии контекстных методов [2]. Во-первых, в нем впервые, если не считать LOEMA, была реализована идея разделения процесса кодирования на моделирование и статистическое ко­дирование, а также идея одновременной адаптации структуры модели (т. е. набора КМ) и частот символов. Во-вторых, простота алгоритма обеспечива­ла возможность его реального применения при относительно скромных возможностях вычислительной техники 80-х гг. В-третьих, DAFC полюбил­ся научным работникам, охотно использовавшим его результаты для срав­нения при написании статей.

В DAFC используются контекстная модель 0-го порядка и л контекст­ных моделей 1-го порядка. В начале сжатия используется КМ(0), в которой все символы алфавита обрабатываемой последовательности имеют отлич­ные от нуля счетчики. По мере хода кодирования КМ(1) создаются только для первых и символов, встретившихся в уже обработанном блоке т раз. Из соображений экономии памяти авторы предлагали использовать л = 31 и т = 50. Далее если текущий символ встречается в контексте С и для этого контекста существует КМ(1), то производится попытка закодировать символ в ней, иначе выдается символ ухода с вероятностью, оцениваемой по методу А, и символ кодируется в КМ(0).

В DAFC также применяется кодирование длин повторов (RLE), кото­рое "запускается" при встрече последовательности из трех одинаковых символов.

Упражнения: Сравните DAFC с алгоритмом работы компрессора Dummy. Если пренебречь RLE, то какие изменения следует внести в Dummy, чтобы получить реализацию DAFC?

Пользуясь приведенными в тексте таблицами, сравните DAFC и Dummy по степени сжатия файлов набора CalgCC (см. табл. 4.8 и 4.9).

ADSM

Алгоритм Adaptive Dependency Source Model (модель источника с адап­тирующейся зависимостью) Абрахамсона (Abrahamson) представляет собой образец интересного подхода к реализации идеи контекстного моделирова­ния [2]. Здесь осуществляется чистое контекстное моделирование 1-го по­рядка, но собственно оценка строится на основании только одного распре­деления частот, общего для всех КМ. Достигается это следующим образом. В каждой КМ(1) счетчики символов хранятся в виде упорядоченного по ве­личине частот списка. Счетчики ранжируются так, что символ с наиболь­шей частотой имеет наименьший ранг 1, а с наименьшей частотой - наи­больший ранг. При обработке текущего символа находится его ранг (это может быть просто номер символа в упорядоченном списке символов теку­щей контекстной модели) и оценка определяется частотой использования этого ранга. Частоты рангов изменяются после кодирования каждого сим­вола. Таким образом, статистическое кодирование осуществляется не на ба­зе частоты символа, а на основании количества появлений символов с соот­ветствующим рангом частоты. Рассмотрим сжатие строки "молоч-ноемолоко" начиная с отмеченного на рисунке стрелкой символа.

В контексте "м" реально встречался только один символ "о", соответст­вующий текущему, поэтому мы кодируем "о", опираясь на частоту fr{\) ис­пользования ранга 1. Затем fii\) обновляется какУК1)⁺⁺- Следующий сим­вол, "л", кодируется в контексте "о". Соответствующая КМ(1) содержит 3 реально наблюдавшихся символа - "л", "ч", "е". Если принять, что в случае одинаковости частот наименьший ранг имеет последний встреченный символ, то "л" кодируется на базе частоты fr(3) применения ранга 3. Произво­дится обновлениеу^З)++ и переход к обработке следующей буквы, "о".

Ни разу не встреченные в соответствующей КМ(1) символы, т. е. имею­щие нулевую частоту, не трактуются как особый случай, им также присваи­вается какой-то ранг.

Были исследованы расширения алгоритма ADSM для 2-го и 3-го поряд­ков [9]. Результаты экспериментов показывают, что, в отличие от многих других классических алгоритмов контекстного моделирования, ADSM ак­туален и по сей день, так как обеспечивает хорошее соотношение скорости работы, объема используемой памяти и коэффициента сжатия. Так, напри­мер, техника ADSM использована в программе сжатия изображений без по­терь BMF, являющейся одной из лучших в своем классе.

Упражнение. Сожмите строку с самого начала, найдите действительные зна­чения ft(1) и ЦЗ), используемые при кодировании 'о" и "л" в примере.

DHPC

Техника Dynamic-History Predictive Compression (сжатие на основе пред­сказания по динамической истории), предложенная Уильямсом (Williams), интересна в сравнении с DAFC как использующая иной способ ограничения роста модели. В этом алгоритме происходит создание КМ(о), только если родительская КМ(о+1) достаточно часто использовалась. Если представить контекст дочерней КМ в виде сцепления (конкатенации) аС какого-то сим­вола а и контекста С родительской, в случае классического DAFC являюще­гося пустой строкой, то можно дать такую сравнительную характеристику. В DAFC образование дочерней КМ возможно в случае превышения часто­той появления образующего контекст символа "а" заданного порога, а в DHPC - при превышении порога частотой появления родительского контек­ста С, т. е. только "заслуженные" КМ могут иметь "детей".

При исчерпании доступной памяти рост модели DHPC прекращается, далее возможна адаптация только за счет изменения счетчиков символов.

Благодаря использованию КМ бблыпих порядков DHPC дает лучшее сжатие, чем DAFC, но уступает по этому показателю классическим пред­ставителям семейства РРМ (РРМС и PPMD).

Алгоритмы РРМА и РРМВ

Алгоритмы РРМА и РРМВ являются самыми ранними среди представи­телей семейства РРМ [5]. Они были предложены авторами техники РРМ одновременно в одной и той же статье и могут рассматриваться как единст­венные "чистокровные" РРМ.

В РРМА и РРМВ применяется ОВУ по методам А и В соответственно. После кодирования символа производится полное обновление счетчиков. Значения счетчиков символов не масштабируются, что требует достаточно больших счетчиков (авторы алгоритмов использовали 32-битовые).

WORD

Алгоритм WORD был создан Моффатом (Moffat) в конце 80-х гг. специ­ально для сжатия текстов и является ярким представителем особого семей­ства контекстных методов.

В алгоритме используются КМ не только для символов, но и для после­довательностей (строк) конечной длины. Весь алфавит сжимаемого блока делится на "буквы" и "не-буквы". Последовательность букв называется "словом", а не-букв - "не-словом". Для оценивания применяются КМ 1-го и 0-го порядка, при этом буква предсказывается буквой, а слово - словом, аналогично для не-букв и не-слов. Если обрабатываемое слово ни разу не встречалось в КМ(1) для слов, то производится уход на уровень КМ(0); если же и там оценивание невозможно, т. е. такая строка встретилась впервые, то слово передается как последовательность букв. Для этого сначала кодирует­ся длина слова, а затем составляющие его буквы с использованием КМ пер­вого, нулевого и минус первого порядков. При оценке вероятностей букв используется техника уходов. Обработка не-слов и не-букв осуществляется аналогично. Таким образом, в WORD используется всего 12 типов КМ: 1-го и 0-го порядка для слов (не-слов), 1-го, 0-го и -1-го порядка для букв (не­букв), 0-го порядка для длин слов (не-слов).

Длина слова (не-слова) ограничивается 20 символами. Как и в случае DHPC, при достижении моделью заданного размера удаление всей структу­ры или ее части не производится, просто прекращается рост.