ARITHMETIC CODING FOR DATA COMPRESSION

ARITHMETIC CODING FOR DATA COMPRESSION

June 1987 Volume 30 Number 6 | IAN H. WITTEN, RADFORD M. NEAL, and JOHN G. CLEARY
The chapter discusses the advantages of arithmetic coding over Huffman coding in data compression. Arithmetic coding represents information more compactly, performs optimally without blocking input data, encourages a clear separation between the model for representing data and the encoding process, accommodates adaptive models easily, and is computationally efficient. However, many practitioners are unaware of its benefits, often believing that Huffman coding is the best possible method. The authors aim to rectify this by presenting an accessible implementation of arithmetic coding and detailing its performance characteristics. They start by reviewing basic concepts of data compression and introducing the model-based approach. They then outline the idea of arithmetic coding using a simple example and present programs for both encoding and decoding. The programs are designed to be flexible, allowing different models to be used easily. The chapter also discusses the construction of fixed and adaptive models, detailing the compression efficiency and execution time of the programs. It includes a proof that decoding is correct in the integer implementation and reviews constraints on word lengths in the program. The authors also provide examples of applications where arithmetic coding is particularly useful, such as adaptive text compression, nonadaptive coding, compressing black/white images, and coding arbitrarily distributed integers. Overall, the chapter emphasizes the superior performance and flexibility of arithmetic coding compared to Huffman coding, making it a valuable technique for data compression.The chapter discusses the advantages of arithmetic coding over Huffman coding in data compression. Arithmetic coding represents information more compactly, performs optimally without blocking input data, encourages a clear separation between the model for representing data and the encoding process, accommodates adaptive models easily, and is computationally efficient. However, many practitioners are unaware of its benefits, often believing that Huffman coding is the best possible method. The authors aim to rectify this by presenting an accessible implementation of arithmetic coding and detailing its performance characteristics. They start by reviewing basic concepts of data compression and introducing the model-based approach. They then outline the idea of arithmetic coding using a simple example and present programs for both encoding and decoding. The programs are designed to be flexible, allowing different models to be used easily. The chapter also discusses the construction of fixed and adaptive models, detailing the compression efficiency and execution time of the programs. It includes a proof that decoding is correct in the integer implementation and reviews constraints on word lengths in the program. The authors also provide examples of applications where arithmetic coding is particularly useful, such as adaptive text compression, nonadaptive coding, compressing black/white images, and coding arbitrarily distributed integers. Overall, the chapter emphasizes the superior performance and flexibility of arithmetic coding compared to Huffman coding, making it a valuable technique for data compression.
Reach us at info@study.space
[slides and audio] Arithmetic coding for data compression