GATE CSE 1989 | Question: 13a

Question

A language uses an alphabet of six letters, $\left\{a, b, c, d, e, f\right\}$. The relative frequency of use of each letter of the alphabet in the language is as given below: $$\begin{array}{|ll|ll|}\hline & \text{LETTER}  & \text{RELATIVE FREQUENCY OF USE}\\\hline &\ a &\ 0.19  \\ &\ b &\ 0.05  \\ &\ c &\ 0.17  \\ &\ d &\ 0.08  \\&\ e &\ 0.40 \\ &\ f &\ 0.11  \\\hline \end{array}$$Design a prefix binary code for the language which would minimize the average length of the encoded words of the language.

Comments

Correct answer is 2.33 ✅

---

one master formula covers every situation.

1. Probabilities: Since the root node is always $1$, the formula becomes:

   $\text{Average Length} = \frac{\text{Sum of all internal nodes}}{1}$

   (Which is just the sum itself)

2. Frequencies: Since the root node is the total count, the formula becomes:

   $\text{Average Length} = \frac{\text{Sum of all internal nodes}}{\text{Total Count}}$

3. Percentages: Since the root node is always $100$, the formula becomes:

   $\text{Average Length} = \frac{\text{Sum of all internal nodes}}{100}$

By using $\frac{\text{Sum of all internal nodes}}{\text{Root Node value}}$, you never have to worry about which format the question uses it will always give you the correct average length!

Answer 1

$a-0.19,b-0.05, c-0.17,d-0.08,e-0.40,f-0.11$

Since it is relative frequency we can multiply each with $100$ and result remains the same.

$a-19,b-5, c-17,d-8,e-40,f-11$

For Assigning prefix binary code lets first create the Huffman tree

$(1) \ a-19,{\color{Red} {b-5} },c-17,{\color{Red} {d-8} },e-40,f-11$

$(2) \ a-19,{\color{Red} {(b,d)-13} },c-17,e-40,{\color{Red} {f-11} }$

$(3) \ {\color{Red} {a-19} },(b,d,f)-24,{\color{Red} {c-17} },e-40$

$(4) \ {\color{Red} {(a,c)-36,(b,d,f)-24}},e-40$

$(5) \ {\color{Red} {(a,b,c,d,f)-60,e-40}}$

Now put $0$ on each of the left edges and $1$ on each of the right edges as shown below

$\text{Prefix code}$ = Traverse from the root node to the leaf node and write the symbol $(1 \  or \ 0)$ present on each edge.

• For $a$ the prefix code is $111$  i.e. $3$ bits
• For $b$ the prefix code is $1010$ i.e. $4$ bits
• For $c$ the prefix code is $110$ i.e. $3$ bits
• For $d$ the prefix code is $1011$ i.e. $4$ bits
• For $e$ the prefix code is $0$ i.e. $1$ bits
• For $f$ the prefix code is $100$ i.e. $3$ bits

And the average length of encoded words $=\dfrac{(19\times 3)+(5\times 4)+(17\times 3)+(8\times 4)+(40\times 1)+(11\times 3)}{100}$

$\quad =\dfrac{57+20+51+32+40+33}{100}$

$\quad =\dfrac{233}{100}$

$\quad =2.33$

Comments

why not merging 36 and 40???

---

@Sarah Sayed  because we have to merge the minimum one first,   so 24 and 36 will merge and after that 40 will.

---

we can also draw tree like this also which is also giving ans 2.33

we can also do this ??? 

Answer 2

Huffman coding is to find prefix of letters,is to compress the message size over ASCII code.

To find length of encoded message find Huffman tree and sum of all internal nodes gives the message length.

First find minimum tress in the forest and remove it add to huffman tree.Add two minimum trees and add in the forest.

Repeat this procedure until forest become single tree.

Length of message=1+0.60+0.24+0.36+0.13

                            =2.33

Answer 3

Here is the simplest and easiest way to solve this kind of Problem