PPM - это очень продвинутый алгоритм расчета вероятностей символов для дальнейшего сжатия Арифметическим кодированием или Хаффаном или Шеноном-Фэно :). Многие современные крутожмущие архиваторы используют именно его.
Идея:
Будем называть контекстом n символов, предшествующие кодируемому символу.Основная идея алгоритма - считать вероятности символов отдельно для каждого контекста. Для контекстов длинной 1 и 2 можно использовать 2-х и 3-х мерные массивы. Для контекстов большей длины приходится использовать деревья, в вершинах которых находятся символы и их частоты.
Пример для контекстов длинной 1:
A[0..255][0..255] - массив для хранения вероятностей встречаемости символов.
A['F]['Z'] - вероятность встречи символа 'Z' в контексте 'F'.)
Пара проблем:
Основной проблемой является следующее:
Если мы например работаем с контекстами длиной n, а кодируемого символа в контексте такой длины еще не встречалось, то придется рассматривать модель n-1 порядка, закодировав предварительно "символ ухода". Однако это символ ухода должен иметь какую-нибуть частоту встречаемости. Именно в способе расчета этой вероятности находится основное различие между плохими и хорошими реализациями алгоритма PPM