<p>The intended answer is probably that the length of the longest codeword is approximately <span class="math-container">$$-\log_2 10^{-6} = 20.$$</span> But this is wrong. The information given doesn't come close to specifying the length of the longest codeword. Even the entire probability distribution doesn't specify the length of the longest codeword. </p>

<p>One can see this by constructing a Huffman tree with a probability distribution with probabilities proportional to the Fibonacci numbers <span class="math-container">$$\{1,1,1,2,3,5,8,13, \ldots, F_n\}.$$</span> (The third 1 is deliberate.) When combining these into a Huffman tree, you are faced with lots of choices. One set of choices yields a tree of depth approximately <span class="math-container">$n$</span>; another, approximately <span class="math-container">$n/2$</span>. </p>

<p>For the probabilities <span class="math-container">$$\frac{1}{34}, \frac{1}{34}, \frac{1}{34}, \frac{2}{34}, \frac{3}{34}, \frac{5}{34}, \frac{8}{34}, \frac{13}{34},$$</span>
we have the large-depth Huffman tree where the longest codeword has length 7:</p>

<p><img src="https://i.sstatic.net/dPEsCm.jpg" alt="(((((((1,1),1),2),3),5),8),13)"></p>

<p>and the small-depth Huffman tree where the longest codeword has length 4:</p>

<p><img src="https://i.sstatic.net/7jMLIm.jpg" alt="(((((((1,1),(1,2)),(3,5)),(8,13))"></p>

<p>Both of these trees have <span class="math-container">$43/17$</span> for the expected length of a codeword, which is optimal.</p>

<p>It is possible to show that the length of the longest codeword is no more than a factor of <span class="math-container">$\log_\phi(2)\approx 1.44$</span> larger than <span class="math-container">$-\log_2 p$</span>, where <span class="math-container">$\phi$</span> is the golden ratio; the worst case example is the large-depth one above, using Fibonacci numbers. So for your example the length is at most <span class="math-container">$28$</span>. And because there are 1024 codewords, the length of the longest one has to be at least <span class="math-container">$\log_2 1024 = 10$</span>.  So the correct answer is the length of the longest codeword is between <span class="math-container">$10$</span> and <span class="math-container">$28$</span>. But unless the OP changed the wording of the question, these bounds don't seem to be what the problem was asking for. </p>

CC BY-SA 4.0
2014-06-16T03:48:10.387Z
2019-12-20T14:48:00.900Z
2019-12-20T14:48:00.900Z
Peter Shor 
<blockquote>
  <p>Having an alphabet made of 1024 symbols, we know that the rarest symbol has a probability of occurrence equal to 10^(-6). Now we want to code all the symbols with Huffman Coding. How many bits will the longest encoded symbol have? How many encoded symbols will have same length?</p>
</blockquote>

<p>I try to imagine a Huffman tree for it, but it does not appear to make much sense, as trees for Huffman encoding aren't always balanced (so I can't use tree's height to calculate this I guess). I know that at least two least-probable symbols will have longest codings, but how to relate element's probability with its Huffman code length? Or maybe there is some other way to calculate it?</p>

CC BY-SA 3.0
2014-06-16T02:46:44.843Z
You can't answer this question. Whoever asked it may be confusing properties of [Shannon-Fano-Elias coding](http://en.wikipedia.org/wiki/Shannon–Fano–Elias_coding) with properties of Huffman coding. The length of the codeword for a symbol with probability $p$ in Shannon-Fano-Elias coding is always approximately $-\log_2 p$.
Peter Shor 
CC BY-SA 3.0
2014-06-16T03:07:14.573Z
I think I might have beed quite misunderstood so I tried to rephrase the question a bit. We have: number of all symbols and probability of the least probable (and therefore with longest bit coding) symbol. Is this certainly not enough?
3yakuya
CC BY-SA 3.0
2014-06-16T03:08:38.680Z
It's not enough. Whoever posed the question is very confused.
Peter Shor 
CC BY-SA 3.0
2014-06-16T03:19:13.440Z
It appears I might have a big discussion comming... Thanks for your time. (if you may, make an answer of it so I could accept it.)
3yakuya
<pr.probability><encoding>
Calculate Huffman code length having probability?
3yakuya
# Calculate Huffman code length having probability?

(Asked by: username_0 on 2014-06-16)

> Having an alphabet made of 1024 symbols, we know that the rarest symbol has a probability of occurrence equal to 10^(-6). Now we want to code all the symbols with Huffman Coding. How many bits will the longest encoded symbol have? How many encoded symbols will have same length?

I try to imagine a Huffman tree for it, but it does not appear to make much sense, as trees for Huffman encoding aren't always balanced (so I can't use tree's height to calculate this I guess). I know that at least two least-probable symbols will have longest codings, but how to relate element's probability with its Huffman code length? Or maybe there is some other way to calculate it?

**Tags:** pr.probability, encoding

> **Comments:**
> **username_1**: You can't answer this question. Whoever asked it may be confusing properties of [Shannon-Fano-Elias coding](http://en.wikipedia.org/wiki/Shannon–Fano–Elias_coding) with properties of Huffman coding. The length of the codeword for a symbol with probability $p$ in Shannon-Fano-Elias coding is always approximately $-\log_2 p$.  
> **username_0**: I think I might have beed quite misunderstood so I tried to rephrase the question a bit. We have: number of all symbols and probability of the least probable (and therefore with longest bit coding) symbol. Is this certainly not enough?  
> **username_1**: It's not enough. Whoever posed the question is very confused.  
> **username_0**: It appears I might have a big discussion comming... Thanks for your time. (if you may, make an answer of it so I could accept it.)  

---

## 1 answers

### Answer by username_1 on 2014-06-16. Score: 15 | Accepted answer

The intended answer is probably that the length of the longest codeword is approximately $$-\log\_2 10^{-6} = 20.$$ But this is wrong. The information given doesn't come close to specifying the length of the longest codeword. Even the entire probability distribution doesn't specify the length of the longest codeword.

One can see this by constructing a Huffman tree with a probability distribution with probabilities proportional to the Fibonacci numbers $$\{1,1,1,2,3,5,8,13, \ldots, F\_n\}.$$ (The third 1 is deliberate.) When combining these into a Huffman tree, you are faced with lots of choices. One set of choices yields a tree of depth approximately $n$; another, approximately $n/2$.

For the probabilities $$\frac{1}{34}, \frac{1}{34}, \frac{1}{34}, \frac{2}{34}, \frac{3}{34}, \frac{5}{34}, \frac{8}{34}, \frac{13}{34},$$
we have the large-depth Huffman tree where the longest codeword has length 7:

![(((((((1,1),1),2),3),5),8),13)](https://i.sstatic.net/dPEsCm.jpg)

and the small-depth Huffman tree where the longest codeword has length 4:

![(((((((1,1),(1,2)),(3,5)),(8,13))](https://i.sstatic.net/7jMLIm.jpg)

Both of these trees have $43/17$ for the expected length of a codeword, which is optimal.

It is possible to show that the length of the longest codeword is no more than a factor of $\log\_\phi(2)\approx 1.44$ larger than $-\log\_2 p$, where $\phi$ is the golden ratio; the worst case example is the large-depth one above, using Fibonacci numbers. So for your example the length is at most $28$. And because there are 1024 codewords, the length of the longest one has to be at least $\log\_2 1024 = 10$. So the correct answer is the length of the longest codeword is between $10$ and $28$. But unless the OP changed the wording of the question, these bounds don't seem to be what the problem was asking for.


---

