Arithmetic Coding Algorithm

Arithmetic coding is a lossless data compression algorithm that encodes an entire message as a single number within the interval from zero to one, rather than assigning a separate fixed code to each symbol the way Huffman coding does. It works by dividing that interval into sub-intervals sized in proportion to each symbol's probability, so a frequent symbol claims a large sub-interval that can be pinpointed with relatively few bits, and narrowing the working interval to the chosen sub-interval after each symbol is processed, so by the end of the message the final narrow interval that remains identifies the entire sequence. Because it encodes the message as a whole rather than symbol by symbol, arithmetic coding can approach the theoretical entropy limit of a message's information content more closely than Huffman coding can, particularly over long messages. The basic technique was developed independently by Jorma Rissanen at IBM Research and Richard Pasco at Stanford University, both publishing their work in May 1976; IBM patented Rissanen's version, and while some later arithmetic coding patents have expired, that patent history slowed the technique's adoption relative to Huffman coding for a period.