PPM (алгоритм стиснення)

PPM (англ. Prediction by Partial Matching — передбачення щодо часткового збігу) — адаптивний статистичний алгоритм стиснення даних без втрат, що базується на контекстному моделюванні і передбаченні. Модель 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]