Modeling for text compression
Tim Bell, Ian H. Witten, John G. Cleary · ACM Computing Surveys · 1989
The best schemes for text compression use large models to help them predict which characters will come next. The actual next characters are coded with respect to the prediction, resulting in compression of information. Models are best formed adaptively, based on the text seen so far. This paper surveys successful strategies for adaptive modeling that are suitable for use in practical text compression systems. The strategies fall into three main classes: finite-context modeling, in which the last few characters are used to condition the probability distribution for the next one; finite-state modeling, in which the distribution is conditioned by the current state (and which subsumes finite-context modeling as an important special case); and dictionary modeling, in which strings of characters are replaced by pointers into an evolving dictionary. A comparison of different methods on the same sample texts is included, along with an analysis of future research directions.
Cited by 261 works. doi:10.1145/76894.76896 Open-access PDF
Authors
References
- A Mathematical Theory of Communication
- The Art of Computer Programming
- A Method for the Construction of Minimum-Redundancy Codes
- The Art of Computer Programming: Volume 3: Sorting and Searching
- A universal algorithm for sequential data compression
- The Art of Computer Programming
- Prediction and Entropy of Printed English
- A Maximization Technique Occurring in the Statistical Analysis of Probabilistic Functions of Markov Chains
- Compression of individual sequences via variable-rate coding
- Inductive Inference: Theory and Methods