- Huffman coding is the application of greedy algorithm.
- Huffman coding is also known as Huffman encoding
- It is a famous greedy algorithm which is used for lossless compression of data
- It uses a variable-length encoding where variable-length codes are assigned to all characters depending on how frequently they occur in the given text
There are two major steps in Huffman coding-
- Building a Huffman tree from the input characters
- Assigning codes to the characters by traversing the Huffman tree
Steps to construct Huffman coding:
- Create a leaf node for all the given characters containing the occurring frequency of characters.
- Arrange all the nodes in the increasing order of frequency value contained in the nodes.
Considering the first two nodes having a minimum frequency, create a new internal node having a frequency equal to the sum of the two nodes frequencies and make the first node as a left child and the other node as a right child of the newly created node.
Keep repeating Step-02 and Step-03 until all the nodes form a single tree. After following all the above steps, our desired Huffman tree will be constructed.
2.Total number of bits in Huffman encoded message
= Total number of characters in the message x Average code length per character
= ∑ ( frequencyi x Code lengthi )
ExtractMin( ) is called 2 x (n-1) times if there are n nodes.As extractMin( ) calls minHeapify( ), it takes O(logn) time.
Thus, Overall complexity becomes O(nlogn).
Time Complexity of Huffman Coding = O (nlogn)
where n is the number of unique characters in the text