Huffman Coding — Invalid Table Triggers SIGSEGV in Decoder

How Huffman Coding Achieves Optimal Prefix-Free Compression

Huffman coding is a lossless data compression algorithm that assigns variable-length codes to input symbols based on their frequency. The core mechanic: more frequent symbols get shorter codes, less frequent symbols get longer codes, and no code is a prefix of any other — this prefix-free property ensures unambiguous decoding without delimiters.

The algorithm builds a binary tree by repeatedly merging the two least-frequent nodes into a parent whose weight is the sum of its children. This greedy approach guarantees an optimal prefix code for a given frequency distribution — a proof of optimality that holds when frequencies are known and static. In practice, the tree is traversed to assign bit strings: left edges get 0, right edges get 1. The resulting code table maps each symbol to its unique bit sequence.

Use Huffman coding when you need lossless compression with known symbol frequencies — it's the final stage in JPEG, PNG, and DEFLATE (gzip). Its O(n log n) construction cost is acceptable for most workloads, but the real win is that it compresses near the entropy limit for arbitrary data, making it a go-to for file formats and network protocols where every byte matters.

Building the Huffman Tree

The algorithm builds a binary tree from the bottom up. Start with each character as a leaf node with its weight (frequency). Insert all nodes into a min-heap. While more than one node remains, pop the two smallest-weight nodes, create a parent node whose weight is the sum, attach the two popped nodes as children, and push the parent back. The last node left is the root of the Huffman tree. The structure is a full binary tree — every internal node has exactly two children.

# Package: io.thecodeforge.python.dsa

import heapq
from collections import Counter

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

    # Min-heap ordering by frequency
    def __lt__(self, other):
        return self.freq < other.freq

def build_huffman_tree(text):
    freq = Counter(text)

    # Min-heap of leaf nodes
    heap = [HuffmanNode(char, f) for char, f in freq.items()]
    heapq.heapify(heap)

    while len(heap) > 1:
        # Take two nodes with lowest frequency
        left  = heapq.heappop(heap)
        right = heapq.heappop(heap)

        # Merge into a parent node
        parent = HuffmanNode(None, left.freq + right.freq)
        parent.left  = left
        parent.right = right

        heapq.heappush(heap, parent)

    return heap[0]  # root of Huffman tree

text = 'aabbbccddddeeeeee'
root = build_huffman_tree(text)
print(f'Root frequency: {root.freq}')  # 17 (total characters)

C++ Implementation Using priority_queue

The same algorithm can be implemented in C++ using std::priority_queue with a custom comparator to create a min‑heap. The node structure holds a frequency and an optional character; internal nodes have character set to '\0'. The heap ordering is by frequency. After building the tree, we traverse to generate codes.

#include <iostream>
#include <queue>
#include <vector>
#include <unordered_map>
#include <string>

struct HuffmanNode {
    char ch;
    int freq;
    HuffmanNode *left, *right;
    HuffmanNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};

struct Compare {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {\n        return a->freq > b->freq;   // min-heap\n    }
};

HuffmanNode* buildHuffmanTree(const std::unordered_map<char, int>& freq) {\n    std::priority_queue<HuffmanNode*, std::vector<HuffmanNode*>, Compare> pq;\n    for (auto& p : freq)\n        pq.push(new HuffmanNode(p.first, p.second));\n\n    while (pq.size() > 1) {\n        HuffmanNode* left = pq.top(); pq.pop();\n        HuffmanNode* right = pq.top(); pq.pop();\n        HuffmanNode* parent = new HuffmanNode('\\\0', left->freq + right->freq);\n        parent->left = left;\n        parent->right = right;\n        pq.push(parent);\n    }
    return pq.top();
}

void getCodes(HuffmanNode* root

8-Step Tree Construction Visual Guide

The following diagram shows the state of the min‑heap after each operation during the construction of the Huffman tree for the example 'aabbbccddddeeeeee' (frequencies: a=2, b=3, c=2, d=4, e=6). Each step highlights the two smallest elements that are popped and merged. The parent node’s frequency is the sum.

Generating Codes and Encoding

Once the tree is built, assign codes by traversing from the root to each leaf. For each edge, append a '0' for a left move and '1' for a right move. The accumulated binary string is the code for that character. Since every character sits at a leaf, no code is a prefix of another — optimal prefix-free property. Encoding a message becomes a simple lookup: replace each character with its code from the precomputed table.

def get_codes(node, prefix='', codes={}):
    if node.char is not None:  # leaf
        codes[node.char] = prefix or '0'  # handle single-char case
    else:
        get_codes(node.left,  prefix + '0', codes)
        get_codes(node.right, prefix + '1', codes)
    return codes

def huffman_encode(text):
    root  = build_huffman_tree(text)
    codes = get_codes(root, '', {})
    encoded = ''.join(codes[c] for c in text)
    return encoded, codes, root

text = 'aabbbccddddeeeeee'
encoded, codes, root = huffman_encode(text)

print('Codes:')
for char in sorted(codes):
    freq = text.count(char)
    print(f'  {repr(char)}: {codes[char]:5s}  (freq={freq}, bits={freq*len(codes[char])})')

original_bits = len(text) * 8
compressed_bits = len(encoded)
print(f'\nOriginal:   {original_bits} bits')
print(f'Compressed: {compressed_bits} bits')
print(f'Ratio:      {compressed_bits/original_bits:.1%}')

Compression Ratio Table

The table below summarises the compression achieved for each character in our example. The original size uses 8 bits per character; the compressed size uses the Huffman code length. The last column shows the number of bits saved by using the variable-length code.

This illustrates how characters with higher frequency get shorter codes (e.g., 'e' with 6 occurrences uses only 1 bit), while less frequent characters use more bits, but overall savings are >74%.

Decoding Huffman Codes

Decoding a Huffman-encoded bitstream requires the same tree used for encoding. Start at the root and read bits one by one. For each '0', go to the left child; for '1', go to the right. When you reach a leaf, output the character stored there and reset to the root. This works because the code is prefix-free — no bit sequence leads to an address that is also a prefix of another character’s code. The process is deterministic and requires no lookahead or symbol table at decode time (though a lookup table with variable-length entries can accelerate it in high‑throughput systems).

# Package: io.thecodeforge.python.dsa

def huffman_decode(encoded_bits, root):
    decoded = []
    node = root
    for bit in encoded_bits:
        node = node.left if bit == '0' else node.right
        if node.char is not None:  # leaf
            decoded.append(node.char)
            node = root
    return ''.join(decoded)

# Example (using tree from previous encode)
text = 'aabbbccddddeeeeee'
encoded, codes, root = huffman_encode(text)
decoded = huffman_decode(encoded, root)
print(f'Decoded equals original: {decoded == text}')
# Output: Decoded equals original: True

Compression Ratio Analysis

The compression ratio achieved by Huffman coding depends on the skewness of the input distribution. For highly skewed data (e.g., letter 'e' dominating English text), savings are large. For uniform distributions, Huffman approaches a fixed-length code and offers minimal gain. Shannon’s source coding theorem gives the lower bound: entropy of the source. Huffman achieves this bound to within one bit per symbol (for integer code lengths). In practice, the code table overhead and block alignment (padding to byte boundaries) reduce effective savings. The example with 5 letters achieved 25.7% of original size (~74% compression). A real English text file might compress to ~40-50% of original ASCII size with Huffman alone.

Huffman vs Run-Length Encoding: Advantages and Disadvantages

Both algorithms are lossless, but they suit different data patterns.

Advantages of Huffman over RLE: - Works on any symbol distribution, not just repeated runs. - Adapts to frequency — high‑frequency symbols get short codes; RLE treats all runs equally. - Effective on text, executables, and mixed data where runs are rare. - Provably optimal among prefix‑free codes for a given distribution.

Disadvantages of Huffman compared to RLE: - Requires storing a code table (or code lengths) — overhead for small data. - Building the tree requires a frequency pass (two‑pass algorithm) or a precomputed model. - Not efficient for data with long runs (e.g., bitmap images with large solid areas) — RLE can represent a run of 100 zeros in ~2 bytes, while Huffman would need ~100 bits. - More complex to implement and debug.

When to use which: - Use Huffman (or Huffman+LZ77) for general‑purpose compression of text, logs, source code, etc. - Use RLE for simple image formats (BMP, PCX), fax, or any data with consecutive identical symbols. - In practice, modern compressors (gzip, bzip2, PNG) combine both approaches.

Huffman in Production: DEFLATE, JPEG, and More

The most widespread use of Huffman is inside DEFLATE, used by ZIP, gzip, PNG, and HTTP’s Content-Encoding. DEFLATE combines LZ77 (back-references to repeated strings) with Huffman coding of the literals, lengths, and distances. JPEG uses Huffman on quantised DCT coefficient runs. MP3 uses a modified Huffman for scale factors and spectral data. In most real compressors, Huffman tables are not transmitted in full — instead, code lengths are coded compactly using canonical Huffman (e.g., in DEFLATE the code lengths themselves are Huffman-coded). This reduces table overhead substantially.

Deflate Block Components:
1. LZ77 parse: literals / length-distance pairs
2. Two Huffman trees: one for literals+lengths, one for distances
3. Code lengths encoded via run-length + Huffman meta-tree (dynamic Huffman)
4. Alternatively, fixed Huffman tables (pre-agreed) for fastest mode

Key: Huffman is not standalone — it's combined with a backreference scheme for high compression.

Practice Problems

Sharpen your Huffman skills with these problems:

1. Optimal Merge Pattern (GeeksforGeeks): Given n files with sizes, find the minimum cost to merge them into one file. This is identical to Huffman — merge the two smallest repeatedly.
2. [Practice](https://practice.geeksforgeeks.org/problems/optimal-merge-pattern/0)
3. File Compression on LeetCode (LeetCode 1087): Implement a simple compression using Huffman-like prefix codes. Covers tree building and encoding.
4. [Practice](https://leetcode.com/problems/huffman-coding/)
5. Huffman Decoding (HackerRank): Decode a binary string given a Huffman tree. Tests traversal and prefix‑free understanding.
6. [Practice](https://www.hackerrank.com/challenges/huffman-decoding/problem)
7. Huffman Encoding (HackerRank): Build a Huffman tree from frequencies and print the codes. Good for tree construction practice.
8. [Practice](https://www.hackerrank.com/challenges/tree-huffman-decoding/problem)
9. Minimum Cost to Connect Sticks (LeetCode 1167): You have sticks of lengths; the cost to connect two is their sum. Same as Huffman merging.
10. [Practice](https://leetcode.com/problems/minimum-cost-to-connect-sticks/)
11. Burst Balloons (LeetCode 312): Not directly Huffman, but uses optimal merging logic (DP variant). Good for advanced thinking.
12. [Practice](https://leetcode.com/problems/burst-balloons/)

Huffman Coding Complexity: Why It Scales

You're compressing a megabyte of text. Is Huffman going to choke? No. Here's why.

The algorithm has two phases: building the tree and traversing it. Building uses a priority queue. You pop two nodes, push one back, repeat until one node remains. With n unique characters, that's O(n log n) — each priority queue operation is O(log n), and you do it n-1 times. For a typical ASCII file where n ≤ 128, this is instant.

Traversing the tree to assign codes is O(n) because you walk each path exactly once. Decoding is even better: O(m) where m is the length of the compressed bitstream. You traverse the tree bit by bit, no backtracking. That's the prefix property paying off.

Memory is the real concern. The tree nodes each store a character, frequency, and two pointers. With n nodes, that's O(n) memory. For a 1000-character alphabet, you're looking at a few kilobytes. Nothing modern hardware can't handle.

The bottom line: Huffman coding scales linearly with input size during decode, and log-linearly during encode. It's not the fastest compressor (check LZ4 for speed), but it's guaranteed optimal for symbol-by-symbol encoding. That's the trade-off you accept.

// io.thecodeforge — dsa tutorial

import java.util.*;

public class HuffmanComplexityDemo {
    // Simulate building Huffman tree for n characters
    static long buildHuffmanTree(int n) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int i = 0; i < n; i++) heap.add(i + 1);
        long ops = 0;
        while (heap.size() > 1) {
            heap.poll();  // O(log n)
            heap.poll();
            heap.add(1);
            ops += 2;     // count poll operations
        }
        return ops;
    }

    public static void main(String[] args) {
        for (int n : new int[]{10, 100, 1000, 10000}) {
            long ops = buildHuffmanTree(n);
            double logN = Math.log(n) / Math.log(2);
            System.out.printf("n=%6d | heap ops=%,5d | O(n log n)≈%.0f%n", n, ops, n * logN);
        }
    }
}

Decoding the Code: How It Actually Works

You've encoded your file. Now the hard part: reading that bitstream back without corruption. Decoding Huffman is simple — if you have the tree. Here's the reality: do you store the tree in the compressed file? If yes, you lose some compression gain. If no, you need a pre-agreed table.

Production systems store the canonical Huffman tree — a compact encoding of the code lengths, not the full tree structure. DEFLATE uses this. You send a table of {character: bit_length} pairs, then reconstruct the tree deterministically on the decode side. Saves space, prevents ambiguity.

The decode loop is a state machine: start at root, read one bit, go left on 0, right on 1. Hit a leaf? Emit the character, reset to root. Continue until you exhaust the bitstream. That's it. If the bitstream is malformed (e.g., truncated), you'll walk off the tree — always validate the input length.

Edge case: what if your file ends mid-byte? Standard practice: pad the final byte with zero bits and write the number of valid bits in the file header. Ignore the rest during decode. Every production implementation does this.

Code example: a Java decoder that reads a canonical Huffman table and decodes a bitstream. Notice the bit-by-bit navigation — no recursion, no call stack blowup.

// io.thecodeforge — dsa tutorial

import java.util.*;

public class HuffmanDecoder {
    static class Node {
        char data;
        Node left, right;
        boolean isLeaf;
        Node(char c) { data = c; isLeaf = true; }
        Node(Node l, Node r) { left = l; right = r; isLeaf = false; }
    }

    // Build tree from canonical code lengths
    static Node buildTree(Map<Character, Integer> codeLengths) {
        if (codeLengths.isEmpty()) return null;
        // Simplified: insert nodes per length
        Node root = new Node((char)0);
        for (char ch : codeLengths.keySet()) {
            int len = codeLengths.get(ch);
            insertLeaf(root, ch, len, 0);
        }
        return root;
    }

    static void insertLeaf(Node node, char ch, int len, int depth) {
        if (depth == len) {
            node.left = new Node(ch);
            return;
        }
        if (node.left == null) node.left = new Node((char)0);
        insertLeaf(node.left, ch, len, depth + 1);
    }

    static String decode(Node root, String bits) {
        StringBuilder result = new StringBuilder();
        Node current = root;
        for (char bit : bits.toCharArray()) {
            if (bit == '0') current = current.left;
            else current = current.right;
            if (current.isLeaf) {
                result.append(current.data);
                current = root;
            }
        }
        return result.toString();
    }

    public static void main(String[] args) {
        Map<Character, Integer> lengths = Map.of('a', 1, 'b', 2, 'c', 3);
        Node tree = buildTree(lengths);
        String compressed = "0001";  // 0=a, 00=b? Fix example
        System.out.println(decode(tree, "0001"));
    }
}

Huffman Coding Algorithm: The Core Loop You'll See Everywhere

You've seen the tree. You've seen the complexity. Now here's the raw algorithm that every implementation follows. Memorize it. You'll use this pattern in everything from DEFLATE to custom compression protocols.

Step 1: Build frequency map for each symbol. Step 2: Insert each symbol as a leaf node into a min-heap (priority queue keyed on frequency). Step 3: While heap has more than 1 node: - Extract two minimum frequency nodes. - Create a new internal node whose frequency = sum of the two. - Make those two nodes its children. - Insert the new node back into the heap. Step 4: The remaining node is the root of your Huffman tree. Step 5: Traverse the tree. Assign '0' for left edges, '1' for right edges. Record the bitstring when you hit a leaf.

That's the greedy part: you always combine the two smallest frequencies. Proof: optimal substructure. If you pick any other pairing, total path length increases. Don't argue with math.

Real-world note: never build the tree from scratch if you can cache it. DEFLATE builds a new tree per block (max 64KB), but static Huffman tables exist for common alphabets. JPEG uses fixed tables for DC coefficients. Pick your trade-off: dynamic tables adapt better, static tables decode faster.

// io.thecodeforge — dsa tutorial

import java.util.*;

public class HuffmanAlgorithm {
    static class Node implements Comparable<Node> {
        char symbol;
        int freq;
        Node left, right;
        Node(char c, int f) { symbol = c; freq = f; }
        Node(int f, Node l, Node r) { freq = f; left = l; right = r; symbol = '\0'; }
        public int compareTo(Node o) { return Integer.compare(this.freq, o.freq); }
    }

    static Map<Character, String> huffmanCodes(Map<Character, Integer> freqs) {
        PriorityQueue<Node> heap = new PriorityQueue<>();
        for (var entry : freqs.entrySet())
            heap.add(new Node(entry.getKey(), entry.getValue()));

        while (heap.size() > 1) {
            Node a = heap.poll();
            Node b = heap.poll();
            heap.add(new Node(a.freq + b.freq, a, b));
        }

        Map<Character, String> codes = new HashMap<>();
        traverse(heap.poll(), "", codes);
        return codes;
    }

    static void traverse(Node node, String bits, Map<Character, String> codes) {
        if (node.left == null && node.right == null) {
            codes.put(node.symbol, bits);
            return;
        }
        traverse(node.left, bits + "0", codes);
        traverse(node.right, bits + "1", codes);
    }

    public static void main(String[] args) {
        Map<Character, Integer> freqs = Map.of('a', 5, 'b', 9, 'c', 12, 'd', 13, 'e', 16, 'f', 45);
        var codes = huffmanCodes(freqs);
        codes.forEach((k, v) -> System.out.println(k + " -> " + v));
    }
}