Контекстное моделирование
| Определение: |
| Контекстное моделирование — оценка вероятности появления символа (элемента, пиксела, сэмпла и даже набора качественно разных объектов) в зависимости от непосредственно ему предыдущих, или контекста. |
| Определение: |
| Если длина контекста ограничена, то такой подход будем называть контекстным моделированием ограниченного порядка (finite-context modeling), при этом под порядком понимается максимальная длина используемых контекстов . |
Содержание
Оценка вероятности
Оценки вероятностей при контекстном моделировании строятся на основании обычных счетчиков частот, связанных с текущим контекстом. Если мы обработали строку , то для контекста счетчик символа равен двум, символ — единице. На основании этого статистики можно утверждать, что вероятность появления после равна , а вероятность появления равна , т.е. Оценки формируются на основе уже просмотренной части потока.
| Определение: |
| Порядок контекстной модели — длина соответствующего этой модели контекста . Если порядок равен , то будем обозначать такую как |
Пример
Рассмотрим процесс оценки отмеченного на рисунке стрелочкой символа , встречающегося в блоке _
Пусть мы используем контекстное моделирование порядка и делаем полное смешивание оценок распределений вероятностей в второго первого и нулевого порядка с весами , и . Считаем, что в начале кодирования в создаются счетчики для всех символов алфавита и инициализируются единицей; счетчик символа после его обработки увеличивается на единицу. Для текущего символа имеются контексты , и (0-го порядка). К данному моменту для них накоплена статистика, показанная в таблице
| Порядок | _ | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Частоты | |||||||||
| Накопленные Частоты | |||||||||
| Частоты | |||||||||
| Накопленные Частоты | |||||||||
| Частоты | |||||||||
| Накопленные Частоты |
Оценка вероятности для символа будет равна
Метод PPM
Описание
(Prediction by partial matching) относится к адаптивным методам моделирования. Исходно кодеру и декодеру поставлена в соответствие начальная модель источника данных. Будем считать, что она состоит из , присваивающей одинаковую вероятность всем символам алфавита входной последовательности. После обработки текущего символа кодер и декодер изменяют свои модели одинаковым образом, в частности наращивая величину оценки вероятности рассматриваемого символа. Следующий символ кодируется (декодируется) на основании новой, измененной модели, после чего модель снова модифицируется и т. д. На каждом шаге обеспечивается идентичность модели кодера и декодера за счет применения одинакового механизма ее обновления.
Пример
Кодирование
Имеется последовательность символов алфавита , которая уже была закодирована.
Пусть счетчик символа ухода равен единице для всех , при обновлении модели счетчики символов увеличиваются на единицу во всех активных , применяется метод исключения и максимальная длина контекста равна трем, т. е. . Первоначально модель состоит из , в которой счетчики всех четырех символов алфавита имеют значение . Состояние модели обработки последовательности представлено на , где прямоугольниками обозначены контекстные модели, при этом для каждой КМ указан курсивом контекст, а также встречавшиеся в контексте символы и их частоты.
Пусть текущий символ равен , т. е. = , тогда процесс его кодирования будет выглядеть следующим образом. Сначала рассматривается контекст -го порядка . Ранее он не встречался, поэтому кодер, ничего не послав на выход, переходит к анализу статистики для контекста -го порядка. В этом контексте () встречались символ и символ , счетчики которых в соответствующей равны каждый, поэтому символ ухода кодируется с вероятностью , где в знаменателе число — наблюдавшаяся частота появления контекста , — значение счетчика символа ухода. В контексте -го порядка дважды встречался символ , который исключается (маскируется), один раз также исключаемый и один раз , поэтому оценка вероятности ухода будет равна . В символ также оценить нельзя, причем все имеющиеся в этой символы , , исключаются, так как уже встречались нам в более высокого порядка. Поэтому вероятность ухода получается равной единице. Цикл оценивания завершается на уровне , где к этому времени остается единственным до сих пор не попавшимся символом, поэтому он получает вероятность и кодируется посредством . Таким образом, при использовании хорошего статистического кодировщика для представления потребуется в целом примерно . Перед обработкой следующего символа создается для строки и производится модификация счетчиков символа в созданной и во всех просмотренных . В данном случае требуется изменение всех порядков от до .
Декодирование
Алгоритм декодирования абсолютно симметричен алгоритму кодирования. После декодирования символа в текущей КМ проверяется, не является ли он символом ухода;, если это так, то выполняется переход к КМ порядком ниже. Иначе считается, что исходный символ восстановлен, он записывается в декодированный поток и осуществляется переход к следующему шагу. Содержание процедур обновления счетчиков, создания новых контекстных моделей, прочих вспомогательных действий и последовательность их применения должны быть строго одинаковыми при кодировании и декодировании. Иначе возможна рассинхронизация копий модели кодера и декодера, что рано или поздно приведет к ошибочному декодированию какого-то символа. Начиная с этой позиции вся оставшаяся часть сжатой последовательности будет разжата неправильно. Разница между кодами символов, оценки вероятности которых одинаковы, достигается за счет того, что РРМ-предсказатель передает кодировщику так называемые накопленные частоты (или накопленные вероятности) оцениваемого символа и его соседей или кодовые пространства символов. Так, например, для контекста "бв" из примера 2 можно составить табл. 4.3. Хороший кодировщик должен отобразить символ 'У с оценкой вероятности q(s) в код длины \og2q{s), что и обеспечит сжатие всей обрабатываемой последовательности в целом.
