23
правки
Изменения
исправлены замечания куратора
{{Определение
|definition=
'''''Контекстное моделирование''''' (''context modeling'')— ''оценка вероятности появления символа'' (элемента, пиксела, сэмпла и даже набора качественно разных объектов) в ''зависимости'' от непосредственно ему предыдущих, или контекста.
}}
{{Определение
}}
===Оценка вероятности===
{{Определение
|definition=
'''''Порядок контекстной модели''''' (''order context model'') — длина соответствующего этой модели контекста . Если порядок <tex>КМ</tex> равен <tex>o</tex>, то будем обозначать такую <tex>КМ</tex> как <tex>“КМ(o)”</tex>.
}}
{{Определение |definition='''''Модель с полным смешиванием''''' (''fully blended model'') — модель, в которой предсказание определяется статистикой <tex>KM</tex> всех используемых порядков.}}====Вычисление смешанной вероятности====Введем следующие обозначения:*<tex>p(s_i|o)</tex> — вероятность, присваемая в <tex>КМ(о)</tex> символу <tex>s_i</tex>.*<tex>p(s_i)</tex> — смешанная вероятность.*<tex>f(s_i|o)</tex> — частота появления <tex>s_i</tex> в соответствующем контексте порядка <tex>о</tex>.*<tex>f(o)</tex> — общая частота появления соответствующего контекста порядка <tex>о</tex> в обработанной последовательности.*<tex>\omega(o)</tex> — вес оценки <tex>КМ(о)</tex>. Оценка <tex>p(s_i|o)</tex> обычно определяется через частоту символа <tex>s_i</tex> по тривиальной формуле: <tex>p(s_i|o) = \dfrac{f(s_i|o)}{f(o)}</tex> В общем случае смешанная вероятность <tex>p(s_i)</tex> выселяется так: <tex>p(s_i) = \sum\limits_{о \in [-1, N]} \omega(o)\cdot p(s_i|o)</tex>====Пример====
Рассмотрим процесс оценки отмеченного на рисунке стрелочкой символа <tex>л</tex>, встречающегося в блоке <tex>“молочное</tex>'''''_'''''<tex>молоко”</tex>
[[Файл: milk.png|350px|thumb|right|рис. 1]]
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| Порядок
|style="background-color:#FFF;padding:2px 30px"| <tex> — </tex>
|}
Оценка вероятности для символа <tex>л</tex> будет равна <tex> qp(л) = 0.1\cdot\dfrac{2}{19}+0.3\cdot\dfrac{1}{3}+0.6\cdot\dfrac{1}{1} = 0.71 </tex>====Метод неявного взвешивания====''Метод неявного взвешивания'' связана с введением вспомогательного '''''символа ухода''''' (''escape''). ''Символ ухода'' не принадлежит к алфавиту сжимаемой последовательности. Фактически он используется для передачи ''декодеру'' указаний ''кодера''. Идея заключается в том, что если используемая <tex>КМ</tex> не позволяет оценить текущий символ (его счетчик равен нулю в этой <tex>КМ</tex>), то на выход посылается закодированный ''символ ухода'' и производится попытка ''оценить'' текущий символ в другой <tex>КМ</tex>, которой соответствует контекст иной длины. Обычно попытка оценки начинается с <tex>КМ</tex> наибольшего порядка <tex>N</tex>, затем в определенной последовательности осуществляется переход к контекстным моделям меньших порядков.
==Метод PPM==
===Описание===
{{Определение
|definition=
'''''Адаптивное моделирование''''' (''adaptive context modeling'') — метод моделирования, при котором, по мере кодирования модель изменяется по заданному алгоритму.
}}
<tex>РРМ</tex> (''Prediction by partial matching'') относится к ''адаптивным'' методам моделирования. Исходно кодеру и декодеру поставлена в соответствие ''начальная'' модель источника данных. Будем считать, что она состоит из <tex>КМ(-1)</tex>, присваивающей одинаковую вероятность всем символам алфавита входной последовательности. После обработки текущего символа кодер и декодер изменяют свои модели одинаковым образом, в частности ''наращивая'' величину оценки вероятности рассматриваемого символа. Следующий символ кодируется (декодируется) на основании новой, измененной модели, после чего модель снова модифицируется и т. д. На каждом шаге обеспечивается ''идентичность'' модели кодера и декодера за счет применения одинакового механизма ее обновления.
Если символ <tex>s</tex> обрабатывается при помощи <tex>РРМ</tex>, то, в первую очередь рассматривается <tex>KM(N)</tex>. Если она оценивает вероятность <tex>s</tex> числом, не равным нулю, то сама и используется для кодирования <tex>s</tex>. Иначе выдается сигнал в виде символа ухода, и на основе меньшей по порядку <tex>KM(N-1)</tex> производится очередная попытка оценить вероятность <tex>s</tex>. Кодирование происходит через уход к <tex>КМ</tex> меньших порядков до тех пор, пока <tex>s</tex> не будет оценен. <tex>КМ(-1)</tex> гарантирует, что это в конце концов произойдет. Таким образом, каждый символ кодируется серией кодов символа ухода, за которой следует код самого символа. Из этого следует, что вероятность ухода также можно рассматривать как вероятность перехода к контекстной модели меньшего порядка.
===Пример===
====Кодирование====
|style="background-color:#FFF;padding:2px 90px"| <tex>\dfrac{1}{3}</tex>
|style="background-color:#FFF;padding:2px 90px"| <tex>\dfrac{1}{3}</tex>
|style="background-color:#FFF;padding:2px 60px"| <tex> [0 ... 0\ldots0.33) </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>в</tex>
|style="background-color:#FFF;padding:2px 90px"| <tex>\dfrac{1}{3}</tex>
|style="background-color:#FFF;padding:2px 90px"| <tex>\dfrac{2}{3}</tex>
|style="background-color:#FFF;padding:2px 60px"| <tex> [0.33 ... 0\ldots0.66) </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>г</tex>
|style="background-color:#FFF;padding:2px 90px"| <tex>\dfrac{1}{3}</tex>
|style="background-color:#FFF;padding:2px 90px"| <tex>1</tex>
|style="background-color:#FFF;padding:2px 60px"| <tex> [0.66 ... 1\ldots1) </tex>
|}
Хороший кодировщик должен отобразить символ <tex>s</tex> с оценкой вероятности <tex>qp(s)</tex> в код длины <tex>\log_2 qp(s)</tex>, что и обеспечит сжатие всей обрабатываемой последовательности в целом.
==Проблема нулевой частоты==
{{Определение
|definition=
'''''Проблема нулевой частоты''''' (''zero frequency problem'') — проблема обработки новых символов, ещё не встречавшихся во входном потоке.
}}
На сегодняшний день можно выделить ''два'' подхода к решению этой проблемы: ''априорные'' методы, основанные на предположениях о природе сжимаемых данных, и ''адаптивные методы'', которые пытаются приспособиться к сжимаемым данным.
===Априорные методы===
Изобретатели алгоритма PPM предложили два метода ОВУ: так называемые метод A и метод B. Частные случаи алгоритма PPM с использованием этих методов называются, соответственно, PPMA и PPMB.
<tex>PPMC:\ Esc_C = \dfrac{Q}{С + Q}</tex>
<tex>PPMD:\ Esc_D = \dfrac{Q}{2*С\cdotС}</tex>
===Адаптивные методы===
{{Определение
|definition=
}}
Для нахождения <tex>ОВУ</tex> строятся <tex>контексты\ ухода</tex> (''Escape Context''), формируемые из различный полей. Всего используется <tex>4</tex> поля, в которых содержится информация о:
{{Определение
|definition=
'''''<tex>p_i</tex> ''''' формируется из фактического количества успешных кодирований и количества уходов в <tex>PPM</tex>-контекстах, соответствующих этому <tex>EC</tex>.
}}
<tex>PPMZ:\ Esc_z = \dfrac{\sum\limits_{i \in [0, 2]} w_{i}\cdot p_{i}}{\sum\limits_{i \in [0, 2]} w_{i}}</tex>
