# Relation between Code Length and Symbol Weight in a Huffman Code

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!

• 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. – Suresh Venkat Jul 17 '11 at 23:02
• @Suresh: Yes, that's what I meant, sorry. How does one normalize a frequency? And why only "almost exactly"? – Cameron Jul 17 '11 at 23:09
• @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]$ – Jeremy Jul 18 '11 at 0:08
• 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. – Peter Shor Feb 8 '16 at 2:22