Data Compression Using Adaptive Coding and Partial String Matching
J. Cleary, Ian H. Witten · IEEE Transactions on Communications · 1984
The recently developed technique of arithmetic coding, in conjunction with a Markov model of the source, is a powerful method of data compression in situations where a linear treatment is inappropriate. Adaptive coding allows the model to be constructed dynamically by both encoder and decoder during the course of the transmission, and has been shown to incur a smaller coding overhead than explicit transmission of the model's statistics. 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, and reports experimental results which show that mixed-case English text can be coded in as little as 2.2 bits/ character with no prior knowledge of the source.
Cited by 1,241 works. doi:10.1109/tcom.1984.1096090
Authors
References
- Compression of individual sequences via variable-rate coding
- The C programming language
- Universal modeling and coding
- Enumerative source encoding
- Experiments with Linear Prediction in Television
- Source coding algorithms for fast data compression
- Compression of Black-White Images with Arithmetic Coding
- Decision making in Markov chains applied to the problem of pattern recognition
- Recognition of continuously read natural corpus
- International digital facsimile coding standards