Методы контекстного моделирования

Терминология

Под контекстным моделированием будем понимать оценку вероятности появления символа (элемента, пиксела, сэмпла, отсчета и даже набора качественно разных объектов) в зависимости от непосредственно ему предшествующих, или контекста.

Заметим, что в быту понятие "контекст" обычно используется в глобальном значении - как совокупность символов (элементов), окружающих текущий обрабатываемый. Это контекст в широком смысле. Выделяют также "левосторонние" и "правосторонние" контексты, т.е. последовательности символов, непосредственно примыкающие к текущему символу слева и справа соответственно. Здесь и далее под контекстом будем понимать именно классический левосторонний: так, например, для последнего символа 'о' последовательности "…молоко…" контекстом является "…молок".

Если длина контекста ограничена, то такой подход будем называть контекстным моделированием ограниченного порядка (finite-context modeling), при этом под порядком понимается максимальная длина используемых контекстов N. Например, при моделировании порядка 3 для последнего символа 'о' в последовательности "…молоко…" контекстом максимальной длины 3 является строка "лок". При сжатии этого символа под "текущими контекстами" могут пониматься "лок", "ок", "к", а также пустая строка "". Все эти контексты длины от N до 0 назовем активными контекстами в том смысле, что при оценке символа может быть использована накопленная для них статистика.

Далее вместо "контекст длины o, $$o \le N$$ /" мы будем обычно говорить "контекст порядка o".

В силу объективных причин - ограниченность вычислительных ресурсов - техника контекстного моделирования именно ограниченного порядка получила наибольшее развитие и распространение, поэтому далее под контекстным моделированием будем понимать именно ее. Дальнейшее изложение также учитывает специфику того, что контекстное моделирование практически всегда применяется как адаптивное.

Оценки вероятностей при контекстном моделировании строятся на основании обычных счетчиков частот, связанных с текущим контекстом. Если мы обработали строку "абсабвбабс", то для контекста "аб" счетчик символа 'c' равен двум (говорят, что символ 'c' появился в контексте "аб" два раза), символа 'в' - единице. На основании этой статистики можно утверждать, что вероятность появления 'c' после "аб" равна 2/3, а вероятность появления 'в' - 1/3, т.е. оценки формируются на основе уже просмотренной части потока.

В общем случае для каждого контекста конечной длины $$o \le N$$, встречаемого в обрабатываемой последовательности, создается контекстная модель КМ. Любая КМ включает в себя счетчики всех символов, встреченных в соответствующем ей контексте, т.е. сразу после строки контекста. После каждого появления какого-то символа s в рассматриваемом контексте производится увеличение значения счетчика символа s в соответствующей контексту КМ. Обычно счетчики инициализируются нулями. На практике счетчики обычно создаются по мере появления в заданном контексте новых символов, т.е. счетчиков ни разу не виденных в заданном контексте символов просто не существует.

Под порядком КМ будем понимать длину соответствующего ей контекста. Если порядок КМ равен o, то будем обозначать такую КМ как "КМ(o)".

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

Понятно, что для нулевого и минус первого порядка контекстная модель одна, а КМ большего порядка может быть несколько, вплоть до $$q^N,$$ где q - размер алфавита обрабатываемой последовательности. КМ(0) и КМ(-1) всегда активны.

Заметим, что часто не делается различий между понятием "контекст" и "контекстная модель". Авторы этой книги такое соглашение не поддерживают.

Часто говорят о "родительских" и "дочерних" контекстах. Для контекста "к" дочерними являются "ок" и "лк", поскольку они образованы сцеплением (конкатенацией) одного символа и контекста "к". Аналогично, для контекста "лок" родительским является контекст "ок", а контекстами-предками - "ок", "к", "". Очевидно, что "пустой" контекст "" является предком для всех. Аналогичные термины применяются для КМ, соответствующих контекстам.

Совокупность КМ образует модель источника данных. Под порядком модели понимается максимальный порядок используемых КМ.

Виды контекстного моделирования

Пример обработки строки "абсабвбабс" иллюстрирует сразу две проблемы контекстного моделирования:

Выше были приведены цифры, в соответствии с которыми при увеличении длины используемого контекста сжатие данных улучшается. К сожалению, при кодировании блоков типичной длины - единицы мегабайтов и меньше - это справедливо только для небольших порядков модели, т.к. статистика для длинных контекстов медленно накапливается. При этом также следует учитывать, что большинство реальных данных характеризуется неоднородностью, нестабильностью силы и вида статистических взаимосвязей, поэтому "старая" статистика контекстно-зависимых частот появления символов малополезна или даже вредна. Поэтому модели, строящие оценку только на основании информации КМ максимального порядка N, обеспечивают сравнительно низкую точность предсказания. Кроме того, хранение модели большого порядка требует много памяти.

Если в модели используются для оценки только КМ(N), то иногда такой подход называют "чистым" (pure) контекстным моделированием порядка N. Из-за вышеуказанного недостатка "чистые" модели представляют обычно только научный интерес.

Действительно, реально используемые файлы обычно имеют сравнительно небольшой размер, поэтому для улучшения их сжатия необходимо учитывать оценки вероятностей, получаемые на основании статистики контекстов разных длин. Техника объединения оценок вероятностей, соответствующих отдельным активным контекстам, в одну оценку называется смешиванием (blending). Известно несколько способов выполнения смешивания.

Рассмотрим модель произвольного порядка N. Если $$q(s_i |o)$$ есть вероятность, присваиваемая в активной КМ(o) символу $$s_i$$ алфавита сжимаемого потока, то смешанная вероятность $$q(s_i)$$ вычисляется в общем случае как

где w(o) - вес оценки КМ(o).

Оценка $$q(s_i |o)$$ обычно определяется через частоту символа $$s_i$$ по тривиальной формуле

где $$f(s_i |o)$$ - частота появления символа $$s_i$$ в соответствующем контексте порядка o ;

$$f(o)$$ - общая частота появления соответствующего контекста порядка o в обработанной последовательности.

Заметим, что правильнее было бы писать не, скажем, $$f(s_i |o)$$, а $$f(s_i |C_{j(o)})$$, т.е. "частота появления символа $$s_i$$ в КМ порядка o с номером j(o) ", поскольку контекстных моделей порядка o может быть огромное количество. Но при сжатии каждого текущего символа мы рассматриваем только одну КМ для каждого порядка, т.к. контекст определяется непосредственно примыкающей слева к символу строкой определенной длины. Иначе говоря, для каждого символа мы имеем набор из N+1 активных контекстов длины от N до 0, каждому из которых однозначно соответствует только одна КМ, если она вообще есть. Поэтому здесь и далее используется сокращенная запись.

Если вес w(-1) > 0, то это гарантирует успешность кодирования любого символа входного потока, т.к. наличие КМ(-1) позволяет всегда получать ненулевую оценку вероятности и, соответственно, код конечной длины.

Различают модели с полным смешиванием (fully blended), когда предсказание определяется статистикой КМ всех используемых порядков, и с частичным смешиванием (partially blended) - в противном случае.

Пример 1

Рассмотрим процесс оценки отмеченного на рис 3.2 стрелкой символа 'л', встретившегося в блоке "молочное_молоко". Считаем, что модель работает на уровне символов.

Пусть мы используем контекстное моделирование порядка 2 и делаем полное смешивание оценок распределений вероятностей в КМ второго, первого и нулевого порядков с весами 0.6, 0.3 и 0.1. Считаем, что в начале кодирования в КМ(0) создаются счетчики для всех символов алфавита {'м', 'о', 'л', 'ч', 'н', 'е', '_', 'к'} и инициализируются единицей; счетчик символа после его обработки увеличивается на 1.

Для текущего символа 'л' имеются контексты "мо", "о" и пустой (нулевого порядка). К данному моменту для них накоплена статистика, показанная в табл. 3.1.

Тогда оценка вероятности для символа 'л' будет равна

В общем случае, для однозначного кодирования символа 'л' такую оценку необходимо проделать для всех символов алфавита. Действительно, с одной стороны, декодер не знает, чему равен текущий символ, с другой стороны, оценка вероятности не гарантирует уникальность кода, а лишь задает его длину. Поэтому статистическое кодирование выполняется на основании накопленной частоты (см. подробности в примере 2 и в пункте "Арифметическое сжатие" главы 1). Например, если кодировать на основании статистики только нулевого порядка, то существует взаимно однозначное соответствие между накопленными частотами из диапазона (8,10] и символом 'л', что не имеет места в случае просто частоты (частоту 2 имеют еще 4 символа). Понятно, что аналогичные свойства остаются в силе и в случае оценок, получаемых частичным смешиванием.

Очевидно, что успех применения смешивания зависит от способа выбора весов w(o). Простой путь состоит в использовании заданного набора фиксированных весов КМ разных порядков при каждой оценке; этот способ был применен в примере 2. Естественно, альтернативой является адаптация весов по мере кодирования. Приспособление может заключаться в придании все большей значимости КМ все больших порядков или, скажем, попытке выбрать наилучшие веса на основании определенных статистических характеристик последнего обработанного блока данных. Но так исторически сложилось, что реальное развитие получили методы неявного взвешивания. Это объясняется в первую очередь их меньшей вычислительной сложностью.

Техника неявного взвешивания связана с введением вспомогательного символа ухода (escape). Символ ухода является квазисимволом и не должен принадлежать алфавиту сжимаемой последовательности. Фактически, он используется для передачи декодеру указаний кодера. Идея заключается в том, что если используемая КМ не позволяет оценить текущий символ (его счетчик равен 0 в этой КМ), то на выход посылается закодированный символ ухода и производится попытка оценить текущий символ в другой КМ, которой соответствует контекст иной длины. Обычно попытка оценки начинается с КМ наибольшего порядка N, затем в определенной последовательности осуществляется переход к контекстным моделям меньших порядков.

Естественно, статистическое кодирование символа ухода выполняется на основании его вероятности, так называемой вероятности ухода. Очевидно, что символы ухода порождаются не источником данных, а моделью. Следовательно, их вероятность может зависеть от характеристик сжимаемых данных, свойств КМ, с которой производится уход, свойств КМ, на которую происходит уход, и т.д. Как можно оценить эту вероятность, имея в виду, что конечный критерий качества - улучшение сжатия? Вероятность ухода - это вероятность появления в контексте нового символа. Тогда, фактически, необходимо оценить правдоподобность наступления ни разу не происходившего события. Теоретического фундамента для решения этой проблемы, видимо, не существует, но за время развития техник контекстного моделирования было предложено несколько подходов, хорошо работающих в большинстве реальных ситуаций. Кроме того, эксперименты показывают, что модели с неявным взвешиванием устойчивы относительно используемого метода оценки вероятности ухода, т.е. выбор какого-то способа вычисления этой величины не влияет на коэффициент сжатия кардинальным образом.

Алгоритмы PPM

Техника контекстного моделирования Prediction by Partial Matching (предсказание по частичному совпадению), предложенная в 1984 году Клири (Cleary) и Уиттеном (Witten) [3.5], является одним из самых известных подходов к сжатию качественных данных и уж точно самым популярным среди контекстных методов. Значимость подхода обусловлена и тем фактом, что алгоритмы, причисляемые к PPM, неизменно обеспечивают в среднем наилучшее сжатие при кодировании данных различных типов и служат стандартом, "точкой отсчета" при сравнении универсальных алгоритмов сжатия.

Перед собственно рассмотрением алгоритмов PPM необходимо сделать замечание о корректности используемой терминологии. На протяжении примерно 10 лет - с середины 1980-х годов до середины 1990-х - под PPM понималась группа методов с вполне определенными характеристиками. В последние годы, вероятно из-за резкого увеличения числа всевозможных гибридных схем и активного практического использования статистических моделей для сжатия, произошло смешение понятий, и термин "PPM" часто используется для обозначения контекстных методов вообще.

Ниже будет описан некий обобщенный алгоритм PPM, а затем особенности конкретных распространенных схем.

Как и в случае многих других контекстных методов, для каждого контекста, встречаемого в обрабатываемой последовательности, создается своя контекстная модель КМ. При этом под контекстом понимается последовательность элементов одного типа - символов, пикселов, чисел, но не набор разнородных объектов. Далее вместо слова "элемент" мы будем использовать "символ". Каждая КМ включает в себя счетчики всех символов, встреченных в соответствующем контексте.

PPM относится к адаптивным методам моделирования. Исходно кодеру и декодеру поставлена в соответствие начальная модель источника данных. Будем считать, что она состоит из КМ(-1), присваивающей одинаковую вероятность всем символам алфавита входной последовательности. После обработки текущего символа кодер и декодер изменяют свои модели одинаковым образом, в частности, наращивая величину оценки вероятности рассматриваемого символа. Следующий символ кодируется (декодируется) на основании новой, измененной модели, после чего модель снова модифицируется и т.д. На каждом шаге обеспечивается идентичность модели кодера и декодера за счет применения одинакового механизма ее обновления.

В PPM используется неявное взвешивание оценок. Попытка оценки символа начинается с КМ(N), где N является параметром алгоритма и называется порядком PPM-модели. В случае нулевой частоты символа в КМ текущего порядка осуществляется переход к КМ меньшего порядка за счет использования механизма уходов (escape strategy), рассмотренного в предыдущем пункте.

Фактически, вероятность ухода - это суммарная вероятность всех символов алфавита входного потока, еще ни разу не появлявшихся в контексте. Любая КМ должна давать отличную от нуля оценку вероятности ухода. Исключения из этого правила возможны только в тех случаях, когда значения всех счетчиков КМ для всех символов алфавита отличны от нуля, то есть любой символ может быть оценен в рассматриваемом контексте. Оценка вероятности ухода традиционно является одной из основных проблем алгоритмов с неявным взвешиванием, и она будет специально рассмотрена ниже в пункте "Оценка вероятности ухода".

Вообще говоря, способ моделирования источника с помощью классических алгоритмов PPM опирается на следующие предположения о природе источника:

Таким образом, механизм уходов первоначально рассматривался лишь как вспомогательный прием, позволяющий решить проблему кодирования символов, ни разу не встречавшихся в контексте порядка N. В идеале, достигаемом после обработки достаточно длинного блока, никакого обращения к КМ порядка меньше N происходить не должно. Иначе говоря, причисление классических алгоритмов PPM к методам, производящим взвешивание, пусть и неявным образом, является не вполне корректным.

При сжатии очередного символа выполняются следующие действия.

Если символ s обрабатывается с использованием PPM-модели порядка N, то, как мы уже отмечали, в первую очередь рассматривается KM(N). Если она оценивает вероятность s числом, не равным нулю, то сама и используется для кодирования s. Иначе выдается сигнал в виде символа ухода, и на основе меньшей по порядку КМ(N-1) производится очередная попытка оценить вероятность s. Кодирование происходит через уход к КМ меньших порядков до тех пор, пока s не будет оценен. КМ(-1) гарантирует, что это в конце концов произойдет. Таким образом, каждый символ кодируется серией кодов символа ухода, за которой следует код самого символа. Из этого следует, что вероятность ухода также можно рассматривать как вероятность перехода к контекстной модели меньшего порядка.

Если в процессе оценки обнаруживается, что текущий рассматриваемый контекст встречается в первый раз, то для него создается KM(N).

При оценке вероятности символа в КМ порядка o < N можно исключить из рассмотрения все символы, которые содержатся в KM(0+1), поскольку ни один из них точно не является символом s. Для этого в текущей KM(o) нужно замаскировать, т.е. временно установить в ноль, значения счетчиков всех символов, имеющихся в КМ(o+1). Такая техника называется методом исключения (exclusion).

После собственно кодирования символа обычно осуществляется обновление статистики всех КМ, использованных при оценке его вероятности, за исключением статической КМ(-1). Такой подход называется методом исключения при обновлении. Простейшим способом модификации является инкремент счетчиков символа в этих КМ. Подробнее о стратегиях обновления будет сказано в пункте "Обновление счетчиков символов".

Пример работы алгоритма PPM

Рассмотрим подробнее работу алгоритма PPM с помощью примера.

Пример 2

Имеется последовательность символов "абвавабввбббв" алфавита {'а', 'б', 'в', 'г'}, которая уже была закодирована. (см. рис. 3.3)

Пусть счетчик символа ухода равен 1 для всех КМ, при обновлении модели счетчики символов увеличиваются на 1 во всех активных КМ, применяется метод исключения, и максимальная длина контекста равна 3, т.е. N = 3.

Первоначально модель состоит из КМ(-1), в которой счетчики всех четырех символов алфавита имеют значение 1. Состояние модели обработки последовательности "абвавабввбббв" представлено на рис. 3.4, где прямоугольниками обозначены контекстные модели, при этом для каждой КМ указан курсивом контекст, а также встречавшиеся в контексте символы и их частоты.

Пусть текущий символ равен 'г', т.е. '?' = 'г', тогда процесс его кодирования будет выглядеть следующим образом.

Сначала рассматривается контекст 3-го порядка "ббв". Ранее он не встречался, поэтому кодер, ничего не послав на выход, переходит к анализу статистики для контекста 2-го порядка. В этом контексте ("бв") встречались символ 'а' и символ 'в', счетчики которых в соответствующей КМ равны 1 каждый, поэтому символ ухода кодируется с вероятностью 1/(2+1), где в знаменателе число 2 - это наблюдавшаяся частота появления контекста "бв", 1 - это значение счетчика символа ухода. В контексте 1-го порядка "в" дважды встречался символ 'а', который исключается (маскируется), один раз также исключаемый 'в' и один раз 'б', поэтому оценка вероятности ухода будет равна 1/(1+1). В КМ(0) символ 'г' также оценить нельзя, причем все имеющиеся в этой КМ символы 'а', 'б', 'в' исключаются, так как уже встречались нам в КМ более высокого порядка. Поэтому вероятность ухода получается равной 1. Цикл оценивания завершается на уровне КМ(-1), где 'г' к этому времени остается единственным до сих пор не попадавшимся символом, поэтому он получает вероятность 1 и кодируется посредством 0 битов. Таким образом, при использовании хорошего статистического кодировщика для представления 'г' потребуется в целом примерно 2.6 бита.

Перед обработкой следующего символа создается КМ для строки "ббв" и производится модификация счетчиков символа 'г' в созданной и во всех просмотренных КМ. В данном случае требуется изменение КМ всех порядков от 0 до N.

Табл. 3.2 демонстрирует оценки вероятностей, которые должны были быть использованы при кодировании символов алфавита {'а', 'б', 'в', 'г'} в текущей позиции.

Алгоритм декодирования абсолютно симметричен алгоритму кодирования. После декодирования символа в текущей КМ проверяется, не является ли он символом ухода, если это так, то выполняется переход к КМ порядком ниже. Иначе считается, что исходный символ восстановлен, он записывается в декодированный поток и осуществляется переход к следующему шагу. Содержание процедур обновления счетчиков, создания новых контекстных моделей, прочих вспомогательных действий и последовательность их применения должны быть строго одинаковыми при кодировании и декодировании. Иначе возможна рассинхронизация копий модели кодера и декодера, что рано или поздно приведет к ошибочному декодированию какого-то символа. Начиная с этой позиции, вся оставшаяся часть сжатой последовательности будет разжата неправильно.

Разница между кодами символов, оценки вероятности которых одинаковы, достигается за счет того, что PPM-предсказатель передает кодировщику так называемые накопленные частоты (или накопленные вероятности) оцениваемого символа и его соседей или кодовые пространства символов. Так, например, для контекста "бв" из примера 2 можно составить табл. 3.3.

Хороший кодировщик должен отобразить символ s с оценкой вероятности q(s) в код длины $$\log _2 q(s)$$, что и обеспечит сжатие всей обрабатываемой последовательности в целом.

В обобщенном виде алгоритм кодирования можно записать так.

/*инициализация контекста длины N (в смысле строки предыдущих 
		символов), эта строка должна содержать N предыдущих
		символов, определяя набор активных контекстов длины o<=N
	*/

	context = "";
	while ( ! DataFile.EOF() ){
		c = DataFile.ReadSymbol(); // текущий символ
		order = N;	// текущий порядок КМ
		success = 0;	// успешность оценки в текущей КМ
		
		do{
			// найдем КМ для контекста текущей длины
			CM = ContextModel.FindModel (context, order);				
			/*попробуем найти текущий символ c в этой КМ, в 
				CumFreq получим его накопленную частоту (или 
				накопленную частоту символа ухода), в counter - 
				ссылку на счетчик символа; флаг success указывает 
				на отсутствие ухода
			*/
			success = CM.EvaluateSymbol (c, CumFreq, counter); 
			/*запомним в стеке КМ и указатель на счетчик для 
				последующего обновления модели 
			*/
			Stack.Push (CM, counter);
			// закодируем c или символ ухода
			StatCoder.Encode (CM, CumFreq, counter);
			order--;
		}while ( ! success );
		
		/*обновим модель: добавим КМ в случае необходимости, 
			изменим значения счетчиков и т.д. 
		*/
		UpdateModel (Stack);

		// обновим контекст: сдвинем влево, справа добавим c
		MoveContext (c);	
	}

Пример реализации PPM-компрессора

Рассмотрим основные моменты реализации компрессора PPM для простейшего случая с порядком модели 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. Нам требуется только распределить
		кодовое пространство в КМ(0) так, чтобы все символы, 
		включая символ ухода, всегда бы имели ненулевые оценки. 
		Пусть также символы будут равновероятными
		*/
		
		for ( int j = 0; j < 256; j++ )
			cm[256].count[j] = 1;
	
		cm[256].TotFr = 256;
	
		/*Явно запишем, что в начале моделирования мы считаем 
		контекст равным 0. Число не имеет значения, лишь бы 
		кодер и декодер точно следовали принятым 
		соглашениям. Обратите на это внимание
		*/
		
		context [0] = 0;
		SP = 0; 
	}

Функции обновления модели также будут общими для кодера и декодера. В update_model производится инкремент счетчиков просмотренных КМ, а в 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_model (int c){
		while (SP) {
			SP--;
			
			if ((stack[SP]->TotFr + stack[SP]->esc) >= MAX_TotFr) 
				rescale (stack[SP]);
			
			if (!stack[SP]->count[c])
				/*в этом контексте это новый символ, увеличим 
				счетчик уходов
				*/
			stack[SP]->esc += 1;
		
			stack[SP]->count[c] += 1;
			stack[SP]->TotFr += 1;
		}
	}

Собственно кодер реализуем функцией encode. Эта функция управляет последовательностью действий при сжатии данных, вызывая вспомогательные процедуры в требуемом порядке, а также находит нужную КМ. Оценка текущего символа производится в функции encode_sym, которая передает результаты своей работы арифметическому кодеру.

int encode_sym (ContextModel *CM, int c){
		// КМ потребует инкремента счетчиков, запомним ее
		stack [SP++] = CM;	 

		if (CM->count[c]){
			/*счетчик сжимаемого символа не равен нулю, тогда
			его можно оценить в текущей КМ; найдем 
			накопленную частоту предыдущего в массиве count 
			символа
			*/	
			
			int CumFreqUnder = 0;
			for (int i = 0; i < c; i++)
				CumFreqUnder += CM->count[i];
			
			/*передадим описание кодового пространства, 
			занимаемого символом c, арифметическому кодеру 
			*/
		
			AC.encode (CumFreqUnder, CM->count[c], 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	c,	// текущий символ
		success;	// успешность кодирования символа в КМ
		
		init_model ();
		AC.StartEncode ();		// проинициализируем арифм. кодер
		
		while (( c = DataFile.ReadSymbol() ) != EOF) {
			// попробуем закодировать в КМ(1)
			success = encode_sym (cm[context[0]], c);
		
			if (!success)
				/*уходим на КМ(0), где любой символ получит 
				ненулевую оценку и будет закодирован
				*/
				encode_sym (cm[256], c);
			
			update_model (c);
			context [0] = c; // сдвинем контекст
		}
		
		// закодируем знак конца файла символом ухода с КМ(0)	
		AC.encode (cm[context[0]].TotFr, cm[context[0]].esc, 
		cm[context[0]].TotFr + cm[context[0]].esc);
	
		AC.encode (cm[256].TotFr, cm[256].esc, 
		cm[256].TotFr + cm[256].esc);
		
		// завершим работу арифметического кодера
		AC.FinishEncode();
	}

Реализация декодера выглядит аналогично. Внимания заслуживает разве что только процедура поиска символа по описанию его кодового пространства. Метод get_freq арифметического кодера возвращает число x, лежащее в диапазоне [CumFreqUnder, CumFreqUnder+CM->count[i]), т.е. CumFreqUnder <= x < 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++;
			}
			
			/*обновим  состояние арифметического кодера на 
			основании точной накопленной частоты символа
			*/
			
			AC.decode_update (CumFreqUnder, CM->count[i], CM->TotFr + CM->esc);
			
			*c = i;
			return 1;
		}else{
			/*обновим  состояние арифметического кодера на 
			основании точной накопленной частоты символа, 
			оказавшегося символом ухода
			*/
		
			AC.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 (cm[context[0]], c);
			if (!success){
				success = decode_sym (cm[256], c);
				
				if (!success) break; //признак конца файла
			}
			
			update_model (c);
			context [0] = c;
			DataFile.WriteSymbol (c);
		}
	}

Характеристики созданного компрессора, названного Dummy, приведены в пункте "Производительность на тестовом наборе Calgary Compression Corpus". Полный текст реализации Dummy оформлен в виде приложения 1.

Оценка вероятности ухода

На долю символов ухода обычно приходится порядка 30% и более от всех оценок, вычисляемых моделировщиком PPM. Это определило пристальное внимание к проблеме оценки вероятности символов с нулевой частотой. Львиная доля публикаций, посвященных PPM, прямо касаются оценки вероятности ухода (ОВУ).

Можно выделить два подхода к решению проблемы ОВУ: априорные методы, основанные на предположениях о природе сжимаемых данных, и адаптивные методы, которые пытаются приспособить оценку к данным. Понятно, что первые призваны обеспечить хороший коэффициент сжатия при обработке типичных данных в сочетании с высокой скоростью вычислений, а вторые ориентированы на обеспечение максимально возможной степени сжатия.

Априорные методы

Введем обозначения:

C - общее число просмотров контекста, т.е. сколько раз он встретился в обработанном блоке данных;

S - количество разных символов в контексте;

$$S^{(i)}$$ - количество таких разных символов, что они встречались в контексте ровно i раз;

$$E^{(x)}$$ - значение ОВУ по методу x.

Изобретатели алгоритма PPM предложили два метода ОВУ: так называемые метод A и метод B. Использующие их алгоритмы PPM были названы PPMA и PPMB соответственно.

В дальнейшем было описано еще 5 априорных подходов к ОВУ: методы C, D, P, X и XC [8, 10, 17]. По аналогии с PPMA и PPMB, алгоритмы PPM, применяющие методы C и D, получили названия PPMC и PPMD соответственно.

Идея методов и их сравнение представлены в табл. 3.4 и табл. 3.5.

Кстати, в примере 2 был использован метод A, а в компрессоре Dummy - метод С.

При реализации метода B воздерживаются от оценки символов до тех пор, пока они не появятся в текущем контексте более одного раза. Это достигается за счет вычитания единицы из счетчиков. Методы P, X, XC базируются на предположении о том, что вероятность появления в обрабатываемых данных символа $$s_i $$ подчиняется закону Пуассона с параметром $$\lambda _i $$.

Места в табл. 3.5 очень условны. Так, например, при сжатии текстов методы XC, D, P, X показывают весьма близкие результаты, и многое зависит от порядка модели и используемых для сравнения файлов. В большинстве случаев существенным является только отставание точности ОВУ по способам A и B от других методов.

Адаптивные методы

Чтобы улучшить оценку вероятности ухода, необходимо иметь такую модель оценки, которая бы адаптировалась к обрабатываемым данным. Подобный адаптивный механизм получил название Secondary Escape Estimation (SEE), т.е. "дополнительной оценки ухода", или "вторичной оценки ухода". Метод заключается в тривиальном вычислении вероятности ухода из текущей КМ через частоту появления новых символов (или, что то же, символов ухода) в контекстных моделях со схожими характеристиками:

где $$f_i (esc)$$ - число наблюдавшихся уходов из контекстных моделей типа i ;

$$n_i$$ - число просмотров контекстных моделей типа i.

Вразумительные обоснования выбора этих характеристик и критериев "схожести" при отсутствии априорных знаний о характере сжимаемой последовательности дать сложно, поэтому известные алгоритмы адаптивной оценки базируются на эмпирическом анализе типовых данных.

Метод Z

Одна из самых ранних попыток реализации SEE известна как метод Z, а использующая его разновидность алгоритма PPM - PPMZ [3.3]. Для точности описания этой техники SEE объект "контекст" ниже будет также именоваться "PPM-контекстом".

Для нахождения ОВУ строятся так называемые контексты ухода (escape contexts) КУ, формируемые из четырех полей. В полях КУ содержится информация о значениях следующих величин: последние четыре символа PPM-контекста, порядок PPM-контекста, количество уходов и количество успешных оценок в соответствующей КМ. Нескольким КМ может соответствовать один КУ.

Информация о фактическом количестве уходов и успешных кодирований во всех контекстных моделях, имеющих общий КУ, запоминается в счетчиках контекстной модели уходов КМУ, построенной для данного КУ. Эта информация определяет ОВУ для текущей КМ. ОВУ находится путем взвешивания оценок, которые дают три КМУ (КМУ порядка 2, 1 и 0), отвечающие характеристикам текущей КМ.

КУ порядка 2 наиболее точно соответствует текущей КМ, контексты ухода порядком ниже формируются главным образом путем выбрасывания части информации из полей КУ порядка 2. Компоненты КУ порядка 2 определяются в соответствии с табл. 3.6 [3.3].

В состав КУ всех порядков входят поля 1, 2, 3. Для КУ порядка 1 поле 4 состоит из 8 битов и строится из шестых и пятых битов последних четырех обработанных символов. У КУ порядка 0 четвертое поле отсутствует. Очевидно, что алгоритм построения поля 4 для КУ порядков 1 и 2 призван улучшить предсказание ухода для текстов на английском языке в кодировке ASCII. Аналогичный прием, хотя и в не столь явном виде, используется в адаптивных методах ОВУ SEE-d1 и SEE-d2, рассмотренных ниже.

При взвешивании статистики КМУ(n) используются следующие веса $$w_n$$

$${1 \over {w_n }} = e \cdot \log _2 \left( {{1 \over e}} \right) + (1 - e) \cdot \log _2 \left( {{1 \over {1 - e}}} \right)$$,

где e - ОВУ, которую дает данная взвешиваемая КМУ(n) ; формируется из фактического количества уходов и успешных кодирований в контекстных моделях, соответствующих этой КМУ, или, иначе, определяется наблюдавшейся частотой ухода из таких КМ.

Окончательная оценка:

$$E^{(Z)} = {{\sum\limits_{n = 0}^2 {e_n w_n } } \over {\sum\limits_{n = 0}^2 {w_n } }}$$.

После ОВУ выполняется поиск текущего символа среди имеющихся в КМ. По результатам поиска (символ найден или нет) обновляются счетчики соответствующих трех КМУ порядка 0, 1 и 2.