Контекстное моделирование

Определение:

Контекстное моделирование (context modeling)— оценка вероятности появления символа (элемента, пиксела, сэмпла и даже набора качественно разных объектов) в зависимости от непосредственно ему предыдущих, или контекста.

Определение:

Если длина контекста ограничена, то такой подход будем называть контекстным моделированием ограниченного порядка (finite-context modeling), при этом под порядком понимается максимальная длина используемых контекстов [math]N[/math].

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

Контекстная модель строятся на основании обычных счетчиков частот, связанных с текущим контекстом. Если мы обработали строку [math]“кускувукус”[/math], то для контекста [math]“ку”[/math] счетчик символа «[math]c[/math]» равен двум, символ «[math]в[/math]» — единице. На основании этого статистики можно утверждать, что вероятность появления «[math]c[/math]» после [math]“ку”[/math] равна [math] \dfrac{2}{3}[/math] , а вероятность появления «[math]в[/math]» равна [math] \dfrac{1}{3}[/math], т.е. Оценки формируются на основе уже просмотренной части потока.

Определение:

Порядок контекстной модели (order context model) — длина соответствующего этой модели контекста . Если порядок [math]КМ[/math] равен [math]o[/math], то будем обозначать такую [math]КМ[/math] как [math]“КМ(o)”[/math].

Определение:

Модель с полным смешиванием (fully blended model) — модель, в которой предсказание определяется статистикой [math]KM[/math] всех используемых порядков.

Вычисление смешанной вероятности

Введем следующие обозначения:

• [math]p(s_i|o)[/math] — вероятность, присваемая в [math]КМ(о)[/math] символу [math]s_i[/math].
• [math]p(s_i)[/math] — смешанная вероятность.
• [math]f(s_i|o)[/math] — частота появления [math]s_i[/math] в соответствующем контексте порядка [math]о[/math].
• [math]f(o)[/math] — общая частота появления соответствующего контекста порядка [math]о[/math] в обработанной последовательности.
• [math]\omega(o)[/math] — вес оценки [math]КМ(о)[/math].

Оценка [math]p(s_i|o)[/math] обычно определяется через частоту символа [math]s_i[/math] по тривиальной формуле:

[math]p(s_i|o) = \dfrac{f(s_i|o)}{f(o)}[/math]

В общем случае смешанная вероятность [math]p(s_i)[/math] выселяется так:

[math]p(s_i) = \sum\limits_{о \in [-1, N]} \omega(o)\cdot p(s_i|o)[/math]

Пример

Рассмотрим процесс оценки отмеченного на рисунке стрелочкой символа [math]л[/math], встречающегося в блоке [math]“молочное[/math]_[math]молоко”[/math]

рис. 1

Будем использовать [math]КМ(2)[/math] с полным смешиванием и использованием заданного набора фиксированных весов [math]КМ[/math] разных порядков: [math]\omega(2) = 0.6[/math], [math]\omega(1) = 0.3[/math] и [math]\omega(0) = 0.1[/math]. Считаем, что в начале кодирования в [math]КМ(o)[/math] создаются счетчики для всех символов алфавита [math]\{“м”, “о”, “л”, “ч”, “н”, “е”,“\_”, “к”\}[/math] и инициализируются единицей; счетчик символа после его обработки увеличивается на единицу. Для текущего символа «[math]л[/math]» имеются контексты [math]“мо”[/math], [math]“о”[/math] и [math]“”[/math] (0-го порядка). К данному моменту для них накоплена статистика, показанная в таблице

Порядок		[math]«м»[/math]	[math]«о»[/math]	[math]«л»[/math]	[math]«ч»[/math]	[math]«н»[/math]	[math]«е»[/math]	[math]«[/math]_[math]»[/math]	[math]«к»[/math]
[math]КМ(0)[/math]	Частоты	[math]3[/math]	[math]5[/math]	[math]2[/math]	[math]2[/math]	[math]2[/math]	[math]2[/math]	[math]2[/math]	[math]1[/math]
[math]КМ(0)[/math]	Накопленные Частоты	[math]3[/math]	[math]8[/math]	[math]10[/math]	[math]12[/math]	[math]14[/math]	[math]16[/math]	[math]18[/math]	[math]19[/math]
[math]КМ(1)[/math]	Частоты	[math] — [/math]	[math] — [/math]	[math]1[/math]	[math]1[/math]	[math] — [/math]	[math]1[/math]	[math] — [/math]	[math] — [/math]
[math]КМ(1)[/math]	Накопленные Частоты	[math] — [/math]	[math] — [/math]	[math]1[/math]	[math]2[/math]	[math] — [/math]	[math]3[/math]	[math] — [/math]	[math] — [/math]
[math]КМ(2)[/math]	Частоты	[math] — [/math]	[math] — [/math]	[math]1[/math]	[math] — [/math]	[math] — [/math]	[math] — [/math]	[math] — [/math]	[math] — [/math]
[math]КМ(2)[/math]	Накопленные Частоты	[math] — [/math]	[math] — [/math]	[math]1[/math]	[math] — [/math]	[math] — [/math]	[math] — [/math]	[math] — [/math]	[math] — [/math]

Оценка вероятности для символа «[math]л[/math]» будет равна [math] p(л) = 0.1\cdot\dfrac{2}{19}+0.3\cdot\dfrac{1}{3}+0.6\cdot\dfrac{1}{1} = 0.71 [/math]

Метод неявного взвешивания

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

Метод РРМ

Описание

Определение:

Адаптивное моделирование (adaptive context modeling) — метод моделирования, при котором, по мере кодирования модель изменяется по заданному алгоритму.

Определение:

Энтропийное кодирование (entropy coding) — кодирование последовательности значений с возможностью однозначного восстановления с целью уменьшения объёма данных с помощью усреднения вероятностей появления элементов в закодированной последовательности.

Обычно термин [math]РРМ[/math] используется для обозначения контекстных методов в общем, по этой причине далее будет рассматриваться некий обобщенный алгоритм [math]РРМ[/math].

[math]РРМ[/math] (Prediction by partial matching) — адаптивный алгоритм сжатия данных без потерь, основанный на контекстном моделировании и предсказании. Исходно кодеру и декодеру поставлена в соответствие начальная модель источника данных. Будем считать, что она состоит из [math]КМ(-1)[/math], присваивающей одинаковую вероятность всем символам алфавита входной последовательности. После обработки текущего символа кодер и декодер изменяют свои модели одинаковым образом, в частности наращивая величину оценки вероятности рас­сматриваемого символа. Следующий символ кодируется (декодируется) на основании новой, измененной модели, после чего модель снова модифици­руется и т. д. На каждом шаге обеспечивается идентичность модели кодера и декодера за счет применения одинакового механизма ее обновления.

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

[math] РРМ [/math] лишь предсказывает значение символа, непосредственное сжатие осуществляется алгоритмами энтропийного кодирования, как например, алгоритм Хаффмана или арифметическое кодирование.

Пример

Кодирование

Имеется последовательность символов [math]“абвавабввбббв”[/math] алфавита [math] \{а, б, в, г\}[/math], которая уже была закодирована.

рис. 2

рис. 3

Пусть счетчик символа ухода равен единице для всех [math]КМ[/math], при обновлении модели счетчики символов увеличиваются на единицу во всех активных [math]КМ[/math], применяется метод исключения и максимальная длина контекста равна трем, т. е. [math]N = 3[/math]. Первоначально модель состоит из [math]КМ(-1)[/math], в которой счетчики всех четырех символов алфавита имеют значение [math]1[/math]. Состояние модели обработки последовательности [math]“абвавабввбббв”[/math] представлено на [math]рис. 3[/math], где прямоугольниками обозначены контекстные модели, при этом для каждой КМ указан курсивом контекст, а также встречавшиеся в контексте символы и их частоты.

[math]Символ[/math]	[math]КМ(3)[/math]	[math]КМ(2)[/math]	[math]КМ(1)[/math]	[math]КМ(0)[/math]	[math]КМ(-1)[/math]	[math]Шанс[/math]	[math]Бит[/math]
«[math]a[/math]»	[math] — [/math]	[math]\dfrac{1}{2+1}[/math]	[math] — [/math]	[math] — [/math]	[math] — [/math]	[math]\dfrac{1}{3}[/math]	[math]1.6[/math]
«[math]б[/math]»	[math] — [/math]	[math]\dfrac{1}{2+1}[/math]	[math] \dfrac{1}{1+1} [/math]	[math] — [/math]	[math] — [/math]	[math]\dfrac{1}{6}[/math]	[math]2.6[/math]
«[math]в[/math]»	[math] — [/math]	[math]\dfrac{1}{2+1}[/math]	[math] — [/math]	[math] — [/math]	[math] — [/math]	[math]\dfrac{1}{3}[/math]	[math]1.6[/math]
«[math]г[/math]»	[math] — [/math]	[math]\dfrac{1}{2+1}[/math]	[math] \dfrac{1}{1+1} [/math]	[math] 1 [/math]	[math] 1 [/math]	[math]\dfrac{1}{6}[/math]	[math]2.6[/math]

Пусть текущий символ равен «[math]г[/math]», т. е. «[math]?[/math]» = «[math]г[/math]», тогда процесс его кодирования будет выглядеть следующим образом. Сначала рассматривается контекст [math]3[/math]-го порядка [math]“ббв”[/math]. Ранее он не встре­чался, поэтому кодер, ничего не послав на выход, переходит к анализу ста­тистики для контекста [math]2[/math]-го порядка. В этом контексте ([math]“бв”[/math]) встречались символ «[math]а[/math]» и символ «[math]в[/math]», счетчики которых в соответствующей [math]КМ[/math] равны [math]1[/math] каждый, поэтому символ ухода кодируется с вероятностью [math]\dfrac{1}{2+1}[/math], где в знаменателе число [math]2[/math] — наблюдавшаяся частота появления контекста [math]“бв”[/math], [math]1[/math] — значение счетчика символа ухода. В контексте [math]1[/math]-го порядка «[math]в[/math]» дважды встречался символ «[math]а[/math]», который исключается (маскируется), один раз также исключаемый «[math]в[/math]» и один раз «[math]б[/math]», поэтому оценка вероятности ухода будет равна [math]\dfrac{1}{1+1}[/math]. В [math]КМ(0)[/math] символ «[math]г[/math]» также оценить нельзя, при­чем все имеющиеся в этой [math]КМ[/math] символы «[math]а[/math]», «[math]б[/math]», «[math]в[/math]» исключаются, так как уже встречались нам в [math]КМ[/math] более высокого порядка. Поэтому вероятность ухода получается равной единице. Цикл оценивания завершается на уровне [math]КМ(-1)[/math], где «[math]г[/math]» к этому времени остается единственным до сих пор не попавшимся символом, поэтому он получает вероятность [math]1[/math] и кодируется посредством [math]0[/math] бит. Таким образом, при использовании хорошего статисти­ческого кодировщика для представления «[math]г[/math]» потребуется в целом примерно [math]2.6[/math] бит. Перед обработкой следующего символа создается [math]КМ[/math] для строки [math]“ббв”[/math] и производится модификация счетчиков символа «[math]г[/math]» в созданной и во всех просмотренных [math]КМ[/math]. В данном случае требуется изменение [math]КМ[/math] всех порядков от [math]0[/math] до [math]N[/math].

Декодирование

Алгоритм декодирования абсолютно симметричен алгоритму кодирования. После декодирования символа в текущей [math]КМ[/math] проверяется, не является ли он символом ухода; если это так, то выполняется переход к [math]КМ[/math] порядком ниже. Иначе считается, что исходный символ восстановлен, он записывается в декодированный поток и осуществляется переход к следующему шагу. Содержание процедур обновления счетчиков, создания новых контекстных моделей, прочих вспомогательных действий и последовательность их применения должны быть строго одинаковыми при кодировании и деко­дировании. Иначе возможна рассинхронизация копий модели кодера и де­кодера, что рано или поздно приведет к ошибочному декодированию како­го-то символа. Начиная с этой позиции вся оставшаяся часть сжатой после­довательности будет разжата неправильно. Разница между кодами символов, оценки вероятности которых одинако­вы, достигается за счет того, что [math]РРМ[/math]-предсказатель передает кодировщику так называемые накопленные частоты (или накопленные вероятности) оце­ниваемого символа и его соседей или кодовые пространства символов. Так, например, для контекста [math]“бв”[/math] можно составить следующую таблицу:

[math]Символ[/math]	[math]Частота[/math]	[math]Оценка\ вероятности[/math]	[math]Накопительная\ оценка[/math]	[math]Кодовое\ пространство[/math]
«[math]а[/math]»	[math] 0 [/math]	[math] — [/math]	[math] — [/math]	[math] — [/math]
«[math]б[/math]»	[math] 1 [/math]	[math]\dfrac{1}{3}[/math]	[math]\dfrac{1}{3}[/math]	[math] [0\ldots0.33) [/math]
«[math]в[/math]»	[math] 1 [/math]	[math]\dfrac{1}{3}[/math]	[math]\dfrac{2}{3}[/math]	[math] [0.33\ldots0.66) [/math]
«[math]г[/math]»	[math] 0 [/math]	[math] — [/math]	[math] — [/math]	[math] — [/math]
«[math]esc[/math]»	[math] 1 [/math]	[math]\dfrac{1}{3}[/math]	[math]1[/math]	[math] [0.66\ldots1) [/math]

Хороший кодировщик должен отобразить символ «[math]s[/math]» с оценкой вероят­ности [math]p(s)[/math] в код длины [math]\log_2 p(s)[/math], что и обеспечит сжатие всей обрабатывае­мой последовательности в целом.

Проблема нулевой частоты

Определение:

Проблема нулевой частоты (zero frequency problem) — проблема обработки новых символов, ещё не встречавшихся во входном потоке.

На сегодняшний день можно выделить два подхода к решению этой проблемы: априорные методы, основанные на предположениях о природе сжимаемых данных, и адаптивные методы, которые пытаются приспособиться к сжимаемым данным.

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

Выедем следующие обозначения:

• [math]С[/math] — общее число просмотров контекста
• [math]Q[/math] — количество разных символов в контексте
• [math]Q_i[/math] — количество таких разных символов, что они встречались в контексте ровно [math]i[/math] раз
• [math]Esc_x[/math] — [math]ОВУ[/math](оценка вероятности кода ухода) по методу [math]x[/math]

Изобретатели алгоритма [math]РРМ[/math] предложили два метода [math]ОВУ[/math]: так называемые метод [math]A[/math] и метод [math]B[/math]. Частные случаи алгоритма [math]РРМ[/math] с использованием этих методов называются, соответственно, [math] PPMA [/math] и [math] PPMB [/math].

[math]PPMA:\ Esc_A = \dfrac{1}{С + 1}[/math]

[math]PPMB:\ Esc_B = \dfrac{Q - Q_1}{С}[/math]

Затем был разработан метод [math]С[/math], а в след за ним метод [math]D[/math]:

[math]PPMC:\ Esc_C = \dfrac{Q}{С + Q}[/math]

[math]PPMD:\ Esc_D = \dfrac{Q}{2\cdotС}[/math]

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

Определение:

SEE (Secondary Escape Estimation) — модель оценки, которая адаптируется к обрабатываемым данным.

Для нахождения [math]ОВУ[/math] строятся [math]контексты\ ухода[/math] (Escape Context), формируемые из различный полей. Всего используется [math]4[/math] поля, в которых содержится информация о:

• порядке [math]РРМ-[/math]контекста
• количестве уходов
• количестве успешных кодирований
• последних двух символах [math]РРМ-[/math]контекста

[math]ОВУ[/math] для текущего контекста находится путем взвешивания оценок, которые дают три контекста ухода ([math]order-2\ EC[/math], [math]order-1\ EC[/math], [math]order-0\ EC[/math]), соответствующие текущему [math]РРМ-[/math]контексту. [math]Order-2\ EC[/math] наиболее точно соответствует текущему контексту, контексты ухода порядком ниже формируются путем выбрасывания части информации полей [math]order-2\ EC[/math]. При взвешивании контекстов ухода используются следующие веса [math]w[/math]:

[math]\dfrac{1}{w} = p \cdot log_2 \dfrac{1}{p} + (1 - p) \cdot log_2 \dfrac{1}{1 - p}[/math], где [math]p - ОВУ[/math], которую дает данный взвешиваемый контекст.

Величину, которая формируется из фактического количества успешных кодирований и количества уходов в [math]PPM[/math]-контекстах, соответствующих этому [math]EC[/math] обозначим как [math]p_i[/math].

[math]PPMZ:\ Esc_z = \dfrac{\sum\limits_{i \in [0, 2]} w_{i}\cdot p_{i}}{\sum\limits_{i \in [0, 2]} w_{i}}[/math]

См. также

• Алгоритм LZMA
• Алгоритм Хаффмана
• Арифметическое кодирование

Источники информации

• The design and analysis of efficient lossless data compression systems
• Introduction to Data Compression
• Prediction by partial matching
• PPM one step to practicality
• Методы сжатия данных