Prediction by Partial Matching FAQ

Предсказание по частичному совпадению
(Prediction by Partial Matching, PPM)

Prediction by Partial Matching (PPM)

Составитель:	Максим Смирнов	http://compression.graphicon.ru/ms/
Тайный советник:	Дмитрий Шкарин	http://compression.graphicon.ru/ds/

Версия от 25.01.00
Изменения от 09.05.02:
- поправлены ссылки в "Литературе";
- мелкие косметические правки.
Изменения от 29.09.02:
- текст переведен в формат html;
- поправлены ссылки в "Литературе";
- удалена пара багов, случайно попавших под клавишу "Del".
Все оригинальные ошибки оставлены в целости и сохранности ;-)
Текст существенно устарел ;-)

Вопросы:

0. Я ничего не понимаю в сжатии. Что делать?
1. Что такое PPM?
2. Алгоритм PPM
3. Достоинства и недостатки PPM
4. Оценка вероятности кода ухода (ОВУ)
5. Обновление счетчиков символов
6. Масштабирование счетчика последнего встреченного символа или recency scaling
7. Масштабирование в детерминированных контекстах или deterministic scaling
8. Выбор порядка для кодирования символа или Local Order Estimation (LOE)
9. Unbounded PPM или PPM*
10. Компрессоры, использующие PPM
11. Литература, исходники

0. Я ничего не понимаю в сжатии. Что делать?
    Читай [2]. Неплохие русскоязычные сайты по сжатию:
http://sochi.net.ru/~maxime/
http://arctest.narod.ru
    Практически все можно найти через:
http://www.google.com    :-)
http://citeseer.nj.nec.com/cs/
http://www.datacompression.info/
http://www.hn.is.uec.ac.jp/~arimura/compression_links.html

1. Что такое PPM?
Классический PPM (prediction by partial matching) - это метод контекстно-зависимого моделирования ограниченного порядка (finite-context modeling), позволяющий оценить вероятность символа в зависимости от предыдущих символов. Строку символов, непосредственно предшествующую текущему символу, будем называть контекстом. Если для оценки вероятности используется контекст длины N, то мы имеем дело с контекстно-ограниченной моделью степени N или порядка N (order-N, O-N).

Пример 1: пусть мы кодируем строку символов алфавита { a, b, c }

  abaabcabcabbabc
                | текущий символ

В модели O-2 вероятность символа 'c' может быть оценена как 2/4, так как контекст уже 4 раза встречался в строке, и 2 раза в этом контексте появлялся символ 'c'. Для модели O-1 получаем оценку 2/5.  /* конец примера */

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

Таблица 1.

Символ	Частота	Вероятность	Кодовое пространство
a	1	1/4	[0.00..0.25)
b	1	1/4	[0.25..0.50)
c	2	2/4	[0.50..1.00)

ЭК отображает соответствующее символу кодовое пространство K в код длиной -lg2 |K| бит (здесь и далее lg2 - это логарифм по основанию 2). Например, длина кода символа 'c' будет равна -lg2 (1.00-0.50) = 1 бит.

2. Алгоритм PPM
    Для каждой контекстной модели (или, что короче, контекста) заводим счетчики символов. Если какой-то символ появляется в данном контексте, то значение соответствующего счетчика этого контекста увеличивается.
    К алфавиту сжимаемой последовательности добавляется один специальный символ - так называемый код ухода 'esc'. Вероятность ухода - это вероятность, которую имеют еще не появлявшиеся в контексте символы. Любая контекстная модель должна давать отличную от нуля оценку вероятности ухода. Исключение из этого правила могут составлять только те случаи, когда заранее известно, что любой символ алфавита может быть оценен в рассматриваемом контексте. Оценка вероятности ухода - это основная проблема PPM, которая будет рассмотрена ниже в пункте 4.
    Если символ S кодируется PPM-моделью с максимальным порядком M, то в первую очередь рассматривается контекстная модель степени M. Если она оценивает вероятность S числом, не равным нулю, то сама и используется для кодирования S. Иначе выдается код ухода, и на основе следующего меньшего по длине контекста производится очередная попытка оценить вероятность S. Кодирование происходит через уход к меньшим контекстам до тех пор, пока S не будет оценен. Контекст -1 степени гарантирует, что это в конце концов произойдет. Таким образом каждый символ кодируется серией символов ухода, за которыми следует код самого символа. Из этого следует, что вероятность ухода также можно рассматривать как вероятность перехода к модели меньшего порядка.
    При оценке вероятности символа в модели порядка m мы можем исключить из рассмотрения все символы, которые уже встречались в контекстах более высоких порядков (M...m+1), поскольку они уже не могут кодироваться моделью более низкого порядка, так как символ S точно не один из них. Для этого во всех моделях меньших порядков нужно замаскировать значения счетчиков символов, вероятность которых могла быть уже оценена моделью более высокого порядка. Такая техника называется методом исключения (exclusions).

Пример 2.
    Имеем последовательность символов "bcbcabcbcabccbc" алфавита { a, b, c, d }, которая уже была закодирована. Будем считать, что счетчик вероятности ухода равен 1 для всех моделей, счетчики символов увеличиваются на 1, применяется метод исключений, и максимальный контекст имеет длину 4 (M=4). Рассмотрим кодирование текущего символа 'd'. Сначала рассматривается контекст 4-го порядка , но поскольку ранее он еще не встречался, то мы, ничего не послав на выход, переходим к контексту O-3. Единственным ранее встречавшимся в этом контексте () символом является 'a', счетчик которого равен 2, поэтому уход кодируется с вероятностью 1/(2+1) (2 - количество использований контекста, 1 - учитываем символ ухода). В модели 2-го порядка за следуют 'a', который исключается, дважды 'b', и один раз 'c', поэтому вероятность ухода будет 1/(3+1). В моделях O-1 и O-0 можно оценить 'a', 'b' и 'c', но каждый из них исключается, поскольку уже встречался в контексте более высокого порядка, поэтому здесь вероятностям ухода даются значения равные 1. Система завершает работу с вероятностями уходов в модели порядка -1, где 'd' остается единственным неоцененным символом, поэтому он кодируется с вероятностью 1 посредством 0 битов. В результате получим, что для кодирования 'd' используется 3.6 битов. Табл.2 демонстрирует коды, которые должны были быть использованы для любого текущего символа из всех возможных.  /* конец примера */

Таблица 2. Механизм кодирования с исключениями 4-х символов алфавита { a, b, c, d }, которые могут следовать за строкой "bcbcabcbcabccbc".

Символ Кодирование

a
a
2/3
( Всего = 2/3 ; 0.58 битов )

b
"esc" b
1/3 2/4
( Всего = 1/6 ; 2.6 битов )

c
"esc" c
1/3 1/4
( Всего = 1/12; 3.6 битов )

d
"esc" "esc" "esc" "esc"
1/3 1/4 1 1
( Всего = 1/12; 3.6 битов )

    Алгоритм декодирования абсолютно симметричен алгоритму кодирования. Декодировав в текущем контексте символ, проверяем, не является ли он кодом ухода, если это так, то переходим к контексту порядком ниже, иначе считаем, что мы восстановили исходный символ и переходим к следующему шагу. Последовательность обновления счетчиков, создания новых контекстных моделей и т.п. при кодировании и декодировании должна быть строго одинаковой.

3. Достоинства и недостатки PPM
    Вот уже в течение десятилетия PPM остается наиболее мощным практическим алгоритмом с точки зрения степени сжатия. По-видимому, побить его в этом смогут только более изощренные методы контекстного моделирования, которые несомненно будут появляться, так как процессоры становятся все быстрее, а доступной памяти все больше.
    Алгоритм PPM обеспечивает наиболее быстрое схождение к оптимальному коду. Для первых N символов сжимаемой строки средняя длина кода будет лишь на O(lg2(N)/N) больше энтропии источника, породившего строку. При этом доказано, что никакой универсальный алгоритм не может иметь большей скорости схождения, чем O(lg2(N)/N). Для словарных схем эти асимптотические оценки имеют вид:
LZ77 -- O( lg2 (lg2(N)) / lg2(N) );
LZ78 -- O(1/lg2(N)).
    Наилучшие результаты PPM показывает на текстах: отличный коэффициент сжатия при высокой скорости, чему наглядным примером является [12].
    Недостатки PPM заключаются в следующем: медленное декодирование (обычно на 5-10% медленнее кодирования); несовместимость программ в случае изменения алгоритма кодирования; чрезвычайно медленная обработка малоизбыточных данных (скорость может падать на порядок); для различных файлов оптимальный максимальный порядок модели колеблется обычно в районе 4..10, поэтому при выборе модели какого-то фиксированного порядка часть файлов будет сжиматься хуже, чем могла бы; плохое сжатие файлов с нестабильными контекстами, здесь классический PPM заметно проигрывает LZ-методам; большие запросы памяти в случае использования сложных моделей высокого порядка - для безбедной жизни нужно не менее 15Мб, а ведь алгоритм симметричный, для кодирования и декодирования требуются практически одинаковые объемы памяти; провалы в степени сжатия по сравнению с LZ на файлах, имеющих длинные повторы блоков символов.
    Несмотря на то, что практически всегда можно подобрать такую PPM-модель, что она будет давать лучшее сжатие, чем LZ или BWT, применение PPM-компрессоров главным образом целесообразно для сжатия текстов и тому подобной информации: для малоизбыточных файлов велики временные затраты, избыточные файлы с длинными повторяющимися строками (тексты программ) можно сжимать с помощью BWT-компрессоров и даже словарных методов, так как соотношение сжатие-скорость-память обычно лучше. Для сильно избыточных данных лучше все-таки использовать PPM, так как LZ77, BWT-методы обычно работают при этом сравнительно медленно из-за деградации структур данных.

4. Оценка вероятности кода ухода (ОВУ)
    ОВУ связана с так называемой "проблемой нулевой частоты" ("zero frequency problem"), описанной в [7].
    Можно выделить два подхода к решению проблемы ОВУ: априорные методы, основанные на предположениях о природе сжимаемых данных, и адаптивные методы, которые пытаются приспособиться к сжимаемым данным.

4.1. Априорные методы
    Введем обозначения:
C - общее число просмотров контекста;

Q - количество разных символов в контексте;

Qi - количество таких разных символов, что они встречались в контексте ровно i раз;

Escx - ОВУ по методу x.

    Изобретатели алгоритма PPM Cleary и Witten в своей оригинальной статье [1] предложили два метода ОВУ: так называемые метод A и метод B. Частные случаи алгоритма PPM с использованием этих методов называются, соответственно, PPMA и PPMB.
    ОВУ по методу A:

          1
EscA = -------
        C + 1

Кстати, в прим.2 был использован метод A.

Метод B:

       Q - Q1
EscB = ------
         C

В 1988г Moffat предложил метод C (PPMC):

         Q
EscC = -----
       C + Q

Затем была разработана модификация метода C, получившая название метода D (PPMD):

         Q
EscD = -----
        2*C

Метод D (см. [5]) в общем случае работает немного лучше метода С, но оба варианта дают значительно лучшие результаты, чем методы A, B.
В статье [7] были описаны методы P,X,XC, основанные на пуассоновской модели процесса. Авторы заявляют, что P,X,XC дают в большинстве случаев лучшие оценки, чем методы A..D.

         Q1    Q2    Q3
EscP  = --- - --- - --- - ...
         C    C^2   C^3
         Q1
EscX  = ---
         C
         Q1
EscXC = ---   при 0 < Q1 < C, иначе по методу C
         C

4.2. Адаптивные методы
Чтобы улучшить оценку вероятности ухода, необходимо иметь такую модель оценки, которая бы адаптировалась к обрабатываемым данным. Подобный адаптивный механизм получил название Secondary Escape Estimation (SEE). Вразумительных обоснований выбора той или иной схемы SEE при отсутствии априорных знаний о характере сжимаемых данных пока не найдено.
Одна из самых ранних попыток реализации SEE была предпринята Bloom'ом (метод Z) [3,13]. Для нахождения ОВУ строятся так называемые контексты ухода Escape Context (EC), формируемые из различный полей. Всего используется 4 поля, в которых содержится информация о: порядке PPM-контекста, количестве уходов, количестве успешных кодирований, последних двух символах PPM-контекста. ОВУ для текущего контекста находится путем взвешивания оценок, которые дают три контекста ухода (order-2 EC, order-1 EC, order-0 EC), соответствующие текущему PPM-контексту. Order-2 EC наиболее точно соответствует текущему контексту, контексты ухода порядком ниже формируются путем выбрасывания части информации полей order-2 EC. При взвешивании контекстов ухода используются следующие веса w:

  1              1                    1
 --- = e * lg2 (---) + (1-e) * lg2 (-----)
  w              e                  1 - e

где e - ОВУ, которую дает данный взвешиваемый контекст; формируется из фактического количества успешных кодирований и количества уходов в PPM-контекстах, соответствующих этому EC. Окончательная оценка:

        sum (e  w )
              i  i
EscZ =  ----------- ,  i = 0,1,2.
          sum w
               i

Если количество уходов в текущем контексте велико, то для оценки используется обычный метод D. Таким образом, можно рассматривать методы A..XC как варианты организации order-(-1) EC.
    После ОВУ выполняется поиск символа в PPM-контексте, по результатам поиска (нашли символ или нет) обновляются счетчики соответствующих EC.
    При построении EC также имеет смысл использовать информацию о контекстах меньших порядков. Это, например, может быть количество уходов (равно количеству символов) в контексте порядка на единицу меньше текущего, или разница между количеством уходов в меньшем контексте и количеством уходов в текущем.
    В [6] описан несколько иной подход к проблеме SEE, основанный на идее наследования информации о сжимаемых данных от "старых" (родительских) контекстов к "молодым".

5. Обновление счетчиков символов
    Модификация счетчиков после обработки очередного символа может быть реализована различным образом. После кодирования каждого символа естественно изменять соответствующие счетчики во всех моделях 0,1,..M. Но в случае классического PPM лучшие результаты достигаются в том случае, когда увеличиваются счетчики оцененного символа только в тех контекстах, в которых он ранее не встречался, и в том контексте, где он был оценен. Иначе говоря, счетчик оцененного символа не увеличивается, если он был оценен в контексте более высокого порядка. Эта техника имеет самостоятельное название - обновляемое исключение (update exclusions). Обычно под исключением понимают сам механизм уходов с исключением из оценки счетчиков тех символов, которые встречались в контекстах большего порядка, в сочетании с именно обновляемым исключением. Применение обновляемого исключения позволяет улучшить сжатие примерно на 2% по сравнению с тем случаем, когда производится обновление счетчиков символа во всех моделях. Исключение из оценки символов, встреченных уже в старших контекстах, улучшает сжатие на 2-5% для моделей PPM небольшого порядка (3..5). При увеличении порядка этот механизм становится абсолютно необходимым, иначе усложнение модели приведет только к ухудшения сжатия практически во всех случаях.
    Также выделяют такую технику как частичное обновляемое исключение (partial update exclusions), при котором производится увеличение счетчиков во всех так называемых детерминированных контекстах; если их нет, то только в самом длинном недетерминированном. Под детерминированным понимается контекст, в котором до данного рассматриваемого момента встречался только один уникальный символ (любое число раз). Частичное обновляемое исключение применяется в PPM*.
    При увеличении значений счетчиков может возникнуть переполнение в арифметическом кодере. Во избежание этого обычно производят деление значений пополам при достижении определенного порога. Максимальное значение порога определяется особенностями конкретного арифметического кодера. С другой стороны, масштабирование счетчиков дает побочный эффект в виде улучшения сжатия при кодировании данных с быстро меняющимися контекстами. Чем нестабильнее контекст, тем чаще следует масштабировать, отбрасывая таким образом часть информации о поведении контекста в прошлом. В свете этого естественной является идея об увеличении счетчиков с неравным шагом, так чтобы недавно встреченные символы получали большие веса, чем "старые" символы.

6. Масштабирование счетчика последнего встреченного символа или recency scaling
Если последний раз в текущем контексте был встречен некий символ S, то вероятность того, что и текущий символ также S, вырастает, причем часто значительно. Этот факт позволяет улучшить предсказание за счет умножения счетчика последнего встреченного символа на некий коэффициент. В большинстве случаев хорошо работает множитель 1.1-1.2, то есть при таком значении наблюдается улучшение сжатия большинства файлов и маловероятно ухудшение сжатия какого-то привередливого файла. Но часто оптимальное значение масштабирующего коэффициента колеблется в районе 2-2.5, так что можно улучшить оценку за счет адаптивного изменения множителя. Подходящее значение выбирается на основе анализа сжимаемых данных с помощью эмпирических формул.
Применение recency scaling позволяет улучшить сжатие в среднем на 0.5%.

7. Масштабирование в детерминированных контекстах или deterministic scaling
    Известно, что методы A..C переоценивают вероятность ухода для детерминированных контекстов. Это можно исправить, умножая счетчик символа на определенный коэффициент. Нетрудно заметить, что этот механизм есть частный случай recency scaling.
    В [4] утверждается, что эффект от deterministic scaling увеличивается, если при этом используется частичное обновляемое исключение, а не обычное обновляемое.
    Deterministic scaling мало что дает в случае использования метода D. Вообще, чем точнее вычисляется вероятность ухода, тем пользы от этого масштабирования меньше. И оно вовсе не нужно при использовании SEE.

8. Выбор порядка для кодирования символа или Local Order Estimation (LOE)
    После задачи оценки вероятности ухода второй по значимости проблемой PPM является выбор порядка модели, обеспечивающей наилучшее сжатие обрабатываемых данных. В зависимости от вида данных оптимальный порядок модели может быть от 0 до 16 (для текстов в районе 4-6) и больше, кроме того, обычно имеются локальные изменения внутри файла.
    Механизм выбора порядка модели для кодирования текущего символа получил название LOE. Все схемы LOE носят чисто эвристический характер (исключая метод CTW [8], работающий с двоичным алфавитом) и заключаются в том, что задаем некую функцию "доверия" и пробуем предсказать с ее помощью эффективность кодирования текущего символа в том или ином доступном контексте порядка от 0 до наперед заданного M. Можно выделить три типа схем LOE:
    - ищем оптимальный порядок сверху вниз от контекста максимального порядка к контексту минимального порядка, прекращаем поиск как только контекст меньшего порядка кажется нам более "подозрительным", чем текущий, который и используем в качестве первого контекста для оценки вероятности символа;
    - поиск снизу вверх;
    - оценка всех доступных контекстов.
    Если в выбранном контексте закодировать символ не удалось, то, вообще говоря, процедуру поиска оптимального можно повторить, но обычно ищут только начальный порядок, а в случае ухода просто переходят на уровень ниже, то есть дальше используется обычный алгоритм PPM.
    Выбор той или иной функции доверия зависит от особенностей конкретной реализации PPM и личных пристрастий разработчика. Как показал опыт, различные "наивные" энтропийные оценки текущего контекста по сравнению со следующим возможным работают плохо. Эти оценки основывались на сравнении средней длины кода в текущем контексте и в следующем; ясное дело, из этого ничего не получалось, так как функция распределения в текущем контексте может быть более плоской, чем в следующем, поэтому сравнивать надо среднюю длину кода, усредненную по всем дочерним контекстам текущего контекста, со средней длиной кода, усредненной по всем дочерним контекстам следующего рассматриваемого контекста. Под дочерним контекстом понимается контекст большего порядка, содержащий в себе строку текущего контекста ("abcd" является дочерним для "bcd").
    В [3] был предложен эффективный и простой метод, дающий оценку исходя из вероятности P наиболее вероятного символа в контексте (Most Probable Symbol's Probability, MPS-P) и количества уходов из контекста E. Обобщенно формулу можно записать так:

a*P*lg2 (P) + b*E*( lg2 (E) - c ) + d*( 1 - P )*( lg2 (E) - c ),

где константы a,b,c,d берутся "с потолка". Впрочем, желающие могут еще добавить констант по своему вкусу - на каком-нибудь файле это обязательно даст выигрыш.
    К счастью, оценка только по P дает хорошие результаты уже в том случае, когда просто выбираем контекст с максимальным P (соответствует варианту обобщенной формулы при b=d=0).

9. Unbounded PPM или PPM*
При фиксировании максимального порядка контекстов в районе 5-6 PPM дает отличные результаты на текстах, но весьма плохо работает на высокоизбыточных данных с большим количеством длинных повторяющихся строк. В [9] был описан метод борьбы с этим недостатком. Предложенный алгоритм, PPM*, был основан на использовании контекстов неограниченной длины. Авторы предложили следующую стратегию выбора максимального порядка на каждом шаге: в качестве контекста максимального порядка выбираем самый короткий детерминированный контекст. В качестве структуры данных используется context trie, содержащее ссылки на уже обработанную часть файла.
Реализация PPM*, описанная одним из автором алгоритма в [4], имела весьма хилые характеристики: сжатие на уровне PPMD order-5, скорость, как утверждается, также сопоставима, но памяти расходуется значительно больше. В принципе, расходы памяти могут быть сопоставимы, так как context trie, если его оформить в виде PATRICIA trie, позволяет достаточно экономно использовать память (расход при этом зависит линейно от размера входных данных). В [6] приводится структура данных на основе suffix tree, требующая примерно в два раза меньше памяти, чем context trie, предложенный авторами PPM*.

10. Компрессоры, использующие PPM
Практически все компрессоры можно найти на
ftp://ftp.elf.stuba.sk/pub/pc/pack/

Компрессор Автор
boa Ian Sutton
ha Harry Hirvola
lgha Юрий Ляпко
arhangel Юрий Ляпко
PPMd Дмитрий Шкарин
ppmz Charles Bloom
rk Malcolm Taylor
rkuc Malcolm Taylor
rkive Malcolm Taylor
x1 Stig Valentini

boa - вариации на тему PPMZ
ha - order-4, оригинальный метод ОВУ: все еще априорный, но есть намеки на адаптацию, в качестве структуры данных для поиска контекстов используются хеш-цепочки; доступны исходники [11]
lgha - ha, переписанный на языке Ассемблера
arhangel - вариации на тему ha; применяются различные фильтры для текстов, таблиц, экзешников и мультимедии
PPMd - ограниченный порядок модели, order-1 SEE (с методом D имеет разве что общих знакомых) на основании статистики контекстов-предков, наследование информации (в этом тексте не рассмотренное); доступны исходники [12]
ppmz - метод Z, LOE, отдельно обрабатываются длинные детерминированные контексты, опционально имеется LZP; доступны исходники [13]
rk - элементы PPMZ, бинарные контексты (с пропуском символов, типа: "ABCD", "ACCD" соответствуют одному контексту "AxCD"), различные фильтры
rkuc - порядки: 16-12-8-5-3-2-1-0 (-1)?, LOE, бинарные контексты
rkive - LZP+PPM, различные фильтры

11. Литература, исходники
Для ознакомления с контекстным моделированием и методами сжатия вообще настоятельно рекомендуется к прочтению [2]. Из прочей литературы полезными следует признать пункты [5], [6].

Литература:
[1] Cleary J.G. and Witten I.H. Data compression using adaptive coding and partial string matching.
   http://compression.graphicon.ru/download/articles/ppm/cleary_witten_1984_pdf.rar
[2] Bell T., Witten I.H., Cleary J.G. Modeling for text compression.
   http://compression.graphicon.ru/download/articles/rev_univ/bell_1989_modeling_pdf.rar
  Есть русский перевод:
   http://compression.graphicon.ru/download/articles/rev_univ/modeling.rar
[3] Bloom C. Solving the problems of context modeling.
   http://compression.graphicon.ru/download/articles/ppm/bloom_1996_ppmz_pdf.rar
[4] Teahan W.J. Probability estimation for PPM.
   http://compression.graphicon.ru/download/articles/ppm/teahan_1995_probest_pdf.rar
[5] Howard P.G. The design and analysis of efficient lossless data compression systems.
   http://compression.graphicon.ru/download/articles/ppm/howard_phd_1993_pdf.rar
[6] Bunton S. On-line stochastic processes in data compression.
   http://compression.graphicon.ru/download/articles/ppm/bunton_phd_1996_pdf.rar
[7] Witten I.H. and Bell T.C. The zero-frequency problem: estimating the probabilities of novel events in adaptive text compression.
   http://compression.graphicon.ru/download/articles/ppm/witten_bell_1991_zerofreq_pdf.rar
[8] Willems F., Shtarkov Y., Tjalkens T. The context tree weighting method: basic properties.
   http://compression.graphicon.ru/download/articles/cm/willems_1995_ctw_basic_pdf.rar
[9] Cleary J.G., Teahan W.J., Witten I.H. Unbounded length contexts for PPM.
   http://compression.graphicon.ru/download/articles/ppm/cleary_teahan_1997cj_pdf.rar

Исходники:
[10] COMP-2 by Mark Nelson
   http://compression.graphicon.ru/download/articles/ppm/
nelson_1991_ddj_arithmetic_modeling_html.rar
[11] HA by Harry Hirvola
   http://compression.graphicon.ru/download/sources/cm/ha_src.rar
[12] PPMD Дмитрия Шкарина
Версия I ревизия 1:
   http://compression.graphicon.ru/download/sources/cm/ppmdi1.rar
[13] PPMZ by Charles Bloom
   http://compression.graphicon.ru/download/sources/cm/ppmz91.rar

наверх

Всё о сжатии данных, изображений и видео

Видео Video

Сравнения кодеков MSU Video Codecs Comparisons

Video Quality Measurement Tool (MSU VQMT)

Benchmarks

3D-видео 3D video

Проекты

Projects

Книга «Методы сжатия данных»

Разделы

About О сервере

Новости:

Новости:

Prediction by Partial Matching (PPM)

Вопросы:

C	- общее число просмотров контекста;
Q	- количество разных символов в контексте;
Qi	- количество таких разных символов, что они встречались в контексте ровно i раз;
Escx	- ОВУ по методу x.

Компрессор	Автор
boa	Ian Sutton
ha	Harry Hirvola
lgha	Юрий Ляпко
arhangel	Юрий Ляпко
PPMd	Дмитрий Шкарин
ppmz	Charles Bloom
rk	Malcolm Taylor
rkuc	Malcolm Taylor
rkive	Malcolm Taylor
x1	Stig Valentini

boa	- вариации на тему PPMZ
ha	- order-4, оригинальный метод ОВУ: все еще априорный, но есть намеки на адаптацию, в качестве структуры данных для поиска контекстов используются хеш-цепочки; доступны исходники [11]
lgha	- ha, переписанный на языке Ассемблера
arhangel	- вариации на тему ha; применяются различные фильтры для текстов, таблиц, экзешников и мультимедии
PPMd	- ограниченный порядок модели, order-1 SEE (с методом D имеет разве что общих знакомых) на основании статистики контекстов-предков, наследование информации (в этом тексте не рассмотренное); доступны исходники [12]
ppmz	- метод Z, LOE, отдельно обрабатываются длинные детерминированные контексты, опционально имеется LZP; доступны исходники [13]
rk	- элементы PPMZ, бинарные контексты (с пропуском символов, типа: "ABCD", "ACCD" соответствуют одному контексту "AxCD"), различные фильтры
rkuc	- порядки: 16-12-8-5-3-2-1-0 (-1)?, LOE, бинарные контексты
rkive	- LZP+PPM, различные фильтры