(algorithm)
Definition: A minimal variable-length message coding based on the frequency of each character. The message is represented by a fraction which is the repeated offset-plus-product reduction of the range (offset) and probability (product) of each character.
See also Huffman coding, Shannon-Fano coding.
Note: Shannon-Fano is a minimal prefix code. Huffman is optimal for character coding (one character-one code word) and simple to program. Arithmetic coding is even more compact, since it can allocate fractional bits, but is more complicated and patents cover some uses.
Range encoding is essentially the same, but uses integers and integer ranges instead of fractions. The implementation in Martin 1979 is thought to not be covered by patents.
Author: PEB
An introduction to data compression methods. Wikipedia entries for Arithmetic coding and Range encoding.
Ian H. Witten, Radford M. Neal, and John G. Cleary, Arithmetic Coding for Data Compression, CACM 30(6):520-540, June 1987.
G. N. N. Martin, Range encoding: an algorithm for removing redundancy from a digitised message, Video & Data Recording Conference, Southampton, UK, July 1979.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 12 December 2011.
HTML page formatted Mon Feb 2 13:10:39 2015.
Cite this as:
Paul E. Black, "arithmetic coding", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 12 December 2011. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/arithmeticCoding.html