GATE IT 2006 | Question: 48

Question

The characters $a$ to $h$ have the set of frequencies based on the first $8$ Fibonacci numbers as follows

$a : 1$, $b : 1$, $c : 2$, $d : 3$, $e : 5$, $f : 8$, $g : 13$, $h : 21$

A Huffman code is used to represent the characters. What is the sequence of characters corresponding to the following code?

$110111100111010$

• A. $fdheg$
• B. $ecgdf$
• C. $dchfg$
• D. $fehdg$

Answer 1

Answer is A. Huffman's tree is as follows. The two least frequent characters are taken as the children of a newly made node and the frequency of the newly made node is made equal to the sum of those two child nodes. Then the same procedure is repeated till all nodes are finished. 

$110111100111010 = 110\;11110\;0\;1110\;10 = fdheg$

Comments

Its actually in the algorithm that when we are performing Extract_min() on the huffman tree, it finds the first minimum and keeps as left child than again executing Extract_min(), it goes to right child. 

Source:Introduction to Algorithms by Cormen

HUFFMAN(C)
1 n ← |C|
2 Q ← C
3 for i ← 1 to n − 1
4 do allocate a new node z
5 left[z]← x ← EXTRACT-MIN(Q)
6 right[z]← y ← EXTRACT-MIN(Q)
7 f [z]← f [x] + f [y]
8 INSERT(Q, z)
9 return EXTRACT-MIN(Q) ✄ Return the root of the tree

Though answer comes same even if we flip left or right (unless we do "some" left or "some" right or mix of both in same algorithm).

---

How did you draw the tree directly ?

---

I think that c will be left child and ab will be right, although it doesn’t matter here. But, insertion in min heap says that, we will insert at the leaf and bubble up till node’s value is greater than or EQUAL to the parent. In that case, c is already the root node and we are inserting ab with value 2. So, after successful bubble up, ab will not be the root, but “c” will be the root and first extract-min will yield “c” as the left child and “ab” as the right child. So, the huffman tree overall will be a skewed one and not the one you’ve shown in answer, but theoretically it doesn’t matter anyway, but to be precise, “c” will be the left child and not the right child.

Answer 2

we apply greedy algorithm on the frequencies of the characters to generate the binary tree.Assigning 0 to the left edge and 1 to the right edge.

prefix codes for the characters are...

a – 1111110
b – 1111111
c – 111110
d – 11110
e – 1110
f – 110
g – 10
h – 0

Given String can be decomposed as fdheg.

Answer is A.

Comments

i think it is better answer and good approch.