Huffman Coding — Lossless Compression from Scratch

The Story That Explains Huffman Coding

Huffman Coding is a lossless data compression algorithm that assigns variable-length binary codes to characters based on their frequency of occurrence. Characters that appear more often get shorter codes; characters that appear rarely get longer codes. The result: the same data stored in fewer bits.

Benefits & Use Cases

How Huffman Coding Works — Step by Step

Animated Huffman Tree Diagram

Click ▶ Next Step to watch each merge happen live. The tree builds from the bottom up.

Code Table — Final Codes for "ABRACADABRA"

Python Implementation — Step-by-Step with Line Annotations

Each code block below is followed by an animated explainer showing exactly what that block does.

Part 1 — The Node Class

# Each node in the Huffman tree holds a character, its frequency,
# and pointers to its left and right children.
class HuffmanNode:
    def __init__(self, char, freq):
        self.char  = char   # The character (None for internal nodes)
        self.freq  = freq   # Frequency / weight of this node
        self.left  = None  # Left child  → bit '0'
        self.right = None  # Right child → bit '1'

    # Needed so heapq can compare nodes by frequency
    def __lt__(self, other):
        return self.freq < other.freq

Part 2 — Build the Huffman Tree

import heapq
from collections import Counter

def build_huffman_tree(text):
    # ── Step 1: Count frequency of each character ──────────────
    freq = Counter(text)                # {'A':5, 'B':2, 'R':2, 'C':1, 'D':1}

    # ── Step 2: Build a min-heap of leaf nodes ─────────────────
    heap = [HuffmanNode(ch, f) for ch, f in freq.items()]
    heapq.heapify(heap)               # O(n) — turns list into min-heap

    # ── Step 3: Merge until one root remains ───────────────────
    while len(heap) > 1:
        left  = heapq.heappop(heap)   # pop smallest frequency node
        right = heapq.heappop(heap)   # pop second smallest

        merged = HuffmanNode(None, left.freq + right.freq)
        merged.left  = left            # left child  → bit 0
        merged.right = right           # right child → bit 1

        heapq.heappush(heap, merged)   # push merged node back

    return heap[0]                     # return root node

Part 3 — Generate Codes by Traversing the Tree

def generate_codes(node, prefix="", codebook=None):
    if codebook is None:
        codebook = {}

    if node is None:
        return codebook

    # Leaf node → we've reached a character, store its code
    if node.char is not None:
        codebook[node.char] = prefix or "0"  # edge case: single char
        return codebook

    # Internal node → recurse left (add '0') and right (add '1')
    generate_codes(node.left,  prefix + "0", codebook)  # ← bit 0
    generate_codes(node.right, prefix + "1", codebook)  # ← bit 1

    return codebook

Part 4 — Encode & Decode Functions

def huffman_encode(text):
    if not text:
        return "", {}, None

    root     = build_huffman_tree(text)     # build the tree
    codebook = generate_codes(root)         # map char → binary string
    encoded  = "".join(codebook[ch] for ch in text)  # encode every char
    return encoded, codebook, root


def huffman_decode(encoded_bits, root):
    decoded = []
    node    = root

    for bit in encoded_bits:
        # Walk down the tree: '0' go left, '1' go right
        node = node.left if bit == "0" else node.right

        # When we hit a leaf, we've decoded one character
        if node.char is not None:
            decoded.append(node.char)
            node = root                     # reset to root for next char

    return "".join(decoded)

Part 5 — Full Working Example with Output

# ── Full demonstration ──────────────────────────────────────
text = "ABRACADABRA"

encoded, codebook, root = huffman_encode(text)

print("=== Huffman Codebook ===")
for char, code in sorted(codebook.items(), key=lambda x: len(x[1])):
    print(f"  '{char}'  →  {code}  ({len(code)} bits)")

print(f"\nOriginal  : {text}")
print(f"Encoded   : {encoded}")
print(f"\nOriginal bits  : {len(text) * 8}")
print(f"Compressed bits: {len(encoded)}")
print(f"Compression    : {100*(1 - len(encoded)/(len(text)*8)):.1f}%")

decoded = huffman_decode(encoded, root)
print(f"\nDecoded   : {decoded}")
print(f"Lossless? : {decoded == text}")

Interactive Compressor — Try Your Own Text

Type any text below and watch the Huffman table, compression ratio, and encoded bits update in real time.

Time & Space Complexity

Key Properties — Prefix-Free Codes

Huffman vs Other Compression Methods

Real-World Implementation — Compress a File

import os, struct, pickle

def compress_file(input_path, output_path):
    # ── Read the raw file ───────────────────────────────────────
    with open(input_path, 'rb') as f:
        data = f.read()

    text = data.decode('latin-1')    # bytes → string (all 256 byte values)

    # ── Build tree and encode ───────────────────────────────────
    encoded, codebook, root = huffman_encode(text)

    # ── Pack bits into bytes (8 bits per byte) ──────────────────
    padded_len = (8 - len(encoded) % 8) % 8   # bits to pad
    encoded   += '0' * padded_len               # right-pad to byte boundary

    byte_array = bytearray()
    for i in range(0, len(encoded), 8):
        byte_array.append(int(encoded[i:i+8], 2))  # binary → int

    # ── Write: [padding_length(1 byte)] [codebook] [data] ───────
    with open(output_path, 'wb') as f:
        f.write(struct.pack('B', padded_len))    # 1 byte: padding info
        codebook_bytes = pickle.dumps(codebook)
        f.write(struct.pack('I', len(codebook_bytes)))  # 4 bytes: table length
        f.write(codebook_bytes)                     # codebook itself
        f.write(bytes(byte_array))                  # compressed data

    orig_size = os.path.getsize(input_path)
    comp_size = os.path.getsize(output_path)
    print(f"Original : {orig_size:,} bytes")
    print(f"Compressed: {comp_size:,} bytes")
    print(f"Ratio    : {100*(1-comp_size/orig_size):.1f}% saved")


# ── Quick test with a large repetitive file ─────────────────
with open("test.txt", "w") as f:
    f.write("AABABCABCDABCDE" * 1000)

compress_file("test.txt", "test.huf")

Golden Rules — What Every Developer Must Know