(algorithm)
Definition: A variable-length coding based on the frequency of occurrence of each character. Divide the characters into two sets with the frequency of each set as close to half as possible, and assign the sets either 0 or 1 coding. Repeatedly divide the sets until each character has a unique coding.
See also arithmetic coding, Huffman coding, Zipf's law.
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 better still, since it can allocate fractional bits, but is more complicated and has patents.
Author: PEB
Debra A. Lelewer's and Daniel S. Hirschberg's survey of data compression.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 4 January 2005.
HTML page formatted Mon Feb 2 13:10:40 2015.
Cite this as:
Paul E. Black, "Shannon-Fano coding", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 4 January 2005. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/shannonFano.html