Variations on a theme by Huffman
Open accessThe DOI matches its Crossref record; 3 of the 3 references it cites were found in a registry or an index.
Abstract
In honor of the twenty-fifth anniversary of Huffman coding, four new results about Huffman codes are presented. The first result shows that a binary prefix condition code is a Huffman code iff the intermediate and terminal nodes in the code tree can be listed by nonincreasing probability so that each node in the list is adjacent to its sibling. The second result upper bounds the redundancy (expected length minus entropy) of a binary Huffman code byP_{1}+ \log_{2}[2(\log_{2}e)/e]=P_{1}+0.086, whereP_{1}is the probability of the most likely source letter. The third result shows that one can always leave a codeword of length two unused and still have a redundancy of at most one. The fourth result is a simple algorithm for adapting a Huffman code to slowly varying esthnates of the source probabilities. In essence, one maintains a running count of uses of each node in the code tree and lists the nodes in order of these counts. Whenever the occurrence of a message increases a node count above the count of the next node in the list, the nodes, with their attached subtrees, are interchanged.
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
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
Self-citationInformation Theory and Reliable Communication
Bell, D. A. (1969) · Electronics and Power · doi:10.1049/ep.1969.0319 · Cited by 4,012
Cited by
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
Gray, R. M., & Neuhoff, D. L. (1998) · IEEE Transactions on Information Theory · doi:10.1109/18.720541 · Cited by 1,642
A First Course in Information Theory
Yeung, R. W. (2002) · Information Technology: Transmission, Processing and Storage · doi:10.1007/978-1-4419-8608-5 · Cited by 533
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
Moffat, A., Neal, R. M., & Witten, I. H. (1998) · ACM Transactions on Information Systems · doi:10.1145/290159.290162 · Cited by 471
Metadata
- Authors
- Gallager, R.
- Venue
- IEEE Transactions on Information Theory
- Published
- 1978-11
- Volume
- 24
- Issue
- 6
- Pages
- 668-674
- ISSN
- 0018-9448 (ISSN-L)
- 1557-9654
- OpenAlex
- W2038649859
- Cited by
- 546
- References
- 3
- FWCI
- 0.52
- Type
- journal article
- Language
- en
- Open access
- green
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.