3.1k views

Suppose the letters $a, \,b, \,c, \,d, \,e, \,f$ have probabilities $\frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \frac{1}{16}, \frac{1}{32}, \frac{1}{32}$, respectively.

Which of the following is the Huffman code for the letter $a, \,b, \,c, \,d, \,e, \,f$?

1. $0$, $10$, $110$, $1110$, $11110$, $11111$

2. $11$, $10$, $011$, $010$, $001$, $000$

3. $11$, $10$, $01$, $001$, $0001$, $0000$

4. $110$, $100$, $010$, $000$, $001$, $111$

edited | 3.1k views

Based on the probabilities, we can say the probable frequency of the letters will be

$16$, $8$, $4$, $2$, $1$, $1$

Now, the Huffman tree can be constructed as follows:

So, A is the answer for $76$.

https://en.wikipedia.org/wiki/Huffman_coding

by Veteran (434k points)
edited
+4

Is there any constraint on where to put the two same weighted values according to them being single and composite? Is the following Huffman tree correct too?

0

@habedo007  it is correct.You will also get the same values,it just your tree can have left and right encoding of 1,0 opposite but it is also correct

0
@rahul sharma 5

If we give left -1, right - 0 on this particular tree, then 'f' will have 11110 which is diff from the option A

But then we could flip e & f to get the code for 'f' as 11111.
0

Where to put two same weight?. Sir/ma'am i  did not get any information about that but i have seen many example they follow FCFS.