PPM (алгоритм стиснення)
PPM (англ. Prediction by Partial Matching — передбачення щодо часткового збігу) — адаптивний статистичний алгоритм стиснення даних без втрат, що базується на контекстному моделюванні[en] і передбаченні. Модель PPM використовує контекст — множину символів у нестиснутому потоці, що передують даному, щоб передбачати значення символу на основі статистичних даних. Сама модель PPM лише пророкує значення символу, безпосереднє стиснення здійснюється за алгоритмами ентропійного кодування, наприклад, алгоритмом Гаффмана або арифметичного кодування.
Довжина контексту, який використовується для передбачення, зазвичай дуже обмежена. Вона позначається n і визначає порядок моделі PPM, що позначається як PPM(n). Необмежені моделі також існують і позначаються PPM*. Якщо передбачити символ за контексту з n символів не можна, то робиться спроба передбачити його за допомогою n-1 символів. Рекурсивний перехід до моделей з меншим порядком відбувається, поки в одній з моделей не відбудеться передбачення, або коли контекст досягне нульової довжини (n=0). Моделі мірою 0 і -1 слід описати окремо. Модель нульового порядку еквівалента випадку контекстно-вільного моделювання, коли ймовірність символу визначається виключно з частоти появи у стискуваному потоці даних. Подібна модель зазвичай застосовується разом з кодуванням за Гаффманом. Модель порядку -1 — це статична модель, що присвоює ймовірності символу певне фіксоване значення; зазвичай усі символи, які можуть зустрітися в стискуваному потоці даних, при цьому вважаються рівноймовірними. Для отримання хорошої оцінки ймовірності символу слід враховувати контексти різних довжин. PPM являє собою варіант стратегії перемішування, коли оцінки ймовірностей, зроблені на підставі контекстів різних довжин, об'єднуються в одну загальну ймовірність. Отримана оцінка кодується будь-яким ентропійним кодером (ЕК), зазвичай це певний різновид арифметичного кодування. На етапі ентропійного кодування і відбувається власне стискання.
Велике значення для алгоритму PPM має проблема обробки нових символів, які ще не зустрічалися у вхідному потоці — проблема нульової частоти[1]. Деякі варіанти реалізацій PPM вважають лічильник нового символу рівним фіксованій величині, наприклад, одиниці. Інші реалізації, як наприклад, PPM-D, збільшують псевдолічильник нового символу кожен раз, коли в потоці дійсно з'являється новий символ (іншими словами, PPM-D оцінює ймовірність появи нового символу як відношення числа унікальних символів до загального числа використовуваних символів).
Опубліковані дослідження алгоритмів сімейства PPM з'явилися в середині 1980-х років. Програмні реалізації не були популярні до 1990-х років, оскільки моделі PPM вимагають значної кількості оперативної пам'яті. Сучасні реалізації PPM належать до найкращих серед алгоритмів стиснення без втрат для текстів природною мовою.[2][3]
Практичне використання[ред. | ред. код]
Варіанти алгоритму PPM широко використовуються, переважно для компресії надлишкової інформації і текстових даних. PPM використовують такі архіватори[4]:
- boa, заснований на PPMz (Ian Sutton)
- ha, PPM порядку 4, оригінальний метод оцінки ймовірності відходу (Harry Hirvola)
- lgha, заснований на коді архіватора ha (Юрій Ляпко)
- ppmpacktc, заснований на коді PPMd, PPMz, PPMVC і коді ha з реалізацією hsc (Олександр Мясніков)
- arhangel, заснований на алгоритмах ha з додаванням набору фільтрів для різних даних (Юрій Ляпко)
- PPMd — реалізація PPM порядку 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
Примітки[ред. | ред. код]
- ↑ проблема нульової частоти. Архів оригіналу за 10 січня 2021.
- ↑ http://www.maximumcompression.com/algoritms.php [Архівовано 13 січня 2021 у Wayback Machine.] Recent PPM implementations are among the best-performing lossless compression programs for natural language text.
- ↑ Introduction to data compression [Архівовано 28 вересня 2015 у Wayback Machine.] ISBN 1-55860-558-4 page 141 «some of the best-performing text compression algorithms are variants of the ppm algorithm»
- ↑ Введение в PPM. Архів оригіналу за 9 січня 2021. Процитовано 8 січня 2021.
Література[ред. | ред. код]
- 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, Life 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 [Архівовано 3 червня 2004 у Wayback Machine.].
- T. Schürmann and P. Grassberger, Entropy estimation of symbol sequences, Chaos, Vol. 6, pp. 414-427, September 1996.
| |||||||||||||||||||||||||||||||||||||||||||
