0
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I saw that on the wiki page, I'm not sure I understood it though. So If the weight of the tree corresponds to an average word length, then a small difference in the weight of the tree between two Huffman codes over the same input is expected? $\endgroup$
    – shinzou
    Commented Feb 15, 2016 at 15:10
  • $\begingroup$ No, any two Huffman codes should have exactly the same weight. Every Huffman code (that is, every code produced by Huffman's algorithm) provably has minimal weight. $\endgroup$
    – Yuval Filmus
    Commented Feb 15, 2016 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.