Алгоритм сжатия PPM
PPM (англ. Prediction by Partial Matching — предсказание по частичному совпадению) — адаптивный статистический алгоритм сжатия данных без потерь, основанный на контекстном моделировании и предсказании. Модель PPM использует контекст — множество символов в несжатом потоке, предшествующих данному, чтобы предсказывать значение символа на основе статистических данных. Сама модель PPM лишь предсказывает значение символа, непосредственное сжатие осуществляется алгоритмами энтропийного кодирования, как например, алгоритм Хаффмана, арифметическое кодирование.
Длина контекста, который используется при предсказании, обычно сильно ограничена. Эта длина обозначается n и определяет порядок модели PPM, что обозначается как PPM(n). Неограниченные модели также существуют и обозначаются просто PPM*. Если предсказание символа по контексту из n символов не может быть произведено, то происходит попытка предсказать его с помощью n-1 символов. Рекурсивный переход к моделям с меньшим порядком происходит, пока предсказание не произойдёт в одной из моделей, либо когда контекст станет нулевой длины (n=0). Модели степени 0 и −1 следует описать особо. Модель нулевого порядка эквивалента случаю контекстно-свободного моделирования, когда вероятность символа определяется исключительно из частоты его появления в сжимаемом потоке данных. Подобная модель обычно применяется вместе с кодированием по Хаффману. Модель порядка −1 представляют собой статическую модель, присваивающую вероятности символа определенное фиксированное значение; обычно все символы, которые могут встретиться в сжимаемом потоке данных, при этом считаются pавновероятными. Для получения хорошей оценки вероятности символа необходимо учитывать контексты pазных длин. PPM представляет собой вариант стратегии перемешивания, когда оценки вероятностей, сделанные на основании контекстов 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
Напишите отзыв о статье "Алгоритм сжатия PPM"
Примечания
- ↑ www.maximumcompression.com/algoritms.php Recent PPM implementations are among the best-performing lossless compression programs for natural language text.
- ↑ [books.google.com/books?id=ChSOjgiY84YC&pg=PA141&dq=PPM+best+text+compression&hl=en 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»
- ↑ [www.compression.ru/download/articles/ppm/smirnov_2000_ppm_faq.html Введение в PPM]
Литература
- J.G. Cleary, and I.H. Witten, [ieeexplore.ieee.org/search/wrapper.jsp?arnumber=1096090 Data compression using adaptive coding and partial string matching], IEEE Transactions on Communications, Vol. 32 (4), pp. 396–402, April 1984.
- A. Moffat, [dx.doi.org/10.1109/26.61469 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, [www.cbloom.com/papers/ppmz.zip Solving the problems of context modeling].
- W.J. Teahan, [cotty.16x16.com/compress/peppm.htm Probability estimation for PPM].
- T. Schürmann and P. Grassberger, [scitation.aip.org/getabs/servlet/GetabsServlet?prog=normal&id=CHAOEH000006000003000414000001&idtype=cvips&gifs=yes Entropy estimation of symbol sequences], Chaos, Vol. 6, pp. 414–427, September 1996.
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Отрывок, характеризующий Алгоритм сжатия PPM
Николай с удивлением смотрел на ее лицо. Это было то же лицо, которое он видел прежде, то же было в нем общее выражение тонкой, внутренней, духовной работы; но теперь оно было совершенно иначе освещено. Трогательное выражение печали, мольбы и надежды было на нем. Как и прежде бывало с Николаем в ее присутствии, он, не дожидаясь совета губернаторши подойти к ней, не спрашивая себя, хорошо ли, прилично ли или нет будет его обращение к ней здесь, в церкви, подошел к ней и сказал, что он слышал о ее горе и всей душой соболезнует ему. Едва только она услыхала его голос, как вдруг яркий свет загорелся в ее лице, освещая в одно и то же время и печаль ее, и радость.– Я одно хотел вам сказать, княжна, – сказал Ростов, – это то, что ежели бы князь Андрей Николаевич не был бы жив, то, как полковой командир, в газетах это сейчас было бы объявлено.
Княжна смотрела на него, не понимая его слов, но радуясь выражению сочувствующего страдания, которое было в его лице.
– И я столько примеров знаю, что рана осколком (в газетах сказано гранатой) бывает или смертельна сейчас же, или, напротив, очень легкая, – говорил Николай. – Надо надеяться на лучшее, и я уверен…
Княжна Марья перебила его.
– О, это было бы так ужа… – начала она и, не договорив от волнения, грациозным движением (как и все, что она делала при нем) наклонив голову и благодарно взглянув на него, пошла за теткой.
Вечером этого дня Николай никуда не поехал в гости и остался дома, с тем чтобы покончить некоторые счеты с продавцами лошадей. Когда он покончил дела, было уже поздно, чтобы ехать куда нибудь, но было еще рано, чтобы ложиться спать, и Николай долго один ходил взад и вперед по комнате, обдумывая свою жизнь, что с ним редко случалось.
Княжна Марья произвела на него приятное впечатление под Смоленском. То, что он встретил ее тогда в таких особенных условиях, и то, что именно на нее одно время его мать указывала ему как на богатую партию, сделали то, что он обратил на нее особенное внимание. В Воронеже, во время его посещения, впечатление это было не только приятное, но сильное. Николай был поражен той особенной, нравственной красотой, которую он в этот раз заметил в ней. Однако он собирался уезжать, и ему в голову не приходило пожалеть о том, что уезжая из Воронежа, он лишается случая видеть княжну. Но нынешняя встреча с княжной Марьей в церкви (Николай чувствовал это) засела ему глубже в сердце, чем он это предвидел, и глубже, чем он желал для своего спокойствия. Это бледное, тонкое, печальное лицо, этот лучистый взгляд, эти тихие, грациозные движения и главное – эта глубокая и нежная печаль, выражавшаяся во всех чертах ее, тревожили его и требовали его участия. В мужчинах Ростов терпеть не мог видеть выражение высшей, духовной жизни (оттого он не любил князя Андрея), он презрительно называл это философией, мечтательностью; но в княжне Марье, именно в этой печали, выказывавшей всю глубину этого чуждого для Николая духовного мира, он чувствовал неотразимую привлекательность.
«Чудная должна быть девушка! Вот именно ангел! – говорил он сам с собою. – Отчего я не свободен, отчего я поторопился с Соней?» И невольно ему представилось сравнение между двумя: бедность в одной и богатство в другой тех духовных даров, которых не имел Николай и которые потому он так высоко ценил. Он попробовал себе представить, что бы было, если б он был свободен. Каким образом он сделал бы ей предложение и она стала бы его женою? Нет, он не мог себе представить этого. Ему делалось жутко, и никакие ясные образы не представлялись ему. С Соней он давно уже составил себе будущую картину, и все это было просто и ясно, именно потому, что все это было выдумано, и он знал все, что было в Соне; но с княжной Марьей нельзя было себе представить будущей жизни, потому что он не понимал ее, а только любил.
Мечтания о Соне имели в себе что то веселое, игрушечное. Но думать о княжне Марье всегда было трудно и немного страшно.
«Как она молилась! – вспомнил он. – Видно было, что вся душа ее была в молитве. Да, это та молитва, которая сдвигает горы, и я уверен, что молитва ее будет исполнена. Отчего я не молюсь о том, что мне нужно? – вспомнил он. – Что мне нужно? Свободы, развязки с Соней. Она правду говорила, – вспомнил он слова губернаторши, – кроме несчастья, ничего не будет из того, что я женюсь на ней. Путаница, горе maman… дела… путаница, страшная путаница! Да я и не люблю ее. Да, не так люблю, как надо. Боже мой! выведи меня из этого ужасного, безвыходного положения! – начал он вдруг молиться. – Да, молитва сдвинет гору, но надо верить и не так молиться, как мы детьми молились с Наташей о том, чтобы снег сделался сахаром, и выбегали на двор пробовать, делается ли из снегу сахар. Нет, но я не о пустяках молюсь теперь», – сказал он, ставя в угол трубку и, сложив руки, становясь перед образом. И, умиленный воспоминанием о княжне Марье, он начал молиться так, как он давно не молился. Слезы у него были на глазах и в горле, когда в дверь вошел Лаврушка с какими то бумагами.
