Jump to content

Adaptive Huffman coding

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by 203.112.195.157 (talk) at 07:11, 9 September 2009 (→Vitter algorithm). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Adaptive Huffman coding (also called Dynamic Huffman coding) is an adaptive coding technique based on Huffman coding. It permits building the code as the symbols are being transmitted, having no initial knowledge of source distribution, that allows one-pass encoding and adaptation to changing conditions in data.

The benefit of one-pass procedure is that the source can be encoded in real time, though it becomes more sensitive to transmission errors, since just a single loss ruins the whole code.

Algorithms

There are a number of implementations of this method, the most notable are FGK (Faller-Gallager-Knuth) and Vitter algorithm.

References

  • Vitter's original paper: J. S. Vitter, "Design and Analysis of Dynamic Huffman Codes," Journal of the ACM, 34(4), October 1987, pp 825-845.
  • J. S. Vitter, "ALGORITHM 673 Dynamic Huffman Coding," ACM Transactions on Mathematical Software, 15(2), June 1989, pp 158-167. Also appears in Collected Algorithms of ACM.
  • Public Domain This article incorporates public domain material from Paul E. Black. "adaptive Huffman coding". Dictionary of Algorithms and Data Structures. NIST.
  • University of California Dan Hirschberg site
  • Cardiff University Dr. David Marshall site
  • C implementation of Vitter algorithm
Retrieved from "https://en.wikipedia.org/enwiki/w/index.php?title=Adaptive_Huffman_coding&oldid=312738367"