23
правки
Изменения
Добавлена проблема нулевой частоты, источники информации, см. также, пример декодирования PPM, а так же исправлены небольшие ошибки
}}
===Оценка вероятности===
Оценки вероятностей при контекстном моделировании строятся на основании ''обычных счетчиков частот'', связанных с текущим контекстом. Если мы обработали строку <tex>“кускувукус”</tex>, то для контекста <tex>“ку”</tex> счетчик символа <tex>c</tex> равен ''двум'', символ <tex>в</tex> — ''единице''. На основании этого статистики можно утверждать, что вероятность появления <tex>c</tex> после <tex>“ку”</tex> равна <tex> \dfrac{2}{3}</tex> , а вероятность появления <tex>в</tex> равна <tex> \dfrac{1}{3}</tex>, т.е. Оценки формируются на основе уже просмотренной части потока.
{{Определение
|definition=
|style="background-color:#FFF;padding:2px 30px"| <tex> — </tex>
|}
Оценка вероятности для символа <tex>л</tex> будет равна <tex> q(л) = 0.1*\cdot\dfrac{2}{19}+0.3*\cdot\dfrac{1}{3}+0.6*\cdot\dfrac{1}{1} = 0.71 </tex>
==Метод PPM==
===Описание===
!style="background-color:#EEE"| <tex>Кодовое\ пространство</tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>aа</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{1}{3}</tex>
|style="background-color:#FFF;padding:2px 60px"| <tex> [0 ... 0.33) </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>в</tex>
|}
Хороший кодировщик должен отобразить символ <tex>s</tex> с оценкой вероятности <tex>q(s)</tex> в код длины <tex>\log_2 q(s)</tex>, что и обеспечит сжатие всей обрабатываемой последовательности в целом.
==Проблема нулевой частоты==
{{Определение
|definition=
'''''Проблема нулевой частоты''''' (''zero frequency problem'') — проблема обработки новых символов, ещё не встречавшихся во входном потоке
}}
На сегодняшний день можно выделить ''два'' подхода к решению этой проблемы: ''априорные'' методы, основанные на предположениях о природе сжимаемых данных, и ''адаптивные методы'', которые пытаются приспособиться к сжимаемым данным.
===Априорные методы===
{{Определение
|definition=
<tex>С</tex> — общее число просмотров контекста
<tex>Q</tex> — количество разных символов в контексте
<tex>Q_i</tex> — количество таких разных символов, что они встречались в контексте ровно <tex>i</tex> раз
<tex>Esc_x</tex> — <tex>ОВУ</tex>(''оценка вероятности кода ухода'') по методу <tex>x</tex>
}}
Изобретатели алгоритма PPM предложили два метода ОВУ: так называемые метод A и метод B. Частные случаи алгоритма PPM с использованием этих методов называются, соответственно, PPMA и PPMB.
<tex>PPMA:\ Esc_A = \dfrac{1}{С + 1}</tex>
<tex>PPMB:\ Esc_B = \dfrac{Q - Q_1}{С}</tex>
Затем был разработан метод С, а в след за ним метод D:
<tex>PPMC:\ Esc_C = \dfrac{Q}{С + Q}</tex>
<tex>PPMD:\ Esc_D = \dfrac{Q}{2*С}</tex>
===Адаптивные методы===
{{Определение
|definition=
<tex>SEE</tex> (''Secondary Escape Estimation'') — модель оценки, которая ''адаптируется'' к обрабатываемым данным
}}
Для нахождения <tex>ОВУ</tex> строятся <tex>контексты\ ухода</tex> (''Escape Context''), формируемые из различный полей. Всего используется <tex>4</tex> поля, в которых содержится информация о:
*порядке PPM-контекста
*количестве уходов
*количестве успешных кодирований
*последних двух символах PPM-контекста.
<tex>ОВУ</tex> для текущего контекста находится путем взвешивания оценок, которые дают три контекста ухода (<tex>order-2\ EC</tex>, <tex>order-1\ EC</tex>, <tex>order-0\ EC</tex>), соответствующие текущему <tex>PPM</tex>-контексту. <tex>Order-2\ EC</tex> наиболее точно соответствует ''текущему'' контексту, контексты ''ухода'' порядком ниже формируются путем выбрасывания части информации полей <tex>order-2\ EC</tex>. При взвешивании контекстов ухода используются следующие веса <tex>w</tex>:
<tex>\dfrac{1}{w} = p \cdot log_2 \dfrac{1}{p} + (1 - p) \cdot log_2 \dfrac{1}{1 - p}</tex>, где <tex>p - ОВУ</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>
==См. также==
*[[Алгоритм LZMA]]
*[[Алгоритм Хаффмана]]
*[[Арифметическое кодирование]]
==Источники информации==
*[ftp://ftp.cs.brown.edu/pub/techreports/93/cs93-28.pdf The design and analysis of efficient lossless data compression systems]
*[http://rahilshaikh.weebly.com/uploads/1/1/6/3/11635894/data_compression.pdf Introduction to Data Compression]
*[https://en.wikipedia.org/wiki/Prediction_by_partial_matching Prediction by partial matching]
*[http://ctxmodel.net/files/PPMd/ShkarinPPMII.pdf PPM one step to practicality]
*[http://www.compression.ru/book/pdf/compression_methods_part1_2-4.pdf Методы сжатия данных]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Алгоритмы сжатия]]
