Huffman Coding

The Huffman Tree is a unique use of a binary tree for the purpose of compression. In this implementation, each node within the tree is its own object. Each object is created when a file containing specific characters and their weight is read in. These nodes are created as “Leaf Nodes” and placed into a MinHeap for sorting purposes. The Nodes are then popped from the root two at a time and their weights are then added together. Each time this happens, a new “Internal Node” is created with the new weight, and the previous two nodes are now the left and right child of the internal node. Finally, the newly created internal node is placed into the MinHeap to be compared during the next iteration. This process continues until one internal node is left in the heap. This last node it the root node of the Huffman Tree.

With the created Huffman Tree, users can pass a user defined string to be encoded into a binary string. The string is created depending on the path from root to leaf node. Left child is “0” and right child is “1”.

Users can also pass in encoded binary strings and receive the reconstructed string. Both the encode and decode methods take advantage of recursion.

Git Repository