Контекстное моделирование — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Метки: правка с мобильного устройства, правка из мобильной версии)
(Дописан пример декодирования для PPM)
(Метки: правка с мобильного устройства, правка из мобильной версии)
Строка 101: Строка 101:
 
===Пример===
 
===Пример===
 
====Кодирование====
 
====Кодирование====
Имеется последовательность символов <tex>“абвавабввбббв”</tex> алфавита <tex> \{“а”, “б”, “в”, “г”\}</tex>, которая уже была ''закодирована''.  
+
Имеется последовательность символов <tex>“абвавабввбббв”</tex> алфавита <tex> \{а, б, в, г\}</tex>, которая уже была ''закодирована''.  
 
[[Файл: Qq.png|350px|thumb|right|рис. 2]]
 
[[Файл: Qq.png|350px|thumb|right|рис. 2]]
 
[[Файл: PpmPart.png|350px|thumb|right|рис. 3]]
 
[[Файл: PpmPart.png|350px|thumb|right|рис. 3]]
Строка 156: Строка 156:
 
Перед обработкой следующего символа создается <tex>КМ</tex> для строки <tex>“ббв”</tex> и производится модификация счетчиков символа <tex>г</tex> в созданной и во всех просмотренных <tex>КМ</tex>. В данном случае требуется изменение <tex>КМ</tex> всех порядков от <tex>0</tex> до <tex>N</tex>.
 
Перед обработкой следующего символа создается <tex>КМ</tex> для строки <tex>“ббв”</tex> и производится модификация счетчиков символа <tex>г</tex> в созданной и во всех просмотренных <tex>КМ</tex>. В данном случае требуется изменение <tex>КМ</tex> всех порядков от <tex>0</tex> до <tex>N</tex>.
 
====Декодирование====
 
====Декодирование====
Алгоритм декодирования абсолютно симметричен алгоритму кодирова­ния. После декодирования символа в текущей КМ проверяется, не является ли он символом ухода;, если это так, то выполняется переход к КМ поряд­ком ниже. Иначе считается, что исходный символ восстановлен, он записывается в декодированный поток и осуществляется переход к следующему шагу. Содержание процедур обновления счетчиков, создания новых кон­текстных моделей, прочих вспомогательных действий и последовательность их применения должны быть строго одинаковыми при кодировании и деко­дировании. Иначе возможна рассинхронизация копий модели кодера и де­кодера, что рано или поздно приведет к ошибочному декодированию како­го-то символа. Начиная с этой позиции вся оставшаяся часть сжатой после­довательности будет разжата неправильно.   
+
Алгоритм декодирования ''абсолютно'' симметричен алгоритму кодирования. После декодирования символа в текущей <tex>КМ</tex> проверяется, не является ли он ''символом ухода''; если это так, то выполняется переход к <tex>КМ</tex> порядком ниже. Иначе считается, что исходный символ ''восстановлен'', он ''записывается'' в декодированный поток и осуществляется переход к следующему шагу. Содержание процедур обновления счетчиков, создания новых ''контекстных моделей'', прочих вспомогательных действий и последовательность их применения должны быть строго одинаковыми при кодировании и деко­дировании. Иначе возможна рассинхронизация копий модели кодера и де­кодера, что рано или поздно приведет к ошибочному декодированию како­го-то символа. Начиная с этой позиции вся оставшаяся часть сжатой после­довательности будет разжата неправильно.   
Разница между кодами символов, оценки вероятности которых одинако­вы, достигается за счет того, что РРМ-предсказатель передает кодировщику так называемые накопленные частоты (или накопленные вероятности) оце­ниваемого символа и его соседей или кодовые пространства символов.  
+
Разница между кодами символов, оценки вероятности которых одинако­вы, достигается за счет того, что <tex>РРМ</tex>-предсказатель передает кодировщику так называемые накопленные частоты (или накопленные вероятности) оце­ниваемого символа и его соседей или кодовые пространства символов.  
Так, например, для контекста "бв" из примера 2 можно составить табл. 4.3.
+
Так, например, для контекста <tex>“бв”</tex> можно составить следующую таблицу:
Хороший кодировщик должен отобразить символ 'У с оценкой вероят­ности q(s) в код длины \og2q{s), что и обеспечит сжатие всей обрабатывае­мой последовательности в целом.
 
 
{| style="background-color:#CCC;margin:0.5px; right"
 
{| style="background-color:#CCC;margin:0.5px; right"
 
!style="background-color:#EEE"| <tex>Символ</tex>
 
!style="background-color:#EEE"| <tex>Символ</tex>
Строка 165: Строка 164:
 
!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:#EEE"| <tex>Кодовое\ пространство</tex>
 
|-
 
|-
 
|style="background-color:#FFF;padding:2px 30px"| <tex>a</tex>
 
|style="background-color:#FFF;padding:2px 30px"| <tex>a</tex>
Строка 197: Строка 196:
 
|style="background-color:#FFF;padding:2px 60px"| <tex> [0.66 ... 1) </tex>
 
|style="background-color:#FFF;padding:2px 60px"| <tex> [0.66 ... 1) </tex>
 
|}
 
|}
 +
Хороший кодировщик должен отобразить символ <tex>s</tex> с оценкой вероят­ности <tex>q(s)</tex> в код длины <tex>\log_2 q(s)</tex>, что и обеспечит сжатие всей обрабатывае­мой последовательности в целом.

Версия 19:32, 31 декабря 2018

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


Определение:
Если длина контекста ограничена, то такой подход будем называть контекстным моделированием ограниченного порядка (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], т.е. Оценки формируются на основе уже просмотренной части потока.

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

Пример

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

рис. 1

Пусть мы используем контекстное моделирование порядка [math]2[/math] и делаем полное смешивание оценок распределений вероятностей в [math]КМ[/math] второго первого и нулевого порядка с весами [math]0.6[/math], [math]0.3[/math] и [math]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] q(л) = 0.1*\dfrac{2}{19}+0.3*\dfrac{1}{3}+0.6*\dfrac{1}{1} = 0.71 [/math]

Метод PPM

Описание

[math]РРМ[/math] (Prediction by partial matching) относится к адаптивным методам моделирования. Исходно кодеру и декодеру поставлена в соответствие начальная модель источника данных. Будем считать, что она состоит из [math]КМ(-1)[/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]a[/math] [math] 1 [/math] [math]\dfrac{1}{3}[/math] [math]\dfrac{1}{3}[/math] [math] [0 ... 0.33) [/math]
[math]б[/math] [math] 0 [/math] [math] — [/math] [math] — [/math] [math] — [/math]
[math]в[/math] [math] 1 [/math] [math]\dfrac{1}{3}[/math] [math]\dfrac{2}{3}[/math] [math] [0.33 ... 0.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 ... 1) [/math]

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