Tech Report CS-92-18

Practical Implementations of Arithmetic Coding

Paul G. Howard and Jeffrey Scott Vitter

April 1992


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 replacment of arithmetic by table lookups coupled with a new deterministic probability estimation scheme.

{\em Index terms:} data compression, arithmetic coding, adaptive modeling, analysis of algorithms, data structures, low precision arithmetic.

(complete text in pdf)