23
правки
Изменения
Нет описания правки
==Метод PPM==
===Описание===
<tex>РРМ</tex> (''Prediction by partial matching'') относится к ''адаптивным'' методам моделирования. Исходно кодеру и декодеру поставлена в соответствие ''начальная'' модель источника данных. Будем считать, что она состоит из <tex>КМ(-1)</tex>, присваивающей одинаковую вероятность всем символам алфавита входной последовательности. После обработки текущего символа кодер и декодер изменяют свои модели одинаковым образом, в частности ''наращивая'' величину оценки вероятности рассматриваемого символа. Следующий символ кодируется (декодируется) на основании новой, измененной модели, после чего модель снова модифицируется и т. д. На каждом шаге обеспечивается ''идентичность'' модели кодера и декодера за счет применения одинакового механизма ее обновления.
===Пример===
====Кодирование====
Имеется последовательность символов <tex>“абвавабввбббв”</tex> алфавита <tex> \{“а”, “б”, “в”, “г”\}</tex>, которая уже была ''закодирована''.
[[Файл: Qq.png|350px|thumb|right|рис. 2]]
Сначала рассматривается контекст <tex>3</tex>-го порядка <tex>“ббв”</tex>. Ранее он не встречался, поэтому кодер, ничего не послав на выход, переходит к анализу статистики для контекста <tex>2</tex>-го порядка. В этом контексте (<tex>“бв”</tex>) встречались символ <tex>а</tex> и символ <tex>в</tex>, счетчики которых в соответствующей <tex>КМ</tex> равны <tex>1</tex> каждый, поэтому ''символ ухода'' кодируется с вероятностью <tex>\dfrac{1}{2+1}</tex>, где в знаменателе число <tex>2</tex> — наблюдавшаяся частота появления контекста <tex>“бв”</tex>, <tex>1</tex> — значение счетчика ''символа ухода''. В контексте <tex>1</tex>-го порядка <tex>в</tex> дважды встречался символ <tex>а</tex>, который исключается (маскируется), один раз также исключаемый <tex>в</tex> и один раз <tex>б</tex>, поэтому оценка вероятности ухода будет ''равна'' <tex>\dfrac{1}{1+1}</tex>. В <tex>КМ(0)</tex> символ <tex>г</tex> также оценить ''нельзя'', причем все имеющиеся в этой <tex>КМ</tex> символы <tex>а</tex>, <tex>б</tex>, <tex>в</tex> исключаются, так как уже встречались нам в <tex>КМ</tex> более высокого порядка. Поэтому вероятность ухода получается равной ''единице''. Цикл оценивания завершается на уровне <tex>КМ(-1)</tex>, где <tex>г</tex> к этому времени остается ''единственным'' до сих пор не попавшимся символом, поэтому он получает вероятность <tex>1</tex> и кодируется посредством <tex>0\ бит</tex>. Таким образом, при использовании хорошего статистического кодировщика для представления <tex>г</tex> потребуется в целом примерно <tex>2.6\ бит</tex>.
Перед обработкой следующего символа создается <tex>КМ</tex> для строки <tex>“ббв”</tex> и производится модификация счетчиков символа <tex>г</tex> в созданной и во всех просмотренных <tex>КМ</tex>. В данном случае требуется изменение <tex>КМ</tex> всех порядков от <tex>0</tex> до <tex>N</tex>.
====Декодирование====
Алгоритм декодирования абсолютно симметричен алгоритму кодирования. После декодирования символа в текущей КМ проверяется, не является ли он символом ухода;, если это так, то выполняется переход к КМ порядком ниже. Иначе считается, что исходный символ восстановлен, он записывается в декодированный поток и осуществляется переход к следующему шагу. Содержание процедур обновления счетчиков, создания новых контекстных моделей, прочих вспомогательных действий и последовательность их применения должны быть строго одинаковыми при кодировании и декодировании. Иначе возможна рассинхронизация копий модели кодера и декодера, что рано или поздно приведет к ошибочному декодированию какого-то символа. Начиная с этой позиции вся оставшаяся часть сжатой последовательности будет разжата неправильно.
Разница между кодами символов, оценки вероятности которых одинаковы, достигается за счет того, что РРМ-предсказатель передает кодировщику так называемые накопленные частоты (или накопленные вероятности) оцениваемого символа и его соседей или кодовые пространства символов.
Так, например, для контекста "бв" из примера 2 можно составить табл. 4.3.
Хороший кодировщик должен отобразить символ 'У с оценкой вероятности q(s) в код длины \og2q{s), что и обеспечит сжатие всей обрабатываемой последовательности в целом.
{| style="background-color:#CCC;margin:0.5px; right"
!style="background-color:#EEE"| <tex>Символ</tex>
!style="background-color:#EEE"| <tex>Частота</tex>
!style="background-color:#EEE"| <tex>Оценка\ вероятности</tex>
!style="background-color:#EEE"| <tex>Накопительная\ оценка</tex>
!style="background-color:#EEE"| <tex>Кодовое пространство</tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>a</tex>
|style="background-color:#FFF;padding:2px 30px"| <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.33) </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>б</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex> 0 </tex>
|style="background-color:#FFF;padding:2px 90px"| <tex> — </tex>
|style="background-color:#FFF;padding:2px 90px"| <tex> — </tex>
|style="background-color:#FFF;padding:2px 60px"| <tex> — </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>в</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex> 1 </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.66) </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>г</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex> 0 </tex>
|style="background-color:#FFF;padding:2px 90px"| <tex> — </tex>
|style="background-color:#FFF;padding:2px 90px"| <tex> — </tex>
|style="background-color:#FFF;padding:2px 60px"| <tex> — </tex>
|-
|style="background-color:#FFF;padding:2px 23px"| <tex>esc</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex> 1 </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) </tex>
|}
