Huffman Coding 🎯

Welcome to a fascinating journey into the world of data compression! Today, we're going to learn about Huffman Coding, a fundamental algorithm in the field of data structures and algorithms. This technique is widely used for lossless data compression, making it a valuable skill for any developer. Let's get started!

What is Huffman Coding? 📝

Huffman Coding is a popular lossless data compression algorithm that assigns variable-length codes to input characters such that frequently occurring characters are assigned shorter codes. This makes it possible to represent data using fewer bits, thereby saving storage space or reducing transmission time.

Why Huffman Coding? 💡

Huffman Coding is appealing due to its efficiency, adaptability, and simplicity. Here are some reasons why:

Lossless Compression: Huffman Coding allows for lossless data compression, meaning the original data can be perfectly reconstructed from the compressed data.
Efficient: By assigning shorter codes to frequently occurring characters, Huffman Coding achieves a higher compression ratio than other simple coding methods like ASCII encoding.
Adaptable: Huffman Coding can be used for text files, images, and other types of data, making it a versatile tool in the data compression landscape.

How Huffman Coding Works? 💡

Let's dive into the process of creating Huffman codes step by step:

Frequency Table: First, we create a frequency table for the input characters. The table lists each character and its corresponding frequency count in the input data.

Character | Frequency
----------|------------
'a'       | 10
'b'       | 5
'c'       | 7
'd'       | 3
'e'       | 15

Node Creation: Next, we create a binary tree with each node representing a character and its frequency count. Leaves represent individual characters, while internal nodes represent the sum of their child nodes' frequencies.

Huffman Tree Diagram

Huffman Code Assignment: Starting from the root node, we assign codes to each character by following the path from the root to the corresponding leaf node. If a node is visited multiple times, we assign different codes to its child nodes.

Character | Code
----------|------
'a'       | 0
'b'       | 10
'c'       | 110
'd'       | 1110
'e'       | 1111

Compression: Finally, we replace each character in the input data with its corresponding Huffman code. The result is a compressed representation of the original data.

Implementing Huffman Coding 💡

Let's implement Huffman Coding in Python:

python

def build_huffman_tree(frequencies):
    heap = [(freq, char, Node(char, freq)) for char, freq in frequencies.items()]
    while len(heap) > 1:
        left, right = heap.pop(0), heap.pop(0)
        parent = Node(None, left[0] + right[0])
        parent.left = left[2]
        parent.right = right[2]
        heap.append((parent.freq, None, parent))
    return parent

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

def compress(text, frequencies):
    tree = build_huffman_tree(frequencies)
    codes = {}

    def assign_codes(node, code):
        if node:
            if node.char is not None:
                codes[node.char] = code
            if node.left:
                assign_codes(node.left, code + '0')
            if node.right:
                assign_codes(node.right, code + '1')

    assign_codes(tree, '')

    compressed = ''.join(codes[char] for char in text)
    return compressed, codes

def decompress(compressed, codes, root):
    result = ''

    def decode(node, code):
        if node:
            if node.char is not None:
                result += node.char
            if node.left and code == '0':
                decode(node.left, code + '0')
            if node.right and code == '1':
                decode(node.right, code + '1')

    start = 0
    while start < len(compressed):
        code = ''
        while start + len(code) < len(compressed) and compressed[start + len(code)] == code[-1]:
            code += compressed[start + len(code)]
        decode(root, code)
        start += len(code) + 1

    return result

text = 'abbbbcdede'
frequencies = {'a': 10, 'b': 5, 'c': 7, 'd': 3, 'e': 15}
compressed, codes = compress(text, frequencies)
print('Compressed data:', compressed)

root = build_huffman_tree(frequencies)
decompressed = decompress(compressed, codes, root)
print('Decompressed data:', decompressed)

That's it for today! In the next lesson, we'll dive deeper into Huffman Coding and explore its applications, variations, and optimizations. Until then, happy coding! 💻✨