The DOI matches its Crossref record; 53 of the 53 references it cites were found in a registry or an index.
Modeling for text compression
Open accessAbstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A Mathematical Theory of Communication
Shannon, C. E. (1948) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1948.tb01338.x · Cited by 88,486
The Art of Computer Programming
Knuth, D. E. (1968) · Cited by 15,999
A Method for the Construction of Minimum-Redundancy Codes
Huffman, D. (1952) · Proceedings of the IRE · doi:10.1109/jrproc.1952.273898 · Cited by 6,334
A universal algorithm for sequential data compression
Ziv, J., & Lempel, A. (1977) · IEEE Transactions on Information Theory · doi:10.1109/tit.1977.1055714 · Cited by 5,456
An introduction to hidden Markov models
Rabiner, L., & Juang, B. (1986) · IEEE ASSP Magazine · doi:10.1109/massp.1986.1165342 · Cited by 4,775
Baum, L. E., Petrie, T., Soules, G., & Weiss, N. (1970) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177697196 · Cited by 4,297
The Art of Computer Programming: Volume 3: Sorting and Searching
Knuth, D. E. (1973) · Cited by 3,955
Compression of individual sequences via variable-rate coding
Ziv, J., & Lempel, A. (1978) · IEEE Transactions on Information Theory · doi:10.1109/tit.1978.1055934 · Cited by 3,432
Arithmetic coding for data compression
Witten, I. H., Neal, R. M., & Cleary, J. G. (1987) · Communications of the ACM · doi:10.1145/214762.214771 · Cited by 2,877
Self-citationOn the Complexity of Finite Sequences
Lempel, A., & Ziv, J. (1976) · IEEE Transactions on Information Theory · doi:10.1109/tit.1976.1055501 · Cited by 2,717
Prediction and Entropy of Printed English
Shannon, C. E. (1951) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1951.tb01366.x · Cited by 2,686
The Art of Computer Programming
Worlton, W. J. (1968) · Nuclear Science and Engineering · doi:10.13182/nse68-a19548 · Cited by 2,251
A Technique for High-Performance Data Compression
Welch (1984) · Computer · doi:10.1109/mc.1984.1659158 · Cited by 2,182
Data Compression Using Adaptive Coding and Partial String Matching
Cleary, J., & Witten, I. (1984) · IEEE Transactions on Communications · doi:10.1109/tcom.1984.1096090 · Cited by 1,241
Self-citationUniversal codeword sets and representations of the integers
Elias, P. (1975) · IEEE Transactions on Information Theory · doi:10.1109/tit.1975.1055349 · Cited by 1,165
Levinson, S. E., Rabiner, L. R., & Sondhi, M. M. (1983) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1983.tb03114.x · Cited by 978
PATRICIA—Practical Algorithm To Retrieve Information Coded in Alphanumeric
Morrison, D. R. (1968) · Journal of the ACM · doi:10.1145/321479.321481 · Cited by 969
Inductive Inference: Theory and Methods
Angluin, D., & Smith, C. H. (1983) · ACM Computing Surveys · doi:10.1145/356914.356918 · Cited by 887
Complexity of automaton identification from given data
Gold, E. M. (1978) · Information and Control · doi:10.1016/s0019-9958(78)90562-4 · Cited by 771
Rissanen, J., & Langdon, G. G. (1979) · IBM Journal of Research and Development · doi:10.1147/rd.232.0149 · Cited by 751
Data compression via textual substitution
Storer, J. A., & Szymanski, T. G. (1982) · Journal of the ACM · doi:10.1145/322344.322346 · Cited by 634
A universal data compression system
Rissanen, J. (1983) · IEEE Transactions on Information Theory · doi:10.1109/tit.1983.1056741 · Cited by 631
Chen, S., McLaughlin, S., Grant, P., et al. (1993) · Cited by 613
Variations on a theme by Huffman
Gallager, R. (1978) · IEEE Transactions on Information Theory · doi:10.1109/tit.1978.1055959 · Cited by 546
An Introduction to Arithmetic Coding
Langdon, G. G. (1984) · IBM Journal of Research and Development · doi:10.1147/rd.282.0135 · Cited by 527
A locally adaptive data compression scheme
Bentley, J. L., Sleator, D. D., Tarjan, R. E., & Wei, V. K. (1986) · Communications of the ACM · doi:10.1145/5684.5688 · Cited by 523
Generalized Kraft Inequality and Arithmetic Coding
Rissanen, J. J. (1976) · IBM Journal of Research and Development · doi:10.1147/rd.203.0198 · Cited by 510
Rissanen, J., & Langdon, G. (1981) · IEEE Transactions on Information Theory · doi:10.1109/tit.1981.1056282 · Cited by 454
Lelewer, D. A., & Hirschberg, D. S. (1987) · ACM Computing Surveys · doi:10.1145/45072.45074 · Cited by 377
Combinatorial Algorithms on Words
(1985) · Springer eBooks · doi:10.1007/978-3-642-82456-2 · Cited by 289
Counting large numbers of events in small registers
Morris, R. (1978) · Communications of the ACM · doi:10.1145/359619.359627 · Cited by 238
A convergent gambling estimate of the entropy of English
Cover, T., & King, R. (1978) · IEEE Transactions on Information Theory · doi:10.1109/tit.1978.1055912 · Cited by 220
Data Compression Using Dynamic Markov Modelling
Cormack, G. V., & Horspool, R. N. S. (1987) · The Computer Journal · doi:10.1093/comjnl/30.6.541 · Cited by 213
Using simulated annealing to design good codes
Gamal, A. E., Hemachandra, L., Shperling, I., & Wei, V. (1987) · IEEE Transactions on Information Theory · doi:10.1109/tit.1987.1057277 · Cited by 213
Source coding algorithms for fast data compression
Pasco, R. C. (1976) · Cited by 191
Data compression with finite windows
Fiala, E. R., & Greene, D. H. (1989) · Communications of the ACM · doi:10.1145/63334.63341 · Cited by 178
Moffat, A. (1989) · Software: Practice and Experience · doi:10.1002/spe.4380190207 · Cited by 172
Interval and recency rank source coding: Two on-line adaptive variable-length schemes
Eliaš, P. (1987) · IEEE Transactions on Information Theory · doi:10.1109/tit.1987.1057251 · Cited by 113
SYSTEM IDENTIFICATION, APPROXIMATION AND COMPLEXITY
Gaines, B. R. (1977) · International Journal of General Systems · doi:10.1080/03081077708934759 · Cited by 113
Application of splay trees to data compression
Jones, D. W. (1988) · Communications of the ACM · doi:10.1145/63030.63036 · Cited by 95
A note on the Ziv - Lempel model for compressing individual sequences (Corresp.)
Langdon, G. G. (1983) · IEEE Transactions on Information Theory · doi:10.1109/tit.1983.1056645 · Cited by 85
Common phrases and minimum-space text storage
Wagner, R. A. (1973) · Communications of the ACM · doi:10.1145/361972.361982 · Cited by 78
Behaviour/structure transformations under uncertainty
Gaines, B. R. (1976) · International Journal of Man-Machine Studies · doi:10.1016/s0020-7373(76)80005-3 · Cited by 68
Algorithms for adaptive Huffman codes
Cormack, G. V., & Horspool, R. N. (1984) · Information Processing Letters · doi:10.1016/0020-0190(84)90021-8 · Cited by 60
A general minimum-redundancy source-coding algorithm
Guazzo, M. (1980) · IEEE Transactions on Information Theory · doi:10.1109/tit.1980.1056143 · Cited by 59
Source encoding using syntactic information source models
Cameron, R. D. (1988) · IEEE Transactions on Information Theory · doi:10.1109/18.9782 · Cited by 53
Fifth-Generation Computer Systems: A Japanese Project
Moto-oka, & Stone (1984) · Computer · doi:10.1109/mc.1984.1659076 · Cited by 48
On the privacy afforded by adaptive text compression
Witten, I. H., & Cleary, J. G. (1988) · Computers & Security · doi:10.1016/0167-4048(88)90580-9 · Cited by 48
Self-citationLongest‐match string searching for ziv‐lempel compression
Bell, T., & Kulp, D. (1993) · Software Practice and Experience · doi:10.1002/spe.4380230705 · Cited by 31
Self-citationAPPROXIMATE, NON-DETERMINISTIC MODELLING OF BEHAVIOUR SEQUENCES
Witten, I. H. (1979) · International Journal of General Systems · doi:10.1080/03081077908960883 · Cited by 15
Self-citationA unifying theory and improvements for existing approaches to text compression
Bell, T. (1986) · UC Research Repository (University of Canterbury) · doi:10.26021/2003 · Cited by 14
Self-citationADAPTIVE TEXT COMPRESSION TO ENHANCE A MODEM
Darragh, J. J., Witten, I. H., & Cleary, J. G. (1983) · Libraries and Cultural Resources (University of Calgary) · doi:10.11575/prism/30523 · Cited by 2
Self-citationFast Ziv-Lempel decoding using RISC architecture
Jaggar, D. V. (1989) · UC Research Repository (University of Canterbury) · Cited by 1
Metadata
- Authors
- Bell, T., Witten, I. H., & Cleary, J. G.
- Venue
- ACM Computing Surveys
- Published
- 1989-12
- Volume
- 21
- Issue
- 4
- Pages
- 557-591
- ISSN
- 0360-0300 (ISSN-L)
- 1557-7341
- OpenAlex
- W2012603689
- Cited by
- 261
- References
- 53
- FWCI
- 8.97
- Type
- journal article
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.