Vitter's algorithm

(algorithm)

Definition: An adaptive Huffman coding scheme. Typically this produces codings the same length as or shorter than static Huffman coding. In the worst case, this uses one more bit per codeword.

Generalization (I am a kind of ...)
adaptive Huffman coding.

Aggregate child (... is a part of or used in me.)
full binary tree.

See also algorithm FGK.

Author: PEB

Implementation

Algorithm 673 in plain text (Pascal).

More information

survey of data compression

Jeffrey Scott Vitter, Design and analysis of dynamic Huffman codes, Journal of the ACM 34(4):825-845, October 1987.
Jeffrey Scott Vitter, ALGORITHM 673: dynamic Huffman coding, ACM Transactions on Mathematical Software, 15(2):158-167, June 1989.

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.

Entry modified 27 August 2007.
HTML page formatted Mon Aug 27 10:17:32 2007.

Cite this as:
Paul E. Black, "Vitter's algorithm", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 27 August 2007. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/vittersAlgorithm.html