HCA

Huffman Coding Algoritm

The technique of Huffman coding is the final stage in many compression methods, including JPEG, MP3, and zip. The purpose of Huffman coding is to take a set of "symbols" (which could be characters in text, run lengths in RLE, pointer values in a Ziv-Lempel system, or parameters in lossy systems), and provide the optimal bit patterns with which they can be represented. It's normally presented as a way of compressing textual documents, and while it can do that reasonably well, it works much better in combination with Ziv-Lempel coding.

shannon-fano-coding-huffman-coding-code-

1- Create a priority queue Q consisting of each unique character.

2- Sort then in ascending order of their frequencies.

3- For all the unique characters:

3a- Create a newNode,

3b- Extract minimum value from Q and assign it to leftChild of newNode.

4- Extract minimum value from Q and assign it to rightChild of newNode.

5- Calculate the sum of these two minimum values and assign it to the value of newNode.

6- Insert this newNode into the tree. Return rootNode

About Huffman Coding

Huffman Coding Complexity

The time complexity for encoding each unique character based on its frequency is O(nlog n).

Extracting minimum frequency from the priority queue takes place 2*(n-1) times and its complexity is O(log n). Thus the overall complexity is O(nlog n).