Explain the procedure for construction of Huffman algorithm with example.

Answers

This answer is not selected as best answer. This answer may not be sufficient for exam.

Your limit has been exceed. We have implemented this system because, We got difficulty on managing our servers. Please donate some amount to remove this limit.

Quota: 0 / 30

Donate

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 zand assign the second minimum frequency to the right child of z. Set the value of the zas the sum of the above two minimum frequencies.
  5. Remove these two minimum frequencies from Qand add the sum into the list of frequencies.
  6. Insert node zinto 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:

User Loaded Image | CSIT Guide

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

User Loaded Image | CSIT Guide

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:

User Loaded Image | CSIT Guide

Now from variable length code we get following code sequence.

User Loaded Image | CSIT Guide

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

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

If you found any type of error on the answer then please mention on the comment or submit your new answer.
Leave your Answer:

Click here to submit your answer.

Discussion
0 Comments
  Loading . . .