HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Huffman tree and maximum depth

Submitted by: @import:stackexchange-cs··
0
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.