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

Контекстные методы

В этом разделе представлено то, что либо нельзя отнести к PPM, либо не хотелось бы :-)

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

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



>> Русские материалы >>
        Ассоциативное кодирование (Associative coding) |
        Динамическое марковское моделирование (сжатие). DMC |
        Прочее

     Английские материалы >>
        Dynamic Markov Modelling (Compression) |
        Context-Tree Weighting |
        Ассоциативное кодирование (Associative coding) |
        Прочее

     Исходные тексты компрессоров
Авторы Название Описание Рейтинг

>> Русские материалы >> Ассоциативное кодирование (Associative coding) | Динамическое марковское моделирование (сжатие). DMC | Прочее
Юкин В. ACB Изложение сути метода ассоциативного кодирования по материалам статьи в журнале Монитор
Конференция fido7.ru.compress, 29.06.97.
TXT.RAR   2 кбайт
?
Буяновский Г. Ассоциативное кодирование Исходники архиватора ACB версии 1.02c с комментариями на русском языке.
TXT.RAR   9 кбайт
5

>> Русские материалы >> Ассоциативное кодирование (Associative coding) | Динамическое марковское моделирование (сжатие). DMC | Прочее
Захаров М. Динамическое сжатие Маркова Краткое изложение основных идей оригинальной статьи Кормака и Хорспула. Прилагается исходный текст на C компрессора Dynamic Markov Compression (DMC) Version 0.0.0, написанного Кормаком.
1993.
HTML.RAR  8 кбайт
5

>> Русские материалы >> Ассоциативное кодирование (Associative coding) | Динамическое марковское моделирование (сжатие). DMC | Прочее
Mahoney M. PAQ1: Описание модели Перевод описания компрессора PAQ1, имеющегося в исходнике этого компрессора.
Перевод Е.Шелвина, 04.09.2002.
2002, Matt Mahoney.
TXT.RAR  5 кбайт
TXT  11 кбайт
Исходный текст PAQ1 (C++):
Скачать  18 кбайт
5


>> Русские материалы >>
        Ассоциативное кодирование (Associative coding) |
        Динамическое марковское моделирование (сжатие). DMC |
        Прочее

     Английские материалы >>
        Dynamic Markov Modelling (Compression) |
        Context-Tree Weighting |
        Ассоциативное кодирование (Associative coding) |
        Прочее

     Исходные тексты компрессоров

>> Английские материалы >> Dynamic Markov Modelling (Compression) | Context-Tree Weighting | Ассоциативное кодирование (Associative coding) | Прочее
Cormack G., Horspool N. Data Compression Using Dynamic Markov Modelling Изложение общего подхода к сжатию на основе использования марковской модели источника в виде конечного автомата. Оригинальное описание алгоритма Dynamic Markov Compression (DMC, Динамическое марковское сжатие).
The Computer Journal, Vol.30, No.6, pp.541-550, 1987.
PDF.RAR  57 кбайт
PS.RAR    51 кбайт
5
Bell T., Moffat A. A note on the DMC data compression scheme Показано, что в Dynamic Markov Compression не используется потенциал модели источника на основе конечного автомата, и что реально модели PPM и DMC относятся к одному семейству.
The Computer Journal, Vol.32, No.1, pp.16-20, 1989.
PDF.RAR  127 кбайт
4
Teuhola J., Raita T. Application of a Finite-State Model to Text Compression Дальнейшее развитие Dynamic Markov Modelling: описание метода Generalized DMC (GDMC), работающего с недвоичным алфавитом.
The Computer Journal, Vol.36, No.7, pp.607-614, 1993.
PDF.RAR  136 кбайт
5
Franti P., Hatakka T. Context Model Automata for Text Compression Finite-state automata offer an alternative approach in the implementation of context models where the states in the automata cannot in general be assigned by a single context. Despite the potential of this approach, it makes the design of the modelling more problematic because the exact behaviour of the model is not known. Here we propose a simple formalism—context model automata (CMA)— that gives an exact interpretation for the minimum context belonging to each state in the automaton. The formalism is general enough to simulate context models such as PPM and GDMC. Using the CMA formalism as our tool, we study the behaviour of the above two context models.
The Computer Journal, Vol.41, No.7, pp.474-485, 1998.
PDF.RAR  142 кбайт
?
Bunton S. On-Line Stochastic Processes in Data Compression Докторская диссертация Сьюзен Бантон. Одно из немногих серьезных исследований техник контекстного моделирования. Подход Dynamic Markov Modelling проанализирован и усовершенствован.
PhD thesis, University of Washington, 1996.
PDF.RAR  800 кбайт
PS.RAR   345 кбайт
5

>> Английские материалы >> Dynamic Markov Modelling (Compression) | Context-Tree Weighting | Ассоциативное кодирование (Associative coding) | Прочее
Willems F., Shtarkov Y., Tjalkens T. The Context Tree Weighting Method: Basic Properties We describe a sequential universal data compression procedure for binary tree sources that performs the "double mixture". Using a context tree, this method weights in an eficient recursive way the coding distributions corresponding to all bounded memory tree sources, and achieves a desirable coding distribution for tree sources with an unknown model and unknown parameters...
IEEE Transactions on Information Theory, Vol.41, No.3, pp.653-664, 1995.
PDF.RAR  185 кбайт
PS.RAR    148 кбайт
?
Willems F., Shtarkov Y., Tjalkens T. Reflections on "The Context-Tree Weighting Method: Basic Properties"  
IEEE Information Theory Society Newsletter, Vol. 47, p.1 & pp.20-27, March 1997.
PDF.RAR  172 кбайт
PS.RAR    89 кбайт
?
Willems F. Extensions to the Context Tree Weighting Method We modify the basic context tree weighting method so that past symbols are not needed, and that the context tree depth is infinite. For stationary ergodic sources we now achieve entropy.
Proceedings of IEEE International Symposium on Information Theory, Trondheim, Norway, June 27 - July 1, 1994, p.387.
PDF.RAR  63 кбайт
PS.RAR    34 кбайт
?
Willems F. The Context-Tree Weighting Method: Extensions Полная статья, тезисы которой приведены выше.
IEEE Transactions on Information Theory, Vol.44, March 1998, pp. 792-798.
PDF.RAR  183 кбайт
PS.RAR    86 кбайт
?
Willems F., Shtarkov Y., Tjalkens T. Context Weighting for General Finite-Context Sources Context weighting procedures are presented for sources with models (structures) in four different classes. Although the procedures are designed for universal data compression purposes, their generality allows application in the area of classification.
IEEE Transactions on Information Theory, Vol.42, pp.1514-1520, Sep. 1996.
PDF.RAR  214 кбайт
PS.RAR    104 кбайт
?
Volf P., Willems F. Context Maximizing: Finding MDL Decision Trees We present an application of the context weighting algorithm. Our objective is to classify objects with decision trees. The best tree will be searched for with the Minimum Description Length Principle. In order to find these trees, we modified the context weighting algorithm.
Symposium on Information Theory in the Benelux, Vol.15, pp.192-200, Loavain-la-Neuve, Belgium, May 1994.
PDF.RAR  120 кбайт
PS.RAR    64 кбайт
?
Volf P., Willems F. A Study of the Context Tree Maximizing Method One can adapt the context tree weighting method in such a way, that it will find the minimum description length model (MDL-model) that corresponds to the data. In this paper this new algorithm, the context tree maximizing algorithm, and a few modifications of the algorithm will be studied, in particular, its performance if we apply it for data compression.
Symposium on Information Theory in the Benelux, vol. 16, 1995.
PDF.RAR  133 кбайт
PS.RAR    73 кбайт
?
Volf P., Willems F. Context-Tree Weighting For Extended Tree Sources At the ISIT'95 Suzuki presented a context weighting algorithm that covered a more general class of sources than the context-tree weighting method, at the cost of some extra complexity. Here his algorithm will be compared to an algorithm, that covers the same model class.
Symposium on Information Theory in the Benelux, vol. 17, pp. 95-101, Enschede, The Netherlands, May 30-31, 1996.
PDF.RAR  234 кбайт
PS.RAR    97 кбайт
?
Volf P., Willems F. A Context-Tree Branch-Weighting Algorithm The context-tree weighting algorithm is a universal source coding algorithm for binary tree sources. In [2] the algorithm is modified for byte-oriented tree sources. This paper describes the context-tree branch-weighting algorithm, which can reduce the number of parameters for such sources, without increasing the complexity significantly.
Symposium on Information Theory in the Benelux, vol. 18, 1997.
PDF.RAR  137 кбайт
PS.RAR    72 кбайт
?
Volf P., Willems F. Switching Between Two Universal Source Coding Algorithms This paper discusses a switching method which can be used to combine two sequential universal source coding algorithms. The switching method treats these two algorithms as black-boxes and can only use their estimates of the probability distributions for the consecutive symbols of the source sequence... Empirical results show that all three weighting algorithms give a performance better than the performance of the source coding algorithms they combine.
IEEE Data Compression Conference, Snowbird, Utah, USA, March, 1998, pp. 491-500.
PDF.RAR  144 кбайт
PS.RAR    70 кбайт
?
Volf P., Willems F. The Switching Method: Elaborations The switching method is a scheme which combines two universal source coding algorithms... The switching algorithm is an efficient weighting algorithm that uses this switching method. This paper focuses on the companion algorithm, the algorithm running in parallel to the main CTW-algorithm.
Symposium on Information Theory in the Benelux, vol. 19, 1998.
PDF.RAR  123 кбайт
PS.RAR    58 кбайт
?
Willems F., Tjalkens T. Complexity Reduction of the Context-Tree Weighting Method We present a method to decrease the storage and communication complexity of the context-tree weighting method. This method is based on combining the estimated probability of a node in the context tree and weighted probabilities of its children in one single variable. This variable is represented by its logarithm.
Proceedings of the 18th Symposium on Information Theory in the Benelux, Veldhoven, The Netherlands, May 15 & 16, 1997, pp.123-130.
PDF.RAR  133 кбайт
PS.RAR    75 кбайт
?
Tjalkens T., Willems F. Implementing the Context-Tree Weighting Method: Arithmetic Coding The context-tree weighting algorithm [6] is an efficient universal source coding method for tree sources. Although a finite accuracy version of this algorithm has been analysed in [8], it is better to implement the algorithm as proposed in [7]. There it was suggested to store in each nodesof the context tree ... Here we present the arithmetic coding procedure that matches to this implementation. It is based on Tjalkens' Ph.D. thesis [4] in which tables are used to circumvent multiplications. We also present a very simple carry-blocking procedure and briefly analyse it.
International Conference on Combinatorics, Information Theory & Statistics, July 18-20, 1997, in Portland, Maine.
PDF.RAR  126 кбайт
PS.RAR    68 кбайт
?
Volf P., Willems F. On The Context Tree Maximizing Algorithm The context tree weighting algorithm was introduced at the 1993 ISIT. Here we are concerned with the context tree maximizing algorithm. We discuss several modifications of this algorithm.
IEEE ISIT, 1995.
PDF.RAR  64 кбайт
PS.RAR    32 кбайт
?
Volf P. Context-Tree Weighting for Text-Sources The context-tree weighting (CTW) algorithm is a universal source coding algorithm for binary tree sources. This paper presents 3 techniques that modify the CTW algorithm for non-binary, and especially for ASCII-character oriented, tree sources.
IEEE ISIT, Ulm, Germany, June 20 - July 4, 1997.
PDF.RAR  64 кбайт
PS.RAR    34 кбайт
?
Tjalkens T., Volf P., Willems F. A Context-Tree Weighting Method for Text Generating Sources Просто одностраничный тезис о мощи CTW и плакаты к выступлению :-)
Proceedings of IEEE Data Compression Conference, March 25-27, 1997, Snowbird, Utah.
PDF.RAR  263 кбайт
PS.RAR    171 кбайт
?
Willems F. Coding for a Binary Independent Piecewise-Identically Distributed Source Two weighting procedures are presented for compaction of output sequences generated by binary independent sources whose unknown parameter may change occasionally. The resulting codes need no knowledge of the sequence length T, i.e. they are strongly sequential, and also the number of parameter changes is unrestricted.
IEEE Transactions on Information Theory, Vol.42, No.6, pp.2210-2217, 1996.
PDF.RAR  203 кбайт
PS.RAR    102 кбайт
?
Sadakane K., Okazaki T., Imai H. Implementing the Context Tree Weighting Method for Text Compression ...We extend the method for multi-alphabet sequences and show a simple implementation using PPM techniques. We also propose a method to optimize a parameter of the context tree weighting for binary alphabet case. Experimental results on texts and DNA sequences show that the performance of PPM can be improved by combining the context tree weighting and that DNA sequences can be compressed in less than 2.0 bpc.
Proceedings of IEEE Data Compression Conference, March 28-30, 2000, Snowbird, Utah, pp.123-132.
PDF.RAR  94 кбайт
PS.RAR    144 кбайт
?
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 кбайт
?

>> Английские материалы >> Dynamic Markov Modelling (Compression) | Context-Tree Weighting | Ассоциативное кодирование (Associative coding) | Прочее
Lambert S., Cohn M. ACB -- Reference material Материалы про ACB, собранные Sean Lambert и Martin Cohn
RAR  46 кбайт
3

>> Английские материалы >> Dynamic Markov Modelling (Compression) | Context-Tree Weighting | Ассоциативное кодирование (Associative coding) | Прочее
Weinberger M., Lempel A., Ziv J. A Sequential Algorithm for the Universal Coding of Finite Memory Sources The estimation and universal compression of discrete sources are considered and a sequential algorithm for the universal coding of finite memory sources, attaining asymptotically minimum redundancy is presented. The algorithm performs an on-line estimation of the source states and uses an arithmetic code.
Теоретическое обоснование асимптотически оптимального последовательного алгоритма кодирования FSMX источников.
IEEE Transactions on Information Theory, Vol.38, No.3, pp.1002-1014, May 1992.
PDF.RAR  616 кбайт
4
Mahoney M. The PAQ1 Data Compression Program Пример реализации взвешивания оценок нескольких предикторов.
This paper describes the PAQ1 lossless data compression program. PAQ1 is an arithmetic encoder using a weighted average of five bit-level predictors... The aging of training statistics makes the model nonstationary, which gives excellent compression for mixed data types. PAQ1 compresses the concatenated Calgary corpus to 1.824 bits per character...
Florida Tech., CS Dept. Draft, Jan. 20, 2002, revised Mar. 19.
PDF  137 кбайт
Исходный текст PAQ1 (C++):
Скачать  18 кбайт
5
Mahoney M. Adaptive Weighing of Context Models for Lossless Data Compression Описание PAQ6, а заодно и предыдущих версий PAQ. Необходимо к прочтению любителям максимального сжатия.
2005, Florida Tech. Technical Report TR-CS-2005-16.
PDF  80 кбайт
Домашняя страница с исходными текстами
5


>> Русские материалы | Английские материалы | Исходные тексты компрессоров
Буяновский Г. ACB Описание алгоритма и исходники на Си и Ассемблере, используемые в архиваторе ACB версии 1.02. На первый взгляд соответствует статье в Мониторе.
Язык: C, Assembler
Скачать  21 кбайт
4
Mahoney M. PAQ Статистический компрессор, реализующий взвешивание оценок нескольких контекстных предикторов.
Авторский сайт: http://cs.fit.edu/~mmahoney/compression/
Язык: C++
Версии (свежие версии скачивайте с авторского сайта):
PAQ4  16 кбайт
Реализовано адаптивное взвешивание. Обновлено 16.10.2003.
PAQ3n  58 кбайт
Улучшена реализация SSE и добавлен предиктор (подмодель). Обновлено 9.09.2003.
PAQ3  13 кбайт
Улучшена реализация SSE и еще по мелочи. Обновлено 3.09.2003.
PAQ2  18 кбайт
Добавлен механизм SSE (secondary symbol estimation). Обновлено 11.05.2003.
PAQ1  18 кбайт
5
Franken E., Peeters M. CTW (Context Tree Weighting) Реализация CTW, выполняемая двумя студентами под руководством Willems'а. Очень тормозной компрессор, что, видимо, не в последнюю очередь определяется структурой данных, неудачной с точки зрения скоростной оптимизации.
Сайт проекта: http://www.ele.tue.nl/ctw/
Язык: C++
версия 0.1  48 кбайт
Описание реализации и использования:
PDF.RAR  311 кбайт
4
Богатов Р.Н. Hipp Экспериментальный компрессор, использующий:
- двойное ограничение глубины суффиксного дерева при использовании объединения детерминированных узлов (path compression);
- полную статистику по фиксированно-удалённым контекстам (частному случаю sparse contexts).
См. описание Hipp v0.5819 с результатами экспериментов.
Язык: C++
Hipp v0.5819 с исходниками 59 Кб (Visual C++ 7.0)
?

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


наверх