Huffman coding: Difference between revisions

Revision as of 19:31, 17 March 2004

Revision as of 19:32, 17 March 2004

Line 35:

The '''n-ary Huffman''' algorithm uses the {0, 1, ..., n-1} alphabet to encode message and builds an n-ary tree.

Extreme cases of Huffman codes are connected with [[Fibonacci number]]s. For example, see [http://mathforum.org/discuss/sci.math/t/207334.]

Huffman coding is optimal when the probability of each input symbol is a power of two. Prefix-free codes tend to have slight inefficiency on small alphabets, where probabilities often fall between powers of two. Expanding the alphabet size by coalescing multiple symbols into "words" before Huffman coding can help a bit.

[[Arithmetic coding]] produces slight gains over Huffman coding, but in practice these gains have not been large enough to offset arithmetic coding's higher computational complexity and patent royalties ([[As of 2001|asAs of November 2001]], IBM owns patents on the core concepts of arithmetic coding in several jurisdictions.)

== Applications ==