Универсальные алгоритмы сжатия данных:

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

>> Русские материалы | Английские материалы | Исходные тексты компрессоров

Смотрите также материалы:
- Контекстные методы сжатия (без PPM)
- Арифметическое сжатие
- Сжатие с помощью грамматических моделей
- Обзоры универсальных алгоритмов сжатия данных
- Книга "Методы сжатия данных". Раздел 1 "Методы сжатия без потерь"



Русские материалы | Английские материалы | Исходные тексты компрессоров
Авторы Название Описание Рейтинг
Шкарин Д.А. Повышение эффективности алгоритма PPM Для алгоритма PPM предложены новые определения обобщенных частот символов и "уходов", позволившие заметно увеличить эффективность кодирования (сжатия) различных типов реальных дискретных данных без искажений.
Проблемы передачи информации, том 37, вып.3, 2001. С44-54.
PDF.RAR  96 кбайт
PS.RAR    84 кбайт
5
Смирнов М. PPM FAQ Введение в PPM. Больше и добавить нечего :)
25.01.2000
HTML   33 кбайт
TXT.RAR  11 кбайт
5
Bell T., Witten I, Cleary J. Modeling for Text Compression Среди прочего, в этом известном обзоре основных универсальных алгоритмов сжатия рассмотрены и алгоритмы PPM.
Перевод (кто переводил?) статьи из ACM Computing Surveys, Vol.21, No.4, pp.557-591, Dec. 1989.
TXT.RAR  54 кбайт
Оригинальная статья на английском:
PDF.RAR  499 кбайт
5
Штарков Е.С., Абузова И.В. (гм...) Modeling for Text Compression... Тьфу... Применение контекстуального моделирования для сжатия информации Клинический случай плагиата: передран один ко одному кусок русского перевода обзора Modeling for Text Compression и объявлен своей работой. Я рыдал...
Известия Тульского гос. унив. Серия Математика. Механика. Информатика. Том 3. Выпуск 2. Информатика, 1997, С.102-107.
PDF.RAR  284 кбайт
0


>> Русские материалы | Английские материалы | Исходные тексты компрессоров
Cleary J.G., Witten I.H. Data compression using adaptive coding and partial string matching
Оригинальная статья авторов PPM!
...But there is a basic conflict between the desire to use high-order Markov models and the need to have them formed quickly as the initial part of the message is sent. This paper describes how the conflict can be resolved with partial string matching...
IEEE Transactions on Communications, Vol. 32(4), pp.396-402, April 1984.
PDF.RAR  181 кбайт
RTF.RAR   72 кбайт
5
Bunton S. On-Line Stochastic Processes in Data Compression Докторская диссертация Сьюзен Бантон. Одно из немногих серьезных исследований техник контекстного моделирования.
PhD thesis, University of Washington, 1996.
PDF.RAR  800 кбайт
PS.RAR   345 кбайт
5
Bunton S. A Generalization and Improvement to PPM's "Blending" Обобщение вариантов вычисления оценок вероятностей с явным и неявным взвешиванием.
Technical Report UW-CSE-97-01-10, Department of Computer Science and Engineering, University of Washington, 1997.
PDF.RAR  201 кбайт
PS.RAR   102 кбайт
5
Bunton S. Semantically Motivated Improvements for PPM Variants ...This paper explains how to significantly improve the compression performance of any PPM variant (by 5–12%) by combining PPM’s probability estimator, ‘blending’, with information-theoretic state selection. Hazards inherent to this combination are overcome by identifying the distinct semantics of the two approaches and resolving the differences using a dual-frequency update mechanism...
Выжимка основных идей из диссертации.
The Computer Journal, Vol. 40, N. 2/3, 1997, pp.77-93.
PDF.RAR  154 кбайт
5
Howard P.G. The design and analysis of efficient lossless data compression systems Докторская диссертация Пола Ховарда. В числе прочего рассматриваются PPMD и способы ускорения PPM.
PhD thesis, Brown University, Providence, Rhode Island, 1993. 
PDF.RAR  595 кбайт
PS.RAR    377 кбайт
5
Bloom C. Solving the problems of context modeling Описание PPMZ. Одно из первых описаний SEE.
California Institute of Technology, 1996. 
PDF.RAR  82 кбайт
PS.RAR    41 кбайт
5
Cleary J.G., Teahan W.J. Unbounded length contexts for PPM Одна из многочисленных статей-клонов о PPM*.
The Computer Journal, Vol. 40, N. 2/3, pp. 67-75. 1997. 
Содержимое нижнего колонтитула статьи считать провокацией :-)
PDF.RAR  203 кбайт
PS.RAR    163 кбайт
4
Hirschberg D.S., Lelewer D.A. Context modeling for text compression Обзор классических алгоритмов контекстного моделирования; модификации PPM, использующие небольшой объем оперативной памяти.
Из книги: Image and Text Compression /Eds. J. A. Storer, Kluwer Academic Publishers, 1992.
PDF.RAR   134 кбайт
PS.RAR    58 кбайт
5
Lelewer D.A., Hirschberg D.S. An Order-2 Context Model for Data Compression With Reduced Time and Space Requirements. Изучение характеристик "облегченной" контекстной модели с уровнями 2 и 0.
Technical Report N.90-33.
PDF.RAR   84 кбайт
PS.RAR    37 кбайт
3
Cleary J.G., Teahan W.J. Experiments on the zero frequency problem Исследуется обоснованность использования закона Лапласа в априорных методах оценки вероятности ухода.
Department of Computer Science, University of Waikato, New Zealand, 1995.
PDF.RAR  171 кбайт
PS.RAR     50 кбайт
2
Teahan W.J. Probability estimation for PPM Изучение специфических приемов, применяющихся в PPM, в том числе: deterministic scaling, recency scaling, использование нескольких методов вычисления оценок вероятностей.
Proceedings of the New Zealand Computer Science Research Students Conference, 1995. University of Waikato, Hamilton, New Zealand.
PDF.RAR  43 кбайт
PS.RAR    20 кбайт
5
Moffat A. Implementing the PPM Data Compression Scheme Описание PPMC -- классической реализации PPM.
IEEE Transactions on Communications, Vol. 38, No. 11, pp. 1917-1921, Nov. 1990.
PDF.RAR  75 кбайт
5
Шкарин Д. PPM: one step to practicality Описание PPMII по-русски английскими словами :) Расписана техника вторичной оценки вероятности символов.
Proceedings of the 2002 IEEE Data Compression Conference, Snowbird, Utah, April 2002.
PDF.RAR  189 кбайт
PS.RAR    92 кбайт
5
Witten I., Bell T. The Zero-Frequency Problem: Estimating the Probabilities of Novel Events in Adaptive Text Compression Анализ различных методов априорной оценки вероятности наступления нового события. Описание группы методов оценки вероятности ухода для PPM.
IEEE Transactions on Information Theory, Vol. 37, No. 4, pp.1085-1094, July 1991.
PDF.RAR  178 кбайт
5
Langdon G., Rissanen J. A Double-Adaptive File Compression Algorithm Алгоритм Double-Adaptive File Compression -- дедушка практических контекстных алгоритмов сжатия.
IEEE Transactions on Communications, Vol. COM-31, No.11, pp.1253-1255, Nov. 1983.
PDF.RAR  60 кбайт
3
Cheney J. Compressing XML with Multiplexed Hierarchical PPM Models Некие попытки сжать XML. Результаты перлюстрации не вызвали настойчивого желания ознакомиться с этим манускриптом поближе. Кто бы прочитал и дал оценку?
Proceedings of the IEEE Data Compression Conference, Snowbird, Utah, March 27-29, 2001.
PDF.RAR  181 кбайт
PS.RAR    88 кбайт
?
Effros M. PPM Performance with BWT Complexity: A New Method for Lossless Data Compression Реализация PPM* с помощью структуры данных типа "суффиксное дерево" для поиска контекстов.
Proceedings of the IEEE Data Compression Conference, Snowbird, Utah, March 28-30, 2000.
PDF.RAR  173 кбайт
4
Yeates S.A. The Relationship between Hidden Markov Models and Prediction by Partial Matching Models ...In the past we have studied the use of PPM models to solve the generalised tag-insertion problem. We show that, in general, PPM-based models are a special case of HMMs, with a particular structure, enabling the use of well researched, mature, HMM tools and techniques to solve the tag-insertion problem...
8th Annual New Zealand Engineering and Technology Postgraduate Conference, University of Waikato, August 30-31.
PDF.RAR  48 кбайт
PS.RAR    65 кбайт
?
Shtarkov Yu.M., Zotkin D. Experimental study of some Cleary-Witten algorithm modifications Рассмотрено поведение PPM при различных способах оценки вероятности символов.
Proc. 7th Intl. Workshop on Information Theory, St.Petersbourgh, Russia, June 1995, pp. 211-214.
PDF.RAR  288 кбайт
2
Aberg J., Shtarkov Y.M., Smeets B.J.M. Towards Understanding and Improving Escape Probabilities in PPM Проанализированы способы неадаптивного и адаптивного определения вероятности ухода для незамаскированных контекстов. Предложено несколько стратегий оценки вероятности ухода.
Proceedings of the IEEE Data Compression Conference, Snowbird, Utah, March 25-27, 1997, pp. 22-31.
PDF.RAR  440 кбайт
4
Drinic M., Kirovski D., and Potkonjak M. PPM Model Cleaning Майкрософтовские наймиты :-) открывают для себя возможности по очистке модели PPM от не особо важной информации с целью улучшения сжатия при ограничениях на память. Следует заметить, что аналогичные техники уже давно используются во многих архиваторах, и заметное улучшение -- как у авторов статьи -- возможно только тогда, когда сам алгоритм оценки слабый. Сама по себе статья написана неплохо.
Proceedings of the IEEE Data Compression Conference, Snowbird, Utah, March 25-27, 2003.
PDF.RAR  170 кбайт
3
Aberg J., Shtarkov Y.M. Text Compression by Context Tree Weighting The results of an experimental study of different modifications of the context tree weighting algorithm are described. In particular, the combination of this algorithm with the well-known PPM approach is studied. For one of the considered modifications the decrease of the average (for the Calgary Corpus) coding rate is 0.091 bits compared with PPMD.
Proceedings of IEEE Data Compression Conference, March 25-27, 1997, Snowbird, Utah, pp.377-386.
PDF.RAR  503 кбайт
?
Aberg J., Shtarkov Y.M., Smeets B.J.M. Non-Uniform PPM and Context Tree Models "Non-Uniform" в том смысле, что способы оценки ухода и обновления частот могут отличаться для разных контекстных моделей. Исседованы характеристики ряда статических методов оценки вероятности ухода посредством подбора наилучших параметров для файлов Calgary Corpus. Предложен аппарат для получения теоретико-практических оценок границ улучшения сжатия за счет уточнения предсказания уходов. Методы предполагают получение оценок с помощью CTW и являются в некотором смысле жульническими.
Proceedings of IEEE Data Compression Conference, March 30 - April 1, 1998, Snowbird, Utah, pp.279-288.
PDF.RAR  139 кбайт
?
Horspool R.N., Cormack G.V. Constructing Word-Based Text Compression Algorithms Рассмотрено 4 алгоритма пословного сжатия на основе: адаптивного кодирования по Хаффману, LZW, PPM 1-0, контекстного моделирования первого порядка с учетом предполагаемой части речи. Даются сравнительные результаты на нескольких небольших файлах. Весьма любопытная статья, несмотря на ее возраст. Было бы интересно посмотреть на современные реализации с более сложными схемами моделирования, использующие больший объем памяти.
Страница публикаций R. Nigel Horspool'а
Proceedings of IEEE Data Compression Conference (DCC'92), Snowbird, UT, March 1992, pp. 62-71.
PDF.RAR  23 кбайт
4+


>> Русские материалы | Английские материалы | Исходные тексты компрессоров >> C/C++ | Pascal/Delphi | Assembler

>> Исходные тексты компрессоров >> C/C++ | Pascal/Delphi | Assembler
Hirvola H. HA Известный DOS-архиватор, в котором реализованы алгоритм типа LZ+Ari (метод ASC) и алгоритм типа PPM с априорным способом оценки вероятности ухода (метод HSC).
Язык: C
версия 0.999 beta  59 кбайт
4
Шкарин Д. PPMd Пакет PPMd: библиотека сжатия на основе PPMII и пример ее использования.
За реализацию -- 5+, за скудные комментарии -- балл долой :)
Язык: C++
версия I ревизия 1  73 кбайт
4+
Bloom C. PPMZ Известный экспериментальный компрессор PPMZ.
Язык: C
версия 9.1  93 кбайт
4
Teahan B. PPM-star Оригинальная авторская реализация PPM*.
Язык: C
скачать  12 кбайт
4
Зиганшин Б. CM Довольно экзотическая штука -- статический PPM.
Язык: C++
скачать  13 кбайт
4
Pachkovsky S. Pretty Simple Archiver (PSA) Некий PPM 10-летнего возраста. Кто бы протестировал на стандартных наборах?
Язык: C++
версия 0.91a  46 кбайт
?
Смирнов М. DummyPPM Учебный PPMD, порядок модели равен 5. Текст снабжен краткими комментариями на русском языке.
Язык: С-образный С++
скачать  11 кбайт
4
Смирнов М. Dummy Компрессор с моделью 1-го порядка. Используется в качестве примера в книге "Методы сжатия данных"
Язык: C++
скачать  2 кбайт
2
Nelson М. COMP-2 В статье "Arithmetic Coding + Statistical Modeling = Data Compression" Нельсон дает исходный текст PPM-компрессора с контекстной моделью ограниченного порядка (порядок задается как параметр командной строки). Код хорошо структурирован и описан.
Язык: C
скачать  67 кбайт
5
Timmermans M. Bicom Биективный PPM*, ничего особенно интересного в модели нет, зато есть шифратор/дешифратор, основанный на эталонной реализации стандарта криптографического закрытия AES (она же Rijndael).
Язык: С++
Сайт проекта: http://www3.sympatico.ca/mt0000/
bicom/bicom.html

скачать  104 кбайт
4
Goldman M. LZap Компрессор, написанный на основе исходников из статьи М.Нельсона "Arithmetic Coding + Statistical Modeling = Data Compression". В описании по некой причине указывается, что это реализация DMC. Сие сомнительно -- яблоко от яблони недалеко падает, так что пока лежит здесь. Хотя степень сжатия Calgary Corpus хуже, чем у bzip2, что странно для PPM. Учитывая сомнительное наименование, какое-то сплошное недоразумение получается :-)
Язык: С
0.20.0 Beta  50 кбайт
?
Jeff Prothero (Cynbe) pzip Компрессор, написанный на основе исходников ppmz2. Автором проделана большая работа по прочистке исходников и написанию внятных комментариев. Можно рекомендовать для изучения. Но сжатие и, особенно, скорость остались принципиально хуже, чем у PPMd, хотя в целом лучше, чем у исходного ppmz2. Предполагается сборка под Linux, но проблемы с портированием маловероятны. GPL.
Страница проекта
Язык: С
версия 0.83  47 кбайт
?


>> Исходные тексты компрессоров >> C/C++ | Pascal/Delphi | Assembler
Филинский А. Bee Оригинальный алгоритм смешивания контекстов разных порядков, 4-битный (полубайтовый) алфавит, автоматическая оптимизация алгоритма на заданных наборах файлов с помощью "магических констант".
Язык: Object Pascal, Delphi 5.x.
Сайт проекта: http://compression.ru/fa/
Исходники Bee 0.7.6  213 кбайт
Для компиляции построителя "магических констант" BeeOpt требуется библиотека компонентов RxLib 2.75.
Исходники Bee 0.6.3  233 кбайт
( + исходники построителя "магических констант" BeeOpt + Bee.Exe и BeeOpt.Exe + файл "магических констант" Bee.Ini.)
4+


>> Исходные тексты компрессоров >> C/C++ | Pascal/Delphi | Assembler
Krupnik Alexander THAP Результат дизассемблемирования HAP&PAH 3.0 by Harald Feldman.
Язык: Assembler.
версия 1.02c  23 кбайт
?

Смотрите также материалы:
- Контекстные методы сжатия (без PPM)
- Арифметическое сжатие
- Сжатие с помощью грамматических моделей
- Обзоры универсальных алгоритмов сжатия данных
- Книга "Методы сжатия данных". Раздел 1 "Методы сжатия без потерь"


наверх