Huffman Decoding

Decompress your Huffman-encoded data to obtain your initial data

We already saw how to encode a given data using Huffman Encoding in Huffman Encoding & Python Implementation post. Now we will examine how to decode a Huffman Encoded data to obtain the initial, uncompressed data again.

Having our Binary Huffman Tree obtained during encode phase, decoding is a very simple process to perform.

Let’s consider we have the same example with Huffman Encoding post, therefore we have AAAAAAABCCCCCCDDEEEEE as our initial data and 000000000000001110101010101011101101010101010 as encoded output with the following Huffman Tree:

“Image by Author”

Now the only thing we should do is starting from the head of Huffman Tree and from the beginning of the encoded data, each time we encounter 1 we go right and while we encounter 0, we go left through the Huffman Tree. When we reach at a leaf node, we obtain the symbol! Then we just start again from the head of Huffman Tree while moving forward on encoded data.

With a few lines added in huffman.py coming from Huffman Encoding & Python Implementation, we can easily implement Huffman_Decoding and here is the result:

def Huffman_Decoding(encoded_data, huffman_tree):
    tree_head = huffman_tree
    decoded_output = []
    for x in…