Алгоритм сжатия PPM

У этого термина существуют и другие значения, см. Ppm.

PPM (англ. Prediction by Partial Matching — предсказание по частичному совпадению) — адаптивный статистический алгоритм сжатия данных без потерь, основанный на контекстном моделировании и предсказании. Модель PPM использует контекст — множество символов в несжатом потоке, предшествующих данному, чтобы предсказывать значение символа на основе статистических данных. Сама модель PPM лишь предсказывает значение символа, непосредственное сжатие осуществляется алгоритмами энтропийного кодирования, как например, алгоритм Хаффмана, арифметическое кодирование.

Длина контекста, который используется при предсказании обычно сильно ограничена. Эта длина обозначается n и определяет порядок модели PPM, что обозначается как PPM(n). Неограниченные модели так же существуют и обозначаются просто PPM*. Если предсказание символа по контексту из n символов не может быть произведено, то происходит попытка предсказать его с помощью n-1 символов. Рекурсивный переход к моделям с меньшим порядком происходит пока предсказание не произойдёт в одной из моделей, либо когда контекст станет нулевой длины (n=0). Модели степени 0 и −1 следует описать особо. Модель нулевого поpядка эквивалента случаю контекстно-свободного моделиpования, когда веpоятность символа опpеделяется исключительно из частоты его появления в сжимаемом потоке данных. Подобная модель обычно пpименяется вместе с кодиpованием по Хаффману. Модель поpядка −1 пpедставляют собой статическую модель, пpисваивающую веpоятности символа опpеделенное фиксиpованное значение; обычно все символы, котоpые могут встpетиться в сжимаемом потоке данных, пpи этом считаются pавновеpоятными. Для получения хоpошей оценки веpоятности символа необходимо учитывать контексты pазных длин. PPM пpедставляет собой ваpиант стpатегии пеpемешивания, когда оценки веpоятностей, сделанные на основании контекстов pазных длин, объединяются в одну общую веpоятность. Полученная оценка кодиpуется любым энтpопийным кодеpом (ЭК), обычно это некая pазновидность аpифметического кодеpа. На этапе энтpопийного кодиpования и пpоисходит собственно сжатие.

Большое значение для алгоритма PPM имеет проблема обработки новых символов, ещё не встречавшихся во входном потоке. Это проблема носит название проблема нулевой частоты. Некоторые варианты реализаций PPM полагают счётчик нового символа равным фиксированной величине, например, единице. Другие реализации, как например, PPM-D, увеличивают псевдосчётчик нового символа каждый раз, когда, действительно, в потоке появляется новый символ. (Другими словами, PPM-D оценивает вероятность появления нового символа как отношение числа уникальных символов к общему числу используемых символов).

Опубликованные исследование алгоритмов семейства PPM появились в середине 1980-х годов. Программные реализации не были популярны до 1990-х годов, потому как модели PPM требуют значительное количество оперативной памяти. Современные реализации PPM являются одними из лучших среди алгоритмов сжатия без потерь для текстов на естественном языке.^[1][2]

Практическое использование

Варианты алгоритма PPM на данный момент широко используются, главным образом для компрессии избыточной информации и текстовых данных. Следующие архиваторы используют PPM^[3]:

• boa, основан на PPMz (Ian Sutton)
• HA, PPM order 4, оригинальный метод оценки вероятности ухода (Harry Hirvola)
• lgha, основан на коде архиватора ha (Юрий Ляпко)
• ppmpacktc, основан на коде PPMd, PPMz, PPMVC и коде HA с реализацией hsc (Александр Мясников)
• arhangel, основан на алгоритмах ha с добавлением набора фильтров для различных данных (Юрий Ляпко)
• PPMd — реализация PPM order-2..16, применяется наследование информации («дурилка» Дмитрия Шкарина)
• ppmz — реализован метод Z (Charles Bloom)
• rk — реализация PPMz с набором фильтров (Malcolm Taylor)
• rkuc — PPM с порядками 16-12-8-5-3-2-1-0 (Malcolm Taylor)
• rkive (Malcolm Taylor)
• x1 — реализация LZP и PPM (Stig Valentini)
• RAR (версии 3 и выше) — реализация варианта PPMd, PPMII
• 7-Zip — реализация варианта PPMd
• WinZip (версии 10 и выше) — реализация варианта PPMd

Примечания

1. ↑ http://www.maximumcompression.com/algoritms.php Recent PPM implementations are among the best-performing lossless compression programs for natural language text.
2. ↑ Introduction to data compression ISBN 1-55860-558-4 page 141 «some of the best-performing text compression algorithms are variants of the ppm algorithm»
3. ↑ Введение в PPM

Литература

• J.G. Cleary, and I.H. Witten, Data compression using adaptive coding and partial string matching, IEEE Transactions on Communications, Vol. 32 (4), pp. 396—402, April 1984.
• A. Moffat, Implementing the PPM data compression scheme, IEEE Transactions on Communications, Vol. 38 (11), pp. 1917—1921, November 1990.
• J.G. Cleary, W.J. Teahan, and I.H. Witten, Unbounded length contexts for PPM, In J.A. Storer and M. Cohn, editors, Proceedings DCC-95, IEEE Computer Society Press, 1995.
• C. Bloom, Solving the problems of context modeling.
• W.J. Teahan, Probability estimation for PPM.
• T. Schürmann and P. Grassberger, Entropy estimation of symbol sequences, Chaos, Vol. 6, pp. 414—427, September 1996.