patternMinor
Huffman tree and maximum depth
Viewed 0 times
depthmaximumhuffmanandtree
Problem
Knowing the frequencies of each symbol, is it possible to determine the maximum height of the tree without applying the Huffman algorithm? Is there a formula that gives this tree height?
Solution
Huffman coding (asymptotically) gets within one bit of the entropy of the sequence. This means that if you calculate the entropy of your symbol frequencies, you will be (asymptotically) within one bit of the average length (i.e. height) of your code. You can use this average to bound the longest length (on average), or you can use combinatorial methods to get determinsitic bounds.
Context
StackExchange Computer Science Q#21394, answer score: 4
Revisions (0)
No revisions yet.