Huffman Coding
Without treatment of some common problems and discussion and analysis of the algorithms that answer them, no introductory computer science algorithms course would be complete. Heapsort and quicksort, balanced search tree dictionary structures, Knuth-Morris-Pratt pattern search, Dijkstra’s algorithm for single-source shortest paths, and, of course, David Huffman’s iconic 1951 algorithm for determining minimum-cost prefix-free codes, also known as Huffman coding, are just a few of the important techniques.
Scanning the data and calculating the frequency of each byte’s occurrence;
Place those nodes in a reverse priority queue depending on their frequencies (the nodes with the lowest frequencies are given priority);
Begin a loop and continue until the queue is empty.
Remove two nodes from the queue and merge them into a single internal node with a frequency equal to the sum of the two nodes’ frequencies;
As children of the newly generated internal node, add the two nodes that were removed from the queue.
Add the newly generated internal node to the queue.
The root of the tree is the final node on the queue.
The process of decoding is deceptively simple. Huffman encoding is a prefix-free encoding technique that avoids ambiguity. There isn’t a single codeword that appears as a prefix to another codeword. Follow the zeros and ones to a leaf and return the character there to decode the encoded message.
Get Cem Baysal’s stories in your inbox
Join Medium for free to get updates from this writer.
String: BCCABBDDAECCBBAEDDCC
Compressed: 101111001101001010010001111101000100001011111
Therefore, Huffman coding turns out to be a simple and efficient way to encode data into short representations without losing information.
