Cheap and Secure Web Hosting Provider : See Now

Does Huffman algorithm generate a minimal weight of a tree?

, , No Comments
Problem Detail: 

Does Huffman algorithm generate a minimal weight of a tree?

I noticed that by trying to make two different trees with the same frequencies of letters, I get different weights of the trees.

We defined the weight of the tree as $\displaystyle\sum_{c\in C}f(c)d(c)$ where $C$ is all the letters, $f()$ is the frequency of the letter, $d()$ is the depth in the tree of that letter.

Asked By : kuhaku

Answered By : Yuval Filmus

If you normalize the frequencies so that they add to 1, then the weight of the tree is just the average codeword length, which is exactly what Huffman's algorithm tries to minimize. Check this section of the Wikipedia article you link to.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/53124

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback