2.5k 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 | 2.5k 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

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

a, b, c, d, should be on right side?
When we use 0s for left and 1s for right in the node.

Like said here :

Even in the answer you wrote, for equal and greater value nodes, you put it on the right side.

https://gateoverflow.in/3591/gate2006-it-48

+1 vote

We get the following Huffman Tree after applying Huffman coding Algorithm The idea is to keep the least probable characters as low as possible by picking them first.

The letters a, b, c, d, e, f have probabilities
1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively.

1
/   \
/     \
1/2    a(1/2)
/  \
/    \
1/4  b(1/4)
/   \
/     \
1/8   c(1/8)
/  \
/    \
1/16  d(1/16)
/  \
e    f
The average length = (1*1/2 + 2*1/4 + 3*1/8 + 4*1/16 + 5*1/32 + 5*1/32)
= 1.9375 

http://www.geeksforgeeks.org/gate-gate-cs-2007-question-77/

answered by (183 points) 1 flag:
✌ Spam (Hira Thakur “this is not solution for above problem”)

1
2