Универсальные алгоритмы сжатия данных:
Контекстные методы
В этом разделе представлено то, что либо нельзя отнести к 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 кбайт |
|
|
>> Русские материалы >> Ассоциативное кодирование (Associative coding) | Динамическое марковское моделирование (сжатие). DMC | Прочее |
|||
| Захаров М. | Динамическое сжатие Маркова | Краткое изложение основных идей оригинальной статьи Кормака и Хорспула. Прилагается исходный текст на C компрессора Dynamic Markov Compression (DMC) Version 0.0.0, написанного Кормаком.
1993. HTML.RAR 8 кбайт |
|
|
>> Русские материалы >> Ассоциативное кодирование (Associative coding) | Динамическое марковское моделирование (сжатие). DMC | Прочее |
|||
| Mahoney M. | PAQ1: Описание модели | Перевод описания компрессора PAQ1, имеющегося в исходнике этого компрессора.
Перевод Е.Шелвина, 04.09.2002. 2002, Matt Mahoney. TXT.RAR 5 кбайт TXT 11 кбайт Исходный текст PAQ1 (C++): Скачать 18 кбайт |
|
|
>> Русские материалы >> Ассоциативное кодирование (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 кбайт |
|
| 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 кбайт |
|
| 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 кбайт |
|
| 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 кбайт |
|
|
>> Английские материалы >> 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 кбайт |
|
|
>> Английские материалы >> 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 кбайт |
|
| 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 кбайт |
|
| Mahoney M. | Adaptive Weighing of Context Models for Lossless Data Compression | Описание PAQ6, а заодно и предыдущих версий PAQ. Необходимо к прочтению любителям максимального сжатия.
2005, Florida Tech. Technical Report TR-CS-2005-16. PDF 80 кбайт Домашняя страница с исходными текстами |
|
|
>> Русские материалы | Английские материалы | Исходные тексты компрессоров | |||
| Буяновский Г. | ACB | Описание алгоритма и исходники на Си и Ассемблере, используемые в архиваторе ACB версии 1.02. На первый взгляд соответствует статье в Мониторе.
Язык: C, Assembler Скачать 21 кбайт |
|
| 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 кбайт |
|
| Franken E., Peeters M. | CTW (Context Tree Weighting) | Реализация CTW, выполняемая двумя студентами под руководством Willems'а.
Очень тормозной компрессор, что, видимо, не в последнюю очередь определяется структурой данных, неудачной с точки зрения скоростной оптимизации.
Сайт проекта: http://www.ele.tue.nl/ctw/ Язык: C++ версия 0.1 48 кбайт Описание реализации и использования: PDF.RAR 311 кбайт |
|
| Богатов Р.Н. | Hipp | Экспериментальный компрессор, использующий: - двойное ограничение глубины суффиксного дерева при использовании объединения детерминированных узлов (path compression); - полную статистику по фиксированно-удалённым контекстам (частному случаю sparse contexts). См. описание Hipp v0.5819 с результатами экспериментов. Язык: C++ Hipp v0.5819 с исходниками 59 Кб (Visual C++ 7.0) |
|
Смотрите также материалы:
- Предсказание по частичному совпадению (PPM)
- Арифметическое сжатие
- Сжатие с помощью грамматических моделей
- Обзоры универсальных алгоритмов сжатия данных
- Книга "Методы сжатия данных". Раздел 1 "Методы сжатия без потерь"
наверх