HUFFMAN CODING

Huffman coding is a lossless data compression technique. Compressions are only possible when repetition is possible. In this, a variable-length codes are assigned to input different characters, the code’s length is based on the frequencies of the characters that is, how frequently characters are being used. The more frequent the characters, fewer the bits or small codes while the less frequent ones get the longer codes or more bits.

The variable-length codes are prefix codes. Prefix codes are the type of codes that are distinguished by the ‘prefix property’. For eg., a code with {3,78} code words has a prefixed property but code of {5,88,6,81} will not have a prefixed property because “8” is the prefix of both “88” and “81”.

HOW TO BUILD A HUFFMAN TREE?

1. We have to build a min-heap, and create a leaf node for every unique character.

2. Extract 2 nodes that have the minimum frequency from the min-heap.

Add both the leaf with the least values. Make a new internal node with the added frequency.

Minimum frequency in the above table is 5 and 7 so 5+7=12

Min-heap now has total of five nodes, four nodes are the roots of the tree which has one element each, and another heap node is the internal node or the root of the tree which has three elements.

3. We will again check the two minimum nodes from the heap and then add them the same way we did in step 2.

The minimum frequency according to the updated table is the internal node(12) and c(24).

12 + 24 = 36

Now, min heap has only 4 nodes, 3 nodes are the roots of the tree which has one element each, and another heap node is the internal node or the root of the tree which has 5 elements.

4. We have to again extract minimum nodes from the heap and then add the frequencies. The minimum frequency according to the updated table is d(32) and the internal node(36).

32 + 36 = 68

Now, min-heap has 3 nodes, 2 nodes are the roots of the tree which have one element each, and another heap node is the internal node or the root of the tree which has 7 elements.

5. Keep repeating the same step until we get only one node left in min-heap. Extracting two minimum frequency nodes that are, e(48) and f(50).

48 + 50 = 98

Min heap now has 2 nodes, both the nodes are the roots of the tree which has more than 1 element.

6. Extract the 2 frequencies from min heap and add them.

68 + 98 = 166

Min heap now has only one node left so the algorithm stops at this point.

HOW TO GET THE CODES FROM THE HUFFMAN TREE?

In order to get the output of the codes, we traverse the tree from the main or the starting root. When we move to the left child, we will write 0 and when we move to the right child we will write 1 to the array.

PSEUDOCODE: