Analysis of arithmetic coding for data compression
Paul G. Howard, Jeffrey Scott Vitter · 2002
The authors analyze the amount of compression possible when arithmetic coding is used for text compression in conjunction with various input models. Arithmetic coding, a technique for statistical lossless encoding, can be thought of as a generalization of Huffman coding in which probabilities are not constrained to be integral powers of 2 and code lengths need not be integers. Adaptive codes are proven to be as good as decrementing semi-adaptive codes. The tradeoff between scaling overheads and savings from exploitation of locality of reference is characterised exactly by means of weighted entropy.>