Arithmetic Coding
Arithmetic coding maps an entire message to a single real number in the interval [0,1), represented with finite precision, so the compression ratio can approach the source entropy arbitrarily closely.
Purpose
It achieves higher compression ratios than Huffman coding when symbol probabilities are known, especially when one symbol's probability is close to 1.
Mechanism
Start with the interval [0,1); for each symbol, subdivide the current interval into subintervals proportional to symbol probabilities and select the one corresponding to that symbol. The output is the binary representation of any number inside the final interval. Finite-precision implementations use integer intervals with renormalization to avoid underflow.
Use cases
- Entropy coding stage of JPEG 2000
- Back end of PPM compressors
- High-ratio text compression