Analysis of Arithmetic Coding for Data Compression

Abstract

Arithmetic coding, in conjunction with a suitable probabilistic model, can pro- vide nearly optimal data compression. In this article we analyze the e ect that the model and the particular implementation of arithmetic coding have on the code length obtained. Periodic scaling is often used in arithmetic coding im- plementations to reduce time and storage requirements; it also introduces a recency e ect which can further a ect compression. Our main contribution is introducing the concept of weighted entropy and using it to characterize in an elegant way the e ect that periodic scaling has on the code length. We explain why and by how much scaling increases the code length for les with a ho- mogeneous distribution of symbols, and we characterize the reduction in code length due to scaling for les exhibiting locality of reference. We also give a rigorous proof that the coding e ects of rounding scaled weights, using integer arithmetic, and encoding end-of- le are negligible.