Óíèâåðñàëüíûå àëãîðèòìû ñæàòèÿ äàííûõ:
Êîíòåêñòíûå ìåòîäû
 ýòîì ðàçäåëå ïðåäñòàâëåíî òî, ÷òî ëèáî íåëüçÿ îòíåñòè ê 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 "Ìåòîäû ñæàòèÿ áåç ïîòåðü"
íàâåðõ