Tech Report CS-91-45

Practical Implementations of Arithmetic Coding

Paul G. Howard and Jeffrey Scott Vitter

July 1991


We provide a tutorial on arithmetic coding, showing how it provides nearly optimal data compression and how it can be matched with almost any probabilistic model. We indicate the main disadvantage of arithmetic coding, its slowness, and give the basis of a fast, space-efficient, approximate arithmetic coder with only minimal loss of compression efficiency. Our coder is based on the replacement of arithmetic by table lookups coupled with a new deterministic probability estimation scheme.

(complete text in pdf)