Huffman Coding

Huffman Coding

Huffman Coding is an algorithm used for lossless data compression.

Huffman Coding is also used as a component in many different compression algorithms. It is used as a component in lossless compressions such as zip, gzip, and png, and even as part of lossy compression algorithms like mp3 and jpeg.

Use the animation below to see how a text can be compressed using Huffman Coding.

The animation shows how the letters in a text are normally stored using UTF-8, and how Huffman Coding makes it possible to store the same text with fewer bits.

Huffman Coding uses a variable length of bits to represent each piece of data, with a shorter bit representation for the pieces of data that occurs more often.

Furthermore, Huffman Coding ensures that no code is the prefix of another code, which makes the compressed data easy to decode.

Creating A Huffman Code Manually

To get a better understanding of how Huffman Coding works, let's create a Huffman code manually, using the same text as in the animation: 'lossless'.

A text is normally stored in the computer using UTF-8, which means that each letter is stored using 8 bits for normal latin letters, like we have in 'lossless'. Other letters or symbols such as '€' or '🦄' are stored using more bits.

To compress the text 'lossless' using Huffman Coding, we start by counting each letter.

As you can see in the nodes above, 's' occurs 4 times, 'l' occurs 2 times, and 'o' and 'e' occurs just 1 time each.

We start building the tree with the least occurring letters 'o' and 'e', and their parent node gets count '2', because the counts for letter 'o' and 'e' are summarized.

The next nodes that get a new parent node, are the nodes with the lowest count: 'l', and the parent node of 'o' and 'e'.

Now, the last node 's' must be added to the binary tree. Letter node 's' and the parent node with count '4' get a new parent node with count '8'.

Following the edges from the root node, we can now determine the Huffman code for each letter in the word 'lossless'.

The Huffman code for each letter can now be found under each letter node in the image above. A good thing about Huffman coding is that the most used data pieces get the shortest code, so just '0' is the code for the letter 's'.

As mentioned earlier, such normal latin letters are usually stored with UTF-8, which means they take up 8 bits each. So for example the letter 'o' is stored as '01101111' with UTF-8, but it is stored as '110' with our Huffman code for the word 'lossless'.

To summarize, we have now compressed the word 'lossless' from its UTF-8 code

01101100 01101111 01110011 01110011 01101100 01100101 01110011 01110011

to just

10 110 0 0 10 111 0 0

using Huffman Coding, which is a huge improvement.

But if data is stored with Huffman Coding as 10 110 0 0 10 111 0 0, or the code is sent to us, how can it be decoded so that we see what information the Huffman code contains?

Furthermore, the binary code is really 10110001011100, without the spaces, and with variable bit lengths for each piece of data, so how can the computer understand where the binary code for each piece of data starts and ends?

Decoding Huffman Code

Just like with code stored as UTF-8, which our computers can already decode to the correct letters, the computer needs to know which bits represent which piece of data in the Huffman code.

So along with a Huffman code, there must also be a conversion table with information about what the Huffman binary code is for each piece of data, so that it can be decoded.

So, for this Huffman code:

100110110

With this conversion table:

Are you able to decode the Huffman code?

We start with the first bit:

There is no letter in the table with just 1 as the Huffman code, so we continue and include the next bit as well.

We can see from the table that 10 is 'b', so now we have the first letter. We check the next bit:

We find that 0 is 'a', so now we have the two first letters 'ba' stored in the Huffman code.

We continue looking up Huffman codes in the table:

Code 11 is 'n'.

Code 0 is 'a'.

Code 11 is 'n'.

Code 0 is 'a'.

The Huffman code is now decoded, and the word is 'banana'!

Huffman Code Prefixes

An interesting and very useful part of the Huffman coding algorithm is that it ensures that there is no code that is the prefix of another code.

This property, that no code is the prefix of another code, makes it possible to decode. And it is especially important in Huffman Coding because of the variable bit lengths.

Huffman Coding Implementation

The correct word for creating Huffman code based on data or text is "encoding", and the opposite would be "decoding", when the original data or text is recreated based on the code.

The code example below takes a word, or any text really, and compress it using Huffman Coding.

class Node:
    def __init__(self, char=None, freq=0):
        self.char = char
        self.freq = freq
        self.left = None
        self.right = None

nodes = []

def calculate_frequencies(word):
    frequencies = {}
    for char in word:
        if char not in frequencies:
            freq = word.count(char)
            frequencies[char] = freq
            nodes.append(Node(char, freq))

def build_huffman_tree():
    while len(nodes) > 1:
        nodes.sort(key=lambda x: x.freq)
        left = nodes.pop(0)
        right = nodes.pop(0)
        
        merged = Node(freq=left.freq + right.freq)
        merged.left = left
        merged.right = right
        
        nodes.append(merged)

    return nodes[0]

def generate_huffman_codes(node, current_code, codes):
    if node is None:
        return

    if node.char is not None:
        codes[node.char] = current_code

    generate_huffman_codes(node.left, current_code + '0', codes)
    generate_huffman_codes(node.right, current_code + '1', codes)

def huffman_encoding(word):
    global nodes
    nodes = []
    calculate_frequencies(word)
    root = build_huffman_tree()
    codes = {}
    generate_huffman_codes(root, '', codes)
    return codes

word = "lossless"
codes = huffman_encoding(word)
encoded_word = ''.join(codes[char] for char in word)

print("Word:", word)
print("Huffman code:", encoded_word)
print("Conversion table:", codes)

Huffman Decoding Implementation

In addition to encode data using Huffman coding, we should also have a way to decode it, to recreate the original information.

The implementation below is basically the same as the previous code example, but with an additional function for decoding the Huffman code.

The huffman_decoding function takes the Huffman code, and the codes Python dictionary (a hashmap) with the characters and their corresponding binary codes. The Function then reverse the mapping, and checks the Huffman code bit-by-bit to recreate the original text.

class Node:
    def __init__(self, char=None, freq=0):
        self.char = char
        self.freq = freq
        self.left = None
        self.right = None

nodes = []

def calculate_frequencies(word):
    frequencies = {}
    for char in word:
        if char not in frequencies:
            freq = word.count(char)
            frequencies[char] = freq
            nodes.append(Node(char, freq))

def build_huffman_tree():
    while len(nodes) > 1:
        nodes.sort(key=lambda x: x.freq)
        left = nodes.pop(0)
        right = nodes.pop(0)
        
        merged = Node(freq=left.freq + right.freq)
        merged.left = left
        merged.right = right
        
        nodes.append(merged)

    return nodes[0]

def generate_huffman_codes(node, current_code, codes):
    if node is None:
        return

    if node.char is not None:
        codes[node.char] = current_code

    generate_huffman_codes(node.left, current_code + '0', codes)
    generate_huffman_codes(node.right, current_code + '1', codes)

def huffman_encoding(word):
    global nodes
    nodes = []
    calculate_frequencies(word)
    root = build_huffman_tree()
    codes = {}
    generate_huffman_codes(root, '', codes)
    return codes

def huffman_decoding(encoded_word, codes):
    current_code = ''
    decoded_chars = []

    # Invert the codes dictionary to get the reverse mapping
    code_to_char = {v: k for k, v in codes.items()}

    for bit in encoded_word:
        current_code += bit
        if current_code in code_to_char:
            decoded_chars.append(code_to_char[current_code])
            current_code = ''

    return ''.join(decoded_chars)

word = "lossless"
codes = huffman_encoding(word)
encoded_word = ''.join(codes[char] for char in word)
decoded_word = huffman_decoding(encoded_word, codes)

print("Initial word:", word)
print("Huffman code:", encoded_word)
print("Conversion table:", codes)
print("Decoded word:", decoded_word)

You have now seen how a text can be compressed using Huffman coding, and how a Huffman code can be decoded to recreate the original text.