Question

2. (10 points) Suppose we want to compress a text consisting of 6 characters, a, b, c, d, e, f using the Huffman Algorithm. Give an example for which the algorithm produces at least one codeword of length 5. In other words, you are being asked to give a set of the character frequencies that results in the deepest tree.

Answer 1

ANSWER :

Worst case will happen when f(a) > 2*f(b) ; f(b) > 2*f(c) ; f(c) > 2*f(d) ; f(d) > 2*f(e) and f(e) > 2*f(f).

Where f(x) is frequency of character x.

Lets consider the scenario when

f(a) = 0.555, f(b) = 0.25, f(c) = 0.12, f(d) = 0.05, f(e) = 0.02 and f(f) = 0.005

Below image shows the steps of construction of Huffman tree:-

slepo :]@ = 0.555 10) = 0.28 JCC) = 0.12 f(d)=005 dle )-0.02 f1t) = 0 '005 Step : f(a)=0.555 (6)=0.25 d(c)=0.12 JCdJo.os y (e.) = 0.028 e step © :f@ -0.655 406)=0,25 366)=0.12 g (def) = 0.075 stero: f@=0.555 | (b)=0.25 J (cdef) = Odgs

step®: (a)=0.555 C f(bcded)-0.4455 (bcded t coded slep@. (abcded) = 1 Sabcdef) obcded cdef,

From the Huffman tree created, we can see that endcoding e() of each character are as follows:-

e(a) = 0

e(b) = 10

e(c) = 110

e(d) = 1110

e(e) = 11110

e(f) = 11111

So we can see that maximum length of encoding is 5 in this case.

PLease comment for any clarification.