0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ You can't answer this question. Whoever asked it may be confusing properties of 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$. $\endgroup$ – Peter Shor Jun 16 '14 at 2:46
  • $\begingroup$ 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? $\endgroup$ – 3yakuya Jun 16 '14 at 3:07
  • 2
    $\begingroup$ It's not enough. Whoever posed the question is very confused. $\endgroup$ – Peter Shor Jun 16 '14 at 3:08
  • $\begingroup$ 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.) $\endgroup$ – 3yakuya Jun 16 '14 at 3:19
12
$\begingroup$

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)

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

(((((((1,1),(1,2)),(3,5)),(8,13))

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.

$\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.