retagged by
9,352 views
13 votes
13 votes

Consider the string $\textrm{abbccddeee}$. Each letter in the string must be assigned a binary code satisfying the following properties:

  1. For any two letters, the code assigned to one letter must not be a prefix of the code assigned to the other letter.
  2. For any two letters of the same frequency, the letter which occurs earlier in the dictionary order is assigned a code whose length is at most the length of the code assigned to the other letter.

Among the set of all binary code assignments which satisfy the above two properties, what is the minimum length of the encoded string?

  1. $21$
  2. $23$
  3. $25$
  4. $30$
retagged by

2 Answers

Best answer
20 votes
20 votes

Given string: $abbccddeee$

$a$ has the least frequency and should be the leaf of the tree. $b,c$ and $d$ have the same frequency but as per Condition 2 in the questions $d$ should be taken first, followed by $c$ and then $b.$ $e$ has the highest frequency and so must be taken last.

$\begin{array}{|c|c|} \hline \textbf{Alphabet} & \textbf{Frequency} \\\hline  a  & 1  \\\hline  b & 2 \\\hline c & 2  \\\hline  d & 2 \\\hline e & 3 \\\hline \end{array}$

The final Huffman tree looks like:

$\begin{array}{|c|c|} \hline \textbf{Prefix Code} & \textbf{Code Length} \\\hline a = 000 & 3 \\\hline b =10 & 2 \\\hline c = 11 & 2 \\\hline d = 001 & 3 \\\hline e = 01 & 2 \\\hline \end{array}$

$\therefore$ Minimum length of encoded string: $(1*3)+(2*2)+(2*2)+(3*2)+(2*3)=23$

Option $B$ is correct.

References:

  1. GATE 2007
  2. GATE 2017
  3. Huffman_coding wiki
edited by
2 votes
2 votes

Answer is $23$.

It is a Huffman tree problem with the only constraint that the depth of node $d$ $\ge$ node $c$ $\ge$ node $b$.

So while creating the tree, node $a$ can only be joined with node $d$. And node $b$ and $c$ have to be joined together. 

Answer:

Related questions