Универсальные алгоритмы сжатия данных:
Предсказание по частичному совпадению
(Prediction by Partial Matching, PPM)
>>
Русские материалы |
Английские материалы |
Исходные тексты компрессоров
Смотрите также материалы:
- Контекстные методы сжатия (без PPM)
- Арифметическое сжатие
- Сжатие с помощью грамматических моделей
- Обзоры универсальных алгоритмов сжатия данных
- Книга "Методы сжатия данных". Раздел 1 "Методы сжатия без потерь"
|
Русские материалы | Английские материалы | Исходные тексты компрессоров |
|||
| Авторы | Название | Описание | Рейтинг |
| Шкарин Д.А. | Повышение эффективности алгоритма PPM | Для алгоритма PPM предложены новые определения обобщенных частот символов и "уходов", позволившие заметно увеличить эффективность кодирования (сжатия) различных типов реальных дискретных данных без искажений. Проблемы передачи информации, том 37, вып.3, 2001. С44-54. PDF.RAR 96 кбайт PS.RAR 84 кбайт |
|
| Смирнов М. | PPM FAQ | Введение в PPM. Больше и добавить нечего :) 25.01.2000 HTML 33 кбайт TXT.RAR 11 кбайт |
|
| 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 кбайт |
|
| Штарков Е.С., Абузова И.В. (гм...) | Modeling for Text Compression... Тьфу... Применение контекстуального моделирования для сжатия информации | Клинический случай плагиата: передран один ко одному кусок русского перевода обзора Modeling for Text Compression и объявлен своей работой. Я рыдал...
Известия Тульского гос. унив. Серия Математика. Механика. Информатика. Том 3. Выпуск 2. Информатика, 1997, С.102-107. PDF.RAR 284 кбайт |
|
|
>> Русские материалы | Английские материалы | Исходные тексты компрессоров |
|||
| Cleary J.G., Witten I.H. | Data compression using adaptive coding and partial string matching |
IEEE Transactions on Communications, Vol. 32(4), pp.396-402, April 1984. PDF.RAR 181 кбайт RTF.RAR 72 кбайт |
|
| Bunton S. | On-Line Stochastic Processes in Data Compression | Докторская диссертация Сьюзен Бантон. Одно из немногих серьезных исследований техник контекстного моделирования.
PhD thesis, University of Washington, 1996. PDF.RAR 800 кбайт PS.RAR 345 кбайт |
|
| 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 кбайт |
|
| 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 кбайт |
|
| 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 кбайт |
|
| Bloom C. | Solving the problems of context modeling | Описание PPMZ. Одно из первых описаний SEE.
California Institute of Technology, 1996. PDF.RAR 82 кбайт PS.RAR 41 кбайт |
|
| 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 кбайт |
|
| 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 кбайт |
|
| 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 кбайт |
|
| 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 кбайт |
|
| 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 кбайт |
|
| 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 кбайт |
|
| Шкарин Д. | PPM: one step to practicality | Описание PPMII по-русски английскими словами :) Расписана техника вторичной оценки вероятности символов.
Proceedings of the 2002 IEEE Data Compression Conference, Snowbird, Utah, April 2002. PDF.RAR 189 кбайт PS.RAR 92 кбайт |
|
| 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 кбайт |
|
| 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 кбайт |
|
| 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 кбайт |
|
| 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 кбайт |
|
| 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 кбайт |
|
| 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 кбайт |
|
| 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 кбайт |
|
|
>> Русские материалы | Английские материалы | Исходные тексты компрессоров >> C/C++ | Pascal/Delphi | Assembler |
|||
|
>> Исходные тексты компрессоров >> C/C++ | Pascal/Delphi | Assembler |
|||
| Hirvola H. | HA | Известный DOS-архиватор, в котором реализованы алгоритм типа LZ+Ari (метод ASC) и алгоритм типа PPM с априорным способом оценки вероятности ухода (метод HSC).
Язык: C версия 0.999 beta 59 кбайт |
|
| Шкарин Д. | PPMd | Пакет PPMd: библиотека сжатия на основе PPMII и пример ее использования.
За реализацию -- 5+, за скудные комментарии -- балл долой :) Язык: C++ версия I ревизия 1 73 кбайт |
|
| Bloom C. | PPMZ | Известный экспериментальный компрессор PPMZ.
Язык: C версия 9.1 93 кбайт |
|
| Teahan B. | PPM-star | Оригинальная авторская реализация PPM*.
Язык: C скачать 12 кбайт |
|
| Зиганшин Б. | CM | Довольно экзотическая штука -- статический PPM.
Язык: C++ скачать 13 кбайт |
|
| Pachkovsky S. | Pretty Simple Archiver (PSA) | Некий PPM 10-летнего возраста. Кто бы протестировал на стандартных наборах?
Язык: C++ версия 0.91a 46 кбайт |
|
| Смирнов М. | DummyPPM | Учебный PPMD, порядок модели равен 5. Текст снабжен краткими комментариями на русском языке.
Язык: С-образный С++ скачать 11 кбайт |
|
| Смирнов М. | Dummy | Компрессор с моделью 1-го порядка. Используется в качестве примера в книге "Методы сжатия данных"
Язык: C++ скачать 2 кбайт |
|
| Nelson М. | COMP-2 | В статье "Arithmetic Coding + Statistical Modeling = Data Compression" Нельсон дает исходный текст PPM-компрессора с контекстной моделью ограниченного порядка (порядок задается как параметр командной строки). Код хорошо структурирован и описан.
Язык: C скачать 67 кбайт |
|
| Timmermans M. | Bicom | Биективный PPM*, ничего особенно интересного в модели нет, зато есть шифратор/дешифратор, основанный на эталонной реализации стандарта криптографического закрытия AES (она же Rijndael).
Язык: С++ Сайт проекта: http://www3.sympatico.ca/mt0000/ bicom/bicom.html скачать 104 кбайт |
|
| 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.) |
|
|
>> Исходные тексты компрессоров >> C/C++ | Pascal/Delphi | Assembler | |||
| Krupnik Alexander | THAP |
Результат дизассемблемирования HAP&PAH 3.0 by Harald Feldman.
Язык: Assembler. версия 1.02c 23 кбайт |
|
Смотрите также материалы:
- Контекстные методы сжатия (без PPM)
- Арифметическое сжатие
- Сжатие с помощью грамматических моделей
- Обзоры универсальных алгоритмов сжатия данных
- Книга "Методы сжатия данных". Раздел 1 "Методы сжатия без потерь"
наверх