A source $S$ has source words $w_1, w_2, \ldots, w_n$, with probabilities $p_1 \geq p_2 \geq \ldots \geq p_n > 0$. Let $C$ be a binary Huffman code for $S$, and let $l$ be the length of the longest code word in $C$. Let $L(C)$ be the expected length of $C$.

Suppose you replace $w_n$ by two source words $w_a$ and $w_b$ with positive probabilities $p_a$ and $p_b$ respectively, where $p_a + p_b = p_n$. Call the new Huffman Code $C’$. What is $L(C’) – L(C)$?

So what I understand is that $L(C) = l_1p_1 + l_2p_2 + \ldots + l_np_n$ and $L(C’) = l_1p_1 + l_2p_2 + \ldots + (l_ap_a + l_bp_b)$ So if I were to find the difference $L(C’) – L(C)$ I am thinking that I would simply be left with $l_ap_a + l_bp_b - l_np_n$, but I have a feeling there is more to this than I presume.

Any ideas or suggestions would be greatly helpful!

  • $\begingroup$ Are you asking this question in the context of a proof of optimality of Huffman coding? Or do you have interest for some other reason? $\endgroup$ – Martin Leslie Oct 26 '13 at 2:44
  • 1
    $\begingroup$ It really isn’t clear just what you’re asking. For instance, you mention $\ell$, but nothing in the question seems to depend on it. Are you considering the case in which the leaf for $w_n$ becomes an internal vertex with daughter leaves for $w_a$ and $w_b$? In that case $\ell_a=\ell_b=\ell_n+1$, and $L(C')-L(C)=p_n$. $\endgroup$ – Brian M. Scott Oct 26 '13 at 5:12
  • $\begingroup$ My professor posed this question as a possible midterm task and I'm simply trying to make sure that I am understanding the information correctly. A proof within the context of optimality may shed some light. However, I am unsure whether wa and wb are leaves for wn, I believe they are since the sum of their probabilities is the probability of wn. But the question that I'm technically asking is "what is L(C’) – L(C) considering the changes made on L(C)?" $\endgroup$ – Mike Oct 26 '13 at 13:34
  • $\begingroup$ @Mike: It’s what you wrote, $\ell_ap_a+\ell_bp_b-\ell_np_n$, but this doesn’t really say much without more context. $\endgroup$ – Brian M. Scott Oct 26 '13 at 23:45

Your Answer

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

Browse other questions tagged or ask your own question.