Алгоритм сжатия PPM
Материал из Википедии — свободной энциклопедии
Алгорити PPM (Prediction by Partial Matching — предсказание по частичному совпаденю) — это адаптивный статистический алгоритм сжатия данных, основанный на контекстном моделировании и предсказании. Модель PPM использует контекст — множество символов в несжатом потоке, предшествующих данному, чтобы предсказывать значение символа на основе статистических данных. Сама модель PPM лишь предсказывает значение символа, непосредственное сжатие осуществляется алгоритмами энтропийного кодирования, как например, алгоритм Хаффмана, арифметическое кодирование.
Длина контекста, который используется при предсказании обычно сильно ограничена. Эта длина обозначается n и определяет порядок модели PPM, что обозначается как PPM(n). Неограниченные модели так же существуют и обозначаются просто PPM*. Если предсказание символа по контексту из n символов не может быть произведено, то происходит попытка предсказать его с помощью n-1 символов. Рекурсивный переход к моделям с меньшим порядком происходит пока предсказание не проихойдёт в одной из моделей, либо когда контекст станет нулевой длины (n=0). В последнем случае предсказание будет произведено по фиксированной модели, не учитывающей контекст символа вообще.
Большое значение для алгоритма PPM имеет проблема обработки новых символов, ещё не встречавшихся во входном потоке. Это проблема носит название проблема нулевой частоты. Некоторые варианты реализаций PPM полагают счётчик новго символа равным фиксированной величине, например, единице. Другие реализации, как например, PPM-D, увеличивают псевдосчётчик нового символа каждый раз, когда, действительно, в потоке появляется новый символ. (Другими словами, PPM-D оценивает вероятность появения нового символа как отношене числа уникальных символов к общему числу используемых символов).
Опубликованные исследование алгоритмов семейства PPM появились в середине 1980-х годов. Программные реализации не были популярны до 1990-х годов, потому как модели PPM требуют значительное количество оперативной памяти. Современные реалзации PPM являются лучшими среди алгоритмов сжатия без потерь для текстов на ествественном языке.
