4
$\begingroup$

I'm not sure if I should ask this here or over at StackOverflow (sorry if this is not the right place).

I'm constructing a Huffman code for a series of symbols with associated weights. I have a list of the code-lengths corresponding to each symbol, sorted by symbol weight (in non-decreasing order). Does it follow that this list is also sorted by code-length (in non-increasing order)?

I suspect that the answer is yes (since lower-weighted symbols will generally have shorter code lengths), but I'm not sure if this is guaranteed.

I guess what I really want to know is, "if a Huffman tree has two leaves a and b, where a had a higher weight than b, is b's code length always at least that of a's?"

Thanks!

$\endgroup$
  • $\begingroup$ does "weight" in this case mean frequency ? the code length according to a huffman code is almost exactly $\log(1/p_i)$, where $p_i$ is the normalized frequency. $\endgroup$ – Suresh Venkat Jul 17 '11 at 23:02
  • $\begingroup$ @Suresh: Yes, that's what I meant, sorry. How does one normalize a frequency? And why only "almost exactly"? $\endgroup$ – Cameron Jul 17 '11 at 23:09
  • $\begingroup$ @Cameron: you normalize the frequency $f_i$ by dividing it by the sum $n$ of the frequencies, so that to get $p_i=g_i/n\in [0,1]$ $\endgroup$ – Jeremy Jul 18 '11 at 0:08
  • $\begingroup$ One comment: the code length in a Huffman code is not necessarily "almost exactly $\log 1/p_i$", although it is generally within a constant factor. $\endgroup$ – Peter Shor Feb 8 '16 at 2:22
6
$\begingroup$

Yes. A Huffman code is optimal. If a less frequent symbol had a shorter code length than a more frequent symbol, then you could get a code with better performance by exchanging them.

$\endgroup$

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.