0
$\begingroup$

I have to prove that the average codeword length is the same in any Huffman encoding schemes for a source S.

The average codeword length is equal to the sum of the codeword lengths times the probability of their source symbols.

If while constructing a Huffman tree for a source S and no two nodes in the top row ever have the same probability, then there would only be one Huffman tree and thus one encoding scheme and average codeword length.

However, if two or more nodes in the top row have the same probability, then it would be possible to switch the nodes of the same probability while constructing the Huffman tree, such that the encoding scheme would have the same codewords (and thus the same average codeword length) but corresponding to different source symbols.

But this only works if the different Huffman trees are essentially the same. How can I expand this to encoding schemes with different codeword lengths (but with the same average codeword length)?

Edit: I know that if the probability of j is larger than that of k, then the length of j will be less than the length of k.

$\endgroup$

1 Answer 1

2
$\begingroup$

Let me suggest a sledgehammer:

  1. Prove that the greedy algorithm is optimal, that is, the average codeword length is minimum. (e.g. http://www.ida.liu.se/opendsa/OpenDSA/Books/OpenDSA/html/HuffProof.html)
  2. By the definition of Huffman coding schemes, all schemes (isomorphic or not) have minimum average codeword length.
$\endgroup$
4
  • $\begingroup$ So you suggest saying that since all Huffman encoding schemes have minimum average codeword length for a source S, then it follows that they will have the same average code word length? Unfortunately I think this is a little too lazy for my professor :) $\endgroup$ Commented Feb 22, 2018 at 3:49
  • $\begingroup$ If the question is actually about Huffman conding schemes, then I'd indeed say it follows from the definition. If the question is whether the greedy tree-building algorithm produces identical average codeword lengths, then just assuming optimality is not an option, of course. However, you can still prove that the algorithm is correct and returns optimal Huffman schemes. That's quite a detour, of course, but not so lazy. The advantage is that examples of optimality proofs are easy to find. Perhaps this is more of a last resort, but why wouldn't it be valid? $\endgroup$
    – tobwin
    Commented Feb 22, 2018 at 3:56
  • $\begingroup$ Note: I have only skimmed the proof (not my field), but perhaps it'll give you inspiration for your related but weaker theorem. $\endgroup$
    – tobwin
    Commented Feb 22, 2018 at 3:59
  • $\begingroup$ We studied that Huffman codes are optimal much later than mentioning that they have the same average codeword length. But since I am not finding anything that directly proves that they have the same average codeword length without mentioning optimality, then I agree with your proof. Thank you for your help! $\endgroup$ Commented Feb 22, 2018 at 4:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .