Data Structures and Algorithms - Old Questions

3. Explain the procedure for construction of Huffman algorithm with example.

Huffman algorithm is a technique of compressing data to reduce its size without losing any of the details. It is generally useful to compress the data in which there are frequently occurring characters.

Using the Huffman tree, we can compress the string to a smaller size.

Procedure for construction of Huffman tree

1. Calculate the frequency of each character in the string.

2. Sort the characters in increasing order of the frequency. These are stored in a priority queue Q.

3. Make each unique character as a leaf node.

4. Create an empty node z. Assign the minimum frequency to the left child of z and assign the second minimum frequency to the right child of z. Set the value of the z as the sum of the above two minimum frequencies.

5. Remove these two minimum frequencies from Q and add the sum into the list of frequencies.

6. Insert node z into the tree.

7. Repeat steps 3 to 5 for all the characters.

8. For each non-leaf node, assign 0 to the left edge and 1 to the right edge.

Example:

Let us take any four characters and their frequencies:

Now sort these characters according to their frequencies in non-decreasing order.

Here before using Huffman algorithm the total number of bits required is

= 2*(6+3+2+1) = 24 bits.

The tree constructed for the above example is shown below:

Now from variable length code we get following code sequence.

Thus after using Huffman algorithm the total number of bits required is

=1*3+2*3+3*2+6*1=21 bits