1632
правки
Изменения
м
rollbackEdits.php mass rollback
Рассмотрим процесс оценки отмеченного на рисунке стрелочкой символа <tex>л</tex>, встречающегося в блоке <tex>“молочное</tex>'''''_'''''<tex>молоко”</tex>
[[Файл: milk.png|350px|thumb|right|рис. 1]]
Будем использовать <tex>КМ(2)</tex> с полным смешиванием и использованием заданного набора фиксированных весов <tex>КМ</tex> разных порядков: <tex>\omega(2) = 0.6</tex>, <tex>\omega(1) = 0.3</tex> и <tex>\omega(0) = 0.1</tex>. Считаем, что в начале кодирования в <tex>КМ(o)</tex> создаются счетчики для всех символов алфавита <tex>\{“м”, “о”, “л”, “ч”, “н”, “е”,“\_”, “к”\}</tex> и инициализируются ''единицей''; счетчик символа после его обработки увеличивается на единицу. Для текущего символа «<tex>л</tex>» имеются контексты <tex>“мо”</tex>, <tex>“о”</tex> и <tex>“”</tex> (<tex>0</tex>-го порядка). К данному моменту для них накоплена статистика, показанная в ''таблице''
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| Порядок
''Метод неявного взвешивания'' связан с введением вспомогательного '''''символа ухода''''' (''escape''). ''Символ ухода'' не принадлежит к алфавиту сжимаемой последовательности. Фактически он используется для передачи ''декодеру'' указаний ''кодера''. Идея заключается в том, что если используемая <tex>КМ</tex> не позволяет оценить текущий символ (его счетчик равен нулю в этой <tex>КМ</tex>), то на выход посылается закодированный ''символ ухода'' и производится попытка ''оценить'' текущий символ в другой <tex>КМ</tex>, которой соответствует контекст иной длины. Обычно попытка оценки начинается с <tex>КМ</tex> наибольшего порядка <tex>N</tex>, затем в определенной последовательности осуществляется переход к контекстным моделям меньших порядков.
==Метод Алгоритм РРМ==
===Описание===
{{Определение
'''''Энтропийное кодирование''''' (''entropy coding'') — кодирование ''последовательности значений'' с возможностью ''однозначного'' восстановления с целью ''уменьшения'' объёма данных с помощью ''усреднения'' вероятностей появления элементов в ''закодированной'' последовательности.
}}
Обычно термин <tex> PPM РРМ</tex> (''Prediction by Partial Matching'') — адаптивный метод сжатия данных без потерь, основанный на контекстном моделировании и предсказании. Модель <tex> PPM </tex> использует ''контекст'' — множество символов используется для обозначения контекстных методов в несжатом потокеобщем, предшествующих данному, чтобы ''предсказывать'' значение символа на основе статистических данных. Сама модель по этой причине далее будет рассматриваться некий обобщенный алгоритм <tex> PPM РРМ</tex> лишь ''предсказывает значение символа'', непосредственное сжатие осуществляется алгоритмами энтропийного кодирования, как например, алгоритм Хаффмана или арифметическое кодирование.
<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> гарантирует, что это в конце концов произойдет. Таким образом, каждый символ кодируется серией кодов символа ухода, за которой следует код самого символа. Из этого следует, что вероятность ухода также можно рассматривать как вероятность перехода к контекстной модели меньшего порядка.
<tex> РРМ </tex> лишь ''предсказывает значение символа'', непосредственное сжатие осуществляется алгоритмами энтропийного кодирования, как например, алгоритм Хаффмана или арифметическое кодирование.
===Пример===
====Кодирование====
|}
Хороший кодировщик должен отобразить символ «<tex>s</tex>» с оценкой вероятности <tex>p(s)</tex> в код длины <tex>\log_2 p(s)</tex>, что и обеспечит сжатие всей обрабатываемой последовательности в целом.
==Проблема нулевой частоты==
{{Определение
