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.

$\endgroup$
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.

$\endgroup$
  • $\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 Feb 15 '16 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 Feb 15 '16 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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