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!

Improve this question
$\endgroup$
4
  • $\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
    Commented Jul 17, 2011 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
    Commented Jul 17, 2011 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$
    – J..y B..y
    Commented Jul 18, 2011 at 0:08
  • 1
    $\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
    Commented Feb 8, 2016 at 2:22

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
0

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.