23
правки
Изменения
небольшие коррективы
}}
<tex> PPM </tex> (''Prediction by Partial Matching'') — адаптивный метод сжатия данных без потерь, основанный на контекстном моделировании и предсказании. Модель <tex> PPM </tex> использует ''контекст'' — множество символов в несжатом потоке, предшествующих данному, чтобы ''предсказывать'' значение символа на основе статистических данных. Сама модель <tex> PPM </tex> лишь ''предсказывает значение символа'', непосредственное сжатие осуществляется алгоритмами энтропийного кодирования, как например, алгоритм Хаффмана или арифметическое кодирование.
Исходно кодеру и декодеру поставлена в соответствие ''начальная'' модель источника данных. Будем считать, что она состоит из <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> гарантирует, что это в конце концов произойдет. Таким образом, каждый символ кодируется серией кодов символа ухода, за которой следует код самого символа. Из этого следует, что вероятность ухода также можно рассматривать как вероятность перехода к контекстной модели меньшего порядка.
