Arithmetic coding for data compression
Communications of the ACMPublished 1 June 1987Open access
Ian H. Witten, Radford M. Neal, John G. Cleary
Citations2,861
SJR quartileQ1
SJR score1.15
SNIP3.34
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The state of the art in data compression is arithmetic coding, not the better-known Huffman method, which gives greater compression, is faster for adaptive models, and clearly separates the model from the channel encoding.
Abstract
The state of the art in data compression is arithmetic coding, not the better-known Huffman method. Arithmetic coding gives greater compression, is faster for adaptive models, and clearly separates the model from the channel encoding.
Keywords
Computer Science
Bell System Technical JournalA Mathematical Theory of Communication
80,675 Citations1948Claude E. Shannon
Proceedings of the IREA Method for the Construction of Minimum-Redundancy Codes
6,200 Citations1952David A. Huffman
IEEE Transactions on Information TheoryCompression of individual sequences via variable-rate coding
3,452 Citations1978J. Ziv, A. Lempel
The proposed concept of compressibility is shown to play a role analogous to that of entropy in classical information theory where one deals with probabilistic ensembles of sequences rather than with individual sequences.
IEEE Transactions on CommunicationsData Compression Using Adaptive Coding and Partial String Matching
1,250 Citations1984John J. Cleary, Ian H. Witten
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.
IBM Journal of Research and DevelopmentArithmetic Coding
739 Citations1979J. Rissanen, Glen G. Langdon
IEEE Transactions on Information TheoryVariations on a theme by Huffman
550 Citations1978Robert G. Gallager
Four new results about Huffman codes are presented and a simple algorithm for adapting a Huffman code to slowly varying esthnates of the source probabilities is presented.
Communications of the ACMA locally adaptive data compression scheme
530 Citations1986Jon Bentley, Daniel D. Sleator +2 more
It is proved that this data compression scheme never performs much worse than Huffman coding and can perform substantially better; experiments on real files show that its performance is usually quite close to that of Huffman coding.
IBM Journal of Research and DevelopmentAn Introduction to Arithmetic Coding
515 Citations1984Glen G. Langdon
IBM Journal of Research and DevelopmentGeneralized Kraft Inequality and Arithmetic Coding
504 Citations1976J. Rissanen
This coding technique requires no blocking, and the per-symbol length of the encoded string approaches the associated entropy within ∈, which is comparable to that of conventional coding methods.
IEEE Transactions on Information TheoryUniversal modeling and coding
463 Citations1981J. Rissanen, Glen G. Langdon
A general class of so-called first-in first-out (FIFO) arithmetic codes is described which require no alphabet extension devices and which therefore can be used in conjunction with the best models.
IBM Journal of Research and DevelopmentOptimizing Preventive Service of Software Products
374 Citations1984E. N. Adams
It is found that most of the benefit to be realized by preventive service comes from removing a relatively small number of high-rate defects that are found early in the service life of the code.
IRE Transactions on Communications SystemsCompression of Black-White Images with Arithmetic Coding
363 Citations1981Glen G. Langdon, J. Rissanen
A new approach for black and white image compression is described, with which the eight CCITT test documents can be compressed in a lossless manner 20-30 percent better than with the best existing compression algorithms.
Proceedings of the IEEEInternational digital facsimile coding standards
195 Citations1980R. A. Hunter, Alfred Henry Robinson
The coding schemes in detail are described in detail and the factors which led to their choice are discussed, and the performance of the codes is assessed, particularly in relation to their compression efficiency and vulnerability to transmission errors.
ACM Computing SurveysSelf-organizing linear search
133 Citations1985J. H. Hester, D. S. Hirschberg
Algorithms that modify the order of linear search lists are surveyed and algorithms in the literature with absolute analyses when available are presented.
IEEE Transactions on Information TheoryArithmetic stream coding using fixed precision registers
93 Citations1979Frank Rubin
Algorithms are presented for encoding and decoding strings of characters as real binary fractions, using registers of fixed precision, and have storage requirements and computation time O(n \log_{2}N) for string length n and alphabet size N.
Information Processing LettersAlgorithms for adaptive Huffman codes
62 Citations1984Gordon V. Cormack, R. Nigel Horspool
Un algorithme d'Huffman permet de generer des codes a redondance minimum pour un ensemble fini de message a frequences de transmissions connues, mais le systeme binaire reste certainement le mieux adapte aux applications informatiques.
IEEE Transactions on Information TheoryA comparison of enumerative and adaptive codes
60 Citations1984John J. Cleary, Ian H. Witten
Two adaptive codes are described for this problem whose coding efficiency is upper-bounded by the extended enumerative codes and on some practical examples the adaptive codes perform significantly better than the nonadaptive ones.