The DOI matches its Crossref record; 31 of the 31 references it cites were found in a registry or an index.
Data compression
Abstract
This paper surveys a variety of data compression methods spanning almost 40 years of research, from the work of Shannon, Fano, and Huffman in the late 1940s to a technique developed in 1986. The aim of data compression is to reduce redundancy in stored or communicated data, thus increasing effective data density. Data compression has important application in the areas of file storage and distributed systems. Concepts from information theory as they relate to the goals and evaluation of data compression methods are discussed briefly. A framework for evaluation and comparison of methods is constructed and applied to the algorithms presented. Comparisons of both theoretical and empirical natures are reported, and possibilities for future research are suggested.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
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 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
Information Theory and Reliable Communication.
Lee, P. M., & Gallager, R. T. (1970) · Journal of the Royal Statistical Society. Series A (General) · doi:10.2307/2344305 · Cited by 5,399
Information Theory and Reliable Communication
Bell, D. A. (1969) · Electronics and Power · doi:10.1049/ep.1969.0319 · Cited by 4,012
ASH, R. B. (1966) · Cited by 3,990
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
The Quadtree and Related Hierarchical Data Structures
Samet, H. (1984) · ACM Computing Surveys · doi:10.1145/356924.356930 · Cited by 2,205
A Technique for High-Performance Data Compression
Welch (1984) · Computer · doi:10.1109/mc.1984.1659158 · Cited by 2,182
Digital image processing (2nd ed.)
(1992) · CVGIP: Image Understanding · doi:10.1016/1049-9660(92)90019-y · Cited by 1,780
Universal 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
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
Variations on a theme by Huffman
Gallager, R. (1978) · IEEE Transactions on Information Theory · doi:10.1109/tit.1978.1055959 · Cited by 546
Fano, R. M., & Wintringham, W. T. (1961) · Physics Today · doi:10.1063/1.3057290 · Cited by 536
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
Knuth, D. E. (1971) · Acta Informatica · doi:10.1007/bf00264289 · Cited by 443
Variable-Length Binary Encodings
Gilbert, E. N., & Moore, E. F. (1959) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1959.tb01583.x · Cited by 354
Optimal Computer Search Trees and Variable-Length Alphabetical Codes
Hu, T. C., & Tucker, A. C. (1971) · SIAM Journal on Applied Mathematics · doi:10.1137/0121057 · Cited by 287
Fast Algorithms for Manipulating Formal Power Series
Brent, R. P., & Kung, H. T. (1978) · Journal of the ACM · doi:10.1145/322092.322099 · Cited by 285
Source coding algorithms for fast data compression
Pasco, R. C. (1976) · Cited by 191
Minimum-redundancy coding for the discrete noiseless channel
Karp, R. M. (1961) · IEEE Transactions on Information Theory · doi:10.1109/tit.1961.1057615 · Cited by 129
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
Data compression on a database system
Cormack, G. V. (1985) · Communications of the ACM · doi:10.1145/214956.214963 · Cited by 84
Common phrases and minimum-space text storage
Wagner, R. A. (1973) · Communications of the ACM · doi:10.1145/361972.361982 · Cited by 78
Optimal Binary Search Trees with Restricted Maximal Depth
Garey, M. R. (1974) · SIAM Journal on Computing · doi:10.1137/0203008 · Cited by 69
Optimal variable length codes (arbitrary symbol cost and equal code word probability)
Varn, B. (1971) · Information and Control · doi:10.1016/s0019-9958(71)90155-0 · 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
Efficient Generation of Optimal Prefix Code
Perl, Y., Garey, M. R., & Even, S. (1975) · Journal of the ACM · doi:10.1145/321879.321883 · Cited by 47
A practitioner's guide to data base compression tutorial
Severance, D. G. (1983) · Information Systems · doi:10.1016/0306-4379(83)90030-3 · Cited by 42
Cited by
Query evaluation techniques for large databases
Graefe, G. (1993) · ACM Computing Surveys · doi:10.1145/152610.152611 · Cited by 1,262
LEARNING BAYESIAN BELIEF NETWORKS: AN APPROACH BASED ON THE MDL PRINCIPLE
Lam, W., & Bacchus, F. (1994) · Computational Intelligence · doi:10.1111/j.1467-8640.1994.tb00166.x · Cited by 758
ECG data compression techniques-a unified approach
Jalaleddine, S. M. S., Hutchens, C. G., Strattan, R. D., & Coberly, W. A. (1990) · IEEE Transactions on Biomedical Engineering · doi:10.1109/10.52340 · Cited by 681
Energy-aware lossless data compression
Barr, K. C., & Asanović, K. (2006) · ACM Transactions on Computer Systems · doi:10.1145/1151690.1151692 · Cited by 346
A new challenge for compression algorithms: Genetic sequences
Grumbach, S., & Tahi, F. (1994) · Information Processing & Management · doi:10.1016/0306-4573(94)90014-0 · Cited by 272
Metadata
- Authors
- Lelewer, D. A., & Hirschberg, D. S.
- Venue
- ACM Computing Surveys
- Published
- 1987-09
- Volume
- 19
- Issue
- 3
- Pages
- 261-296
- ISSN
- 0360-0300 (ISSN-L)
- 1557-7341
- OpenAlex
- W2295528854
- Cited by
- 377
- References
- 31
- FWCI
- 3.37
- Type
- journal article
- Language
- en
- Open access
- closed
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.