<p>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.</p>

CC BY-SA 3.0
2011-07-18T00:28:48.570Z
2011-07-18T00:28:48.570Z
Peter Shor 
<p>I'm not sure if I should ask this here or over at StackOverflow (sorry if this is not the right place).</p>

<p>I'm constructing a <a href="http://en.wikipedia.org/wiki/Huffman_coding" rel="nofollow">Huffman code</a> 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)?</p>

<p>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.</p>

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

<p>Thanks!</p>

CC BY-SA 3.0
2011-07-17T23:02:32.117Z
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
CC BY-SA 3.0
2011-07-17T23:09:52.953Z
@Suresh: Yes, that's what I meant, sorry. How does one normalize a frequency? And why only "almost exactly"?
Cameron
CC BY-SA 3.0
2011-07-18T00:08:49.250Z
@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]$
J.y B.y
CC BY-SA 3.0
2016-02-08T02:22:36.660Z
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 
<it.information-theory>
Relation between Code Length and Symbol Weight in a Huffman Code
Cameron
# Relation between Code Length and Symbol Weight in a Huffman Code

(Asked by: username_0 on 2011-07-17)

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](http://en.wikipedia.org/wiki/Huffman_coding) 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!

**Tags:** it.information-theory
> **Comments:**
> **username_1**: 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.  
> **username_0**: @Suresh: Yes, that's what I meant, sorry. How does one normalize a frequency? And why only "almost exactly"?  
> **username_2**: @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]$  
> **username_3**: 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.  

---

## 1 answers

### Answer by username_3 on 2011-07-18. Score: 6 | Accepted answer

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.


---

