Техника контекстного моделирования Prediction by Partial Matching (предсказание по частичному совпадению), предложенная в 1984 г. Клири (Geary) и Уиттеном (Witten) [5], является одним из самых известных подходов к сжатию качественных данных и уж точно самым популярным среди контекстных методов. Значимость подхода обусловлена и тем фактом, что алгоритмы, причисляемые к РРМ, неизменно обеспечивают в среднем наилучшее сжатие при кодировании данных различных типов и служат стандартом, "точкой отсчета" при сравнении универсальных алгоритмов сжатия.
Перед собственно рассмотрением алгоритмов РРМ необходимо сделать замечание о корректности используемой терминологии. На протяжении примерно 10 лет - с середины 80-х гг. до середины 90-х - под РРМ понималась группа методов с вполне определенными характеристиками. В последние годы, вероятно из-за резкого увеличения числа всевозможных гибридных схем и активного практического использования статистических моделей для сжатия, произошло смешение понятий и термин "РРМ" часто используется для обозначения контекстных методов вообще.
Ниже будет описан некий обобщенный алгоритм РРМ, а затем особенности конкретных распространенных схем.
Как и в случае многих других контекстных методов, для каждого контекста, встречаемого в обрабатываемой последовательности, создается своя контекстная модель КМ. При этом под контекстом понимается последовательность элементов одного типа - символов, пикселов, чисел, но не набор разнородных объектов. Далее вместо слова "элемент" мы будем использовать слово "символ". Каждая КМ включает в себя счетчики всех символов, встреченных в соответствующем контексте.
РРМ относится к адаптивным методам моделирования. Исходно кодеру и декодеру поставлена в соответствие начальная модель источника данных. Будем считать, что она состоит из КМ(-1), присваивающей одинаковую вероятность всем символам алфавита входной последовательности. После обработки текущего символа кодер и декодер изменяют свои модели одинаковым образом, в частности наращивая величину оценки вероятности рассматриваемого символа. Следующий символ кодируется (декодируется) на основании новой, измененной модели, после чего модель снова модифицируется и т. д. На каждом шаге обеспечивается идентичность модели кодера и декодера за счет применения одинакового механизма ее обновления.
В РРМ используется неявное взвешивание оценок. Попытка оценки символа начинается с KM(/V), где N является параметром алгоритма и называется порядком РРМ-модели. В случае нулевой частоты символа в КМ текущего порядка осуществляется переход к КМ меньшего порядка за счет использования механизма уходов (escape strategy), рассмотренного в предыдущем подразд.
Фактически, вероятность ухода - это суммарная вероятность всех символов алфавита входного потока, еще ни разу не появлявшихся в контексте. Любая КМ должна давать отличную от нуля оценку вероятности ухода. Исключения из этого правила возможны только в тех случаях, когда значения всех счетчиков КМ для всех символов алфавита отличны от нуля, т. е. любой символ может быть оценен в рассматриваемом контексте. Оценка вероятности ухода традиционно является одной из основных проблем алгоритмов с неявным взвешиванием, и она будет специально рассмотрена ниже в подразд. "Оценка вероятности ухода".
)i Вообще говоря, способ моделирования источника с помощью классических алгоритмов РРМ опирается на следующие предположения о природе источника:
1) источник является марковским с порядком N, т. е. вероятность генерации символа зависит от N предыдущих символов и только от них;
2) источник имеет такую дополнительную особенность, что чем ближе располагается один из символов контекста к текущему символу, тем больше корреляция между ними.
Таким образом, механизм уходов первоначально рассматривался лишь как вспомогательный прием, позволяющий решить проблему кодирования символов, ни разу не встречавшихся в контексте порядка N. В идеале, достигаемом после обработки достаточно длинного блока, никакого обращения к КМ порядка меньше N происходить не должно. Иначе говоря, причисление классических алгоритмов РРМ к методам, производящим взвешивание, пусть и неявным образом, является не вполне корректным.
При сжатии очередного символа выполняются следующие действия.
Если символ 5 обрабатывается с использованием РРМ-модели порядка N, то, как мы уже отмечали, в первую очередь рассматривается KM(JV). Если она оценивает вероятность s числом, не равным нулю, то сама и используется для кодирования s. Иначе выдается сигнал в виде символа ухода, и на основе меньшей по порядку KM(N-l) производится очередная попытка оценить вероятность s. Кодирование происходит через уход к КМ меньших порядков до тех пор, пока s не будет оценен. КМ(-1) гарантирует, что это в конце концов произойдет. Таким образом, каждый символ кодируется серией кодов символа ухода, за которой следует код самого символа. Из этого следует, что вероятность ухода также можно рассматривать как вероятность перехода к контекстной модели меньшего порядка.
Если в процессе оценки обнаруживается, что текущий рассматриваемый контекст встречается в первый раз, то для него создается КМ.
При оценке вероятности символа в КМ порядка о < N можно исключить из рассмотрения все символы, которые содержатся в КМ(о+1), поскольку ни один из них точно не является символом s. Для этого в текущей КМ(о) нужно замаскировать, т. е. временно установить в нуль, значения счетчиков всех символов, имеющихся в КМ(о+1). Такая техника называется методом исключения (exclusion).
После собственно кодирования символа обычно осуществляется обновление статистики всех КМ, использованных при оценке его вероятности, за исключением статической КМ(-1). Такой подход называется методом исключения при обновлении. Простейшим способом модификации является инкремент счетчиков символа в этих КМ. Подробнее о стратегиях обновления будет сказано в подразд. "Обновление счетчиков символов".
Пример работы алгоритма РРМ
Рассмотрим подробнее работу алгоритма РРМ с помощью примера.
Пример 2
Имеется последовательность символов "абвавабввбббв" алфавита {"а", "б", "в", "г"}, которая уже была закодирована.
а |
б |
в |
а |
в |
а |
б |
в |
в |
б |
б |
б |
>|? |
Пусть счетчик символа ухода равен единице для всех КМ, при обновлении модели счетчики символов увеличиваются на единицу во всех активных КМ, применяется метод исключения и максимальная длина контекста равна трем, т. е. N= 3.
Первоначально модель состоит из КМ(-1), в которой счетчики всех четырех символов алфавита имеют значение 1. Состояние модели обработки последовательности "абвавабввбббв" представлено на рис. 4.2, где прямоугольниками обозначены контекстные модели, при этом для каждой КМ указан курсивом контекст, а также встречавшиеся в контексте символы и их частоты.
Пусть текущий символ равен "г", т. е. "?" = "г", тогда процесс его кодирования будет выглядеть следующим образом.
|
Рис. 4.2. Состояние модели после обработки последовательности "абвавабввбббв"
Сначала рассматривается контекст 3-го порядка "ббв". Ранее он не встречался, поэтому кодер, ничего не послав на выход, переходит к анализу статистики для контекста 2-го порядка. В этом контексте ("бв") встречались символ "а" и символ "в", счетчики которых в соответствующей КМ равны 1 каждый, поэтому символ ухода кодируется с вероятностью 1/(2+1), где в знаменателе число 2- это наблюдавшаяся частота появления контекста "бв", 1 - это значение счетчика символа ухода. В контексте 1-го порядка "в" дважды встречался символ "а", который исключается (маскируется), один раз также исключаемый "в" и один раз "б", поэтому оценка вероятности ухода будет равна 1/(1+1). В КМ(0) символ "г" также оценить нельзя, причем все имеющиеся в этой КМ символы "а", "б", "в" исключаются, так как уже встречались нам в КМ более высокого порядка. Поэтому вероятность ухода получается равной единице. Цикл оценивания завершается на уровне КМ(-1), где "г" к этому времени остается единственным до сих пор не попадавшимся символом, поэтому он получает вероятность 1 и кодируется посредством 0 бит. Таким образом, при использовании хорошего статистического кодировщика для представления "г" потребуется в целом примерно 2.6 бита.
Перед обработкой следующего символа создается КМ для строки "ббв" и производится модификация счетчиков символа "г" в созданной и во всех просмотренных КМ. В данном случае требуется изменение КМ всех порядков от 0 до N.
Табл. 4.2 демонстрирует оценки вероятностей, которые должны были быть использованы при кодировании символов алфавита {"а", "б", "в", "г"} в текущей позиции.
Таблица 4.2
Символе |
Последовательность оценок для КМ каждого порядка от 3 до -1 |
Общая оценка вероятности q(s) |
Представление требует битов |
||||
3 |
2 |
1 |
О |
-1 |
|||
|
"ббв" |
"бв" |
"в" |
ИИ |
|
|
|
"а" |
" |
1 2 + 1 |
~ |
'" |
* |
1 3 |
1.6 |
"б" |
'• |
1 2 + 1 |
1 1 + 1 |
■ |
~ |
1 6 |
2.6 |
"в" |
" |
1 2 + 1 |
" |
■ |
" |
1 3 |
1.6 |
tip" |
" |
1 2 + 1 |
1 1 + 1 |
1 |
1 |
1 6 |
2.6 |
Алгоритм декодирования абсолютно симметричен алгоритму кодирования. После декодирования символа в текущей КМ проверяется, не является ли он символом ухода;, если это так, то выполняется переход к КМ порядком ниже. Иначе считается, что исходный символ восстановлен, он записывается в декодированный поток и осуществляется переход к следующему шагу. Содержание процедур обновления счетчиков, создания новых контекстных моделей, прочих вспомогательных действий и последовательность их применения должны быть строго одинаковыми при кодировании и декодировании. Иначе возможна рассинхронизация копий модели кодера и декодера, что рано или поздно приведет к ошибочному декодированию какого-то символа. Начиная с этой позиции вся оставшаяся часть сжатой последовательности будет разжата неправильно.
Разница между кодами символов, оценки вероятности которых одинаковы, достигается за счет того, что РРМ-предсказатель передает кодировщику так называемые накопленные частоты (или накопленные вероятности) оцениваемого символа и его соседей или кодовые пространства символов. Так, например, для контекста "бв" из примера 2 можно составить табл. 4.3.
Таблица 4.3
Символ |
Частота |
Оценка вероятности |
Накопленная вероятность (оценка) |
Кодовое пространство |
"а" |
1 |
1/3 |
1/3 |
[0...0.33) |
"б" |
0 |
- |
- |
- |
"в" |
1 |
1/3 |
2/3 |
Г0.33...0.66) |
•ум |
0 |
- |
- |
- |
Уход |
1 |
1/3 |
1 |
[0.66 ... 1) |
Хороший кодировщик должен отобразить символ 'У с оценкой вероятности q(s) в код длины \og2q{s), что и обеспечит сжатие всей обрабатываемой последовательности в целом.
В обобщенном виде алгоритм кодирования можно записать так.
/*инициализация контекста длины N (в смысле строки предыдущих символов), эта строка должна содержать N предыдущих символов, определяя набор активных контекстов длины о £ N */
context = ""; while ( ! DataFile.EOFO И
с = DataFile.ReadSymbol(); // текущий символ
order = N; // текущий порядок КМ
success =0; // успешность оценки в текущей КМ
do{
// найдем КМ для контекста текущей длины СМ = ContextModel.FindModel (context, order); /♦попробуем найти текущий символ с в этой КМ, в CumFreq получим его накопленную частоту (или накопленную частоту символа ухода), в counter -ссылку на счетчик символа; флаг success указывает
на отсутствие ухода
*/
success = CM.EvaluateSymbol (с, sCumFreq, counter);
/♦запомним в стеке КМ и указатель на счетчик для последующего обновления модели
*/
Stack.Push (CM, counter);
// закодируем с или символ ухода
StatCoder.Encode (CM, CumFreq, counter);
order—; (while ( ! success ); /♦обновим модель: добавим KM в случае необходимости,
изменим значения счетчиков и т. д. */
UpdateModel (Stack);
// обновим контекст: сдвинем влево, справа добавим с MoveContext (с); }
Пример реализации РРМ-компрессора
Рассмотрим основные моменты реализации компрессора РРМ для простейшего случая с порядком модели N = 1 без исключения символов. Будем также исходить из того, что статистическое кодирование выполняется арифметическим кодером.
При контекстном моделировании 1-го порядка нам не требуются сложные структуры данных, обеспечивающие эффективное хранение и доступ к информации отдельных КМ. Можно просто хранить описания КМ в одномерном массиве, размер которого равен количеству символов в алфавите входной последовательности, и находить нужную КМ, используя символ ее контекста как индекс. Мы используем байт-ориентированное моделирование, поэтому размер массива для контекстных моделей порядка 1 будет равен 256. Чтобы не плодить лишних сущностей, мы, во-первых, откажемся от КМ(-1) за счет соответствующей инициализации КМ(0) и, во-вторых, будем хранить КМ(0) в том же массиве, что и КМ(1). Считаем, что КМ(0) соответствует индекс 256.
В структуру контекстной модели ContextModel включим массив счетчиков count для всех возможных 256 символов. Для символа ухода введем в структуру КМ специальный счетчик esc, а также добавим поле TotFr, в котором будет содержаться сумма значений счетчиков всех обычных символов. Использование поля TotFr не обязательно, но позволит ускорить обработку данных.
С учетом сказанного структуры данных компрессора будут такими:
struct.ContextModel{
int esc,
TotFr;
int count[256]; }; ContextModel cm(257];
Если размер типа int равен 4 байтам, то нам потребуется не менее 257 Кб памяти для хранения модели.
Опишем стек, в котором будут храниться указатели на требующие модификации КМ, а также указатель стека SP и контекст context.
ContextModel *stack[2];
int SP,
context [1]; //контекст вырождается в 1 символ
Больше никаких глобальных переменных и структур данных нам не нужно.
Инициализацию модели будем выполнять в общей для кодера и декодера функции init_model.
void init_model (void){
/*Так как cm является глобальной переменной, то значения всех полей равны нулю. Нам требуется только распределить кодовое пространство в КМ(0) так,, чтобы все символы,включая символ ухода, всегда бы имели ненулевые оценки. Пусть также символы будут равновероятными
*/
for ( int j = 0; j < 256; j++ ) cra[256].countfj] = 1 ;
cm[256].TotFr = 256;
/*Явнр запишем, что в начале моделирования мы считаем контекст равным нулю. Число не имеет значения, лишь бы 'кодер и декодер точно следовали принятым соглашениям. Обратите на это внимание
*/
context [0] = 0; SP = 0; }
Функции обновления модели также будут общими для кодера и декодера. В updatemodel производится инкремент счетчиков просмотренных КМ, а в rescale осуществляется масштабирование счетчиков. Необходимость масштабирования обусловлена особенностями типичных реализаций арифметического кодирования и заключается в делении значений счетчиков пополам при достижении суммы значений всех счетчиков TotFr+esc некоторого порога. Подробнее об этом рассказано в подразд. "Обновление счетчиков символов" этой главы.
const int MAX_TotFr = 0x3fff; void rescale (ContextModel *CM){ CM->TotFr = 0; for (int i = 0; i < 256; i++){
/♦обеспечим отличие от нуля значения
счетчика после масштабирования */
CM->count[i] -= CM->count[i] » 1; CM->TotFr += CM->count[i]; } )
void update_raodel (int c){ while (SP) {
SP— ;
if ((stack(SP]->TotFr + stack[SP]->esc) >= MAXJTotFr)
rescale (stack[SP]); if (!stack[SP]->count[c])
/*в этом контексте это новый символ, увеличим
счетчик уходов */
stack[SP]->esc += 1; stack[SP]->count[c] += 1; stack[SP]->TotFr += 1; ) }
Собственно кодер реализуем функцией encode. Эта функция управляет последовательностью действий при сжатии данных, вызывая вспомогательные процедуры в требуемом порядке, а также находит нужную КМ. Оценка текущего символа производится в функции encodesym, которая передает результаты своей работы арифметическому кодеру.
int encode_sym (ContextModel *CM, int с) (
//КМ потребует инкремента счетчиков, запомним ее stack [SP++] = СМ;
if (CM->count[c]){
/♦счетчик сжимаемого символа не равен нулю, тогда его можно оценить в текущей КМ; найдем
накопленную частоту предыдущего в массиве count символа */
int CumFreqUnder = 0;
for (int i = 0; i < с; i++)
CumFreqUnder += CM->count[i];
/*передадим описание кодового пространства,
занимаемого символом с, арифметическому кодеру
*/
AC.encode (CumFreqUnder, CM->count[с], CM->TotFr + CM->esc);
return 1; // возвращаемся в encode с победой }else{
/*нужно уходить на КМ(0);
если текущий контекст 1-го порядка встретился первый раз, то заранее известно, что его КМ пуста (все счетчики равны нулю) и кодировать уход не только не имеет смысла, но и нельзя, так как TotFr+esc = 0
*/
if (CM->esc)
AC.encode (CM->TotFr, CM->esc, CM->TotFr + CM->esc)
return 0; // закодировать символ не удалось } }
void encode (void){
int с, // текущий символ
success; // успешность кодирования символа в КМ init_model ();
AC.StartEncode (); // проинициализируем арифм. кодер while (( с = DataFile.ReadSymboK) ) != EOF) { // попробуем закодировать в КМ(1) success = encodesym (&cm[context[0]], с); if (!success)
/*уходим на КМ(0), где любой символ получит
ненулевую оценку и будет закодирован */
encode_sym (&cm[256], с); update_model (с);
context [0] = с; // сдвинем контекст )
// закодируем знак конца файла символом ухода с КМ(0) AC.encode (cm[context[0]].TotFr, cmfcontext[0]].esc,
cm[context[0]].TotFr + cmfcontext[0]].esc); AC.encode (cm[256].TotFr, cm[256].esc,
cm(256].TotFr + cm[256].esc); // завершим работу арифметического кодера AC.FinishEncodeO ; }
Реализация декодера выглядит аналогично. Внимания заслуживает разве что только процедура поиска символа по описанию его кодового пространства. Метод getfreq арифметического кодера возвращает число х, лежащее в диапазоне [CiunFreqUnder, CumFreqUnder+CM->count[i]), т. е. CumFreqUnder < х < < CumFreqUnder+CM->count[i]. Поэтому искомым символом является i, для которого выполнится это условие.
int decode_sym (ContextModel *CM, int *c){ stack [SP++] = CM; if (!CM->esc) return 0;
int cum_freq = AC.get_freq (CM->TotFr + CM->esc); if (cum_freq < CM->TotFr){
/♦символ был закодирован в этой КМ; найдем символ и
его точное кодовое пространство */
int CumFreqUnder =0; int i = 0; for (;;){
if ( (CumFreqUnder + CM->count[i]) <= cum_freq)
CumFreqUnder += CM->count[i]; else break; i++; } /♦обновим состояние арифметического кодера
на основании точной накопленной частоты символа */ АС.decode_update (CumFreqUnder, CM->count[i],
CM->TotFr + CM->esc); *c = i; return 1; }else{
/* обновим состояние арифметического кодера на основании точной накопленной частоты символа, оказавшегося символом ухода */ АС.decode_update (CM->TotFr, CM->esc,
CM->TotFr + CM->esc); return 0; } }
void decode (void){
int c,
success; init_model () ;
AC.StartDecode О; for (;;)(
success = decode_sym (Scm[context[0]], &c); if (!success){
success = decode_sym (&cm[256], &c); if (!success) break; //признак конца файла )
update_model (с); context [0] = с; DataFile.WriteSymbol (с); } )
Характеристики созданного компрессора, названного Dummy, приведены в подразд. "Компрессоры и архиваторы, использующие контекстное моделирование" (см. "Производительность на тестовом наборе Calgary Compression Corpus"). Полный текст реализации Dummy оформлен в виде приложения 1.