Техника контекстного моделирования 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) в код длины \og₂q{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.