Huffman Coding Deep Dive

Huffman coding is one of the most classic lossless compression algorithms, proposed by David A. Huffman in 1952. This article provides a comprehensive analysis from mathematical principles to engineering implementation.

Historical Background

In 1952, David A. Huffman was pursuing his doctoral degree at MIT when his advisor Robert Fano assigned a topic: finding the optimal prefix coding method. Huffman abandoned the mainstream top-down approach of the time and instead adopted a bottom-up greedy strategy, ultimately discovering the algorithm that bears his name.^[1]

Mathematical Foundation

Information Entropy

Given a source symbol set $S = {s_1, s_2, ..., s_n}$ with probability distribution $P = {p_1, p_2, ..., p_n}$, information entropy is defined as:

$$ H(P) = -\sum_{i=1}^{n} p_i \log_2 p_i $$

Meaning of Entropy: Represents the average information content per symbol, and also the theoretical lower bound for lossless compression.

Prefix Codes

A prefix code is a special encoding where no codeword is a prefix of another. This guarantees unique decodability.

Example: {0, 10, 11} is a prefix code, but {0, 01, 11} is not (0 is a prefix of 01).

Optimal Prefix Code

An optimal prefix code minimizes the average code length:

$$ L = \sum_{i=1}^{n} p_i \cdot l_i $$

Where $l_i$ is the code length for symbol $s_i$.

Algorithm Principles

Core Idea

Huffman's algorithm uses a greedy strategy: repeatedly merge the two nodes with the smallest probabilities to build a binary tree.

Algorithm Steps

1. Create a leaf node for each symbol with weight = probability/frequency
2. Repeat until only one node remains:
   • Select the two nodes with smallest weights
   • Create a new node as their parent
   • New node weight = sum of two children's weights
3. The path from root to leaf determines the code (left=0, right=1)

Correctness Proof

Lemma: Let $x$ and $y$ be the two symbols with the smallest probabilities. There exists an optimal prefix code where $x$ and $y$ have the same code length and differ only in the last bit.

Proof: Let $a$ and $b$ be the two deepest leaves in the optimal code. If $x$ is not $a$, swapping $x$ and $a$ does not increase the average code length (since $p_x \leq p_a$). Similarly, we can swap $y$ and $b$. ∎

Implementation Details

Tree Building Algorithm

struct Node {
    uint8_t symbol;
    uint32_t freq;
    Node* left = nullptr;
    Node* right = nullptr;
};

struct Compare {
    bool operator()(Node* a, Node* b) {
        if (a->freq == b->freq) return a->symbol > b->symbol;
        return a->freq > b->freq;
    }
};

Node* buildHuffmanTree(const std::vector<uint32_t>& freqs) {
    // Use a min-heap (priority_queue is a max-heap by default; invert with >)
    std::priority_queue<Node*, std::vector<Node*>, Compare> pq;
    for (int sym = 0; sym < 256; ++sym) {
        if (freqs[sym] > 0) {
            pq.push(new Node{static_cast<uint8_t>(sym), freqs[sym]});
        }
    }

    // Merge until only one node remains
    while (pq.size() > 1) {
        Node* left = pq.top(); pq.pop();
        Node* right = pq.top(); pq.pop();
        Node* parent = new Node{0, left->freq + right->freq, left, right};
        pq.push(parent);
    }

    return pq.top();
}

Code Table Generation

void generateCodes(Node* root, const std::string& code,
                   std::array<std::string, 256>& codes) {
    if (root == nullptr) {
        return;
    }

    if (root->left == nullptr && root->right == nullptr) {
        // Leaf node: save the code
        codes[root->symbol] = code;
        return;
    }

    // Recursively generate codes for left and right subtrees
    generateCodes(root->left, code + "0", codes);
    generateCodes(root->right, code + "1", codes);
}

Edge Cases

Case	Handling Method
Empty input	Return predefined error code
Single symbol	Special handling: code length = 1, code = 0
Equal probabilities	Degrades to fixed-length coding
Zero frequency	Skip the symbol

Determinism Guarantee

To ensure deterministic binary output, when frequencies are equal, sort by symbol value:

// Comparison function: break ties by symbol value for deterministic output
struct Compare {
    bool operator()(Node* a, Node* b) {
        if (a->freq == b->freq) return a->symbol > b->symbol;
        return a->freq > b->freq;
    }
};

Binary Format

CompressKit's Huffman encoding output format:

| Magic (4 bytes) | Freq Count (4 bytes LE) | Frequencies (N × 4 bytes LE) | Bitstream |

• Magic: HFMN (0x48 0x46 0x4D 0x4E)
• Freq Count: Number of symbols (N)
• Frequencies: Frequency per symbol (little-endian)
• Bitstream: Encoded bit stream

Performance Analysis

Time Complexity

Operation	Complexity	Description
Tree building	O(σ log σ)	σ = alphabet size (256)
Code generation	O(σ)	Visit all leaf nodes
Encoding	O(n)	n = input length
Decoding	O(n)	Constant time per symbol

Space Complexity

• Encoder: O(σ) for code table
• Decoder: O(σ) for decode tree

Measured Performance

Implementation	Encoding Speed	Decoding Speed	Memory Usage
C++	312 MB/s	398 MB/s	1.8 MB

Comparison with Other Algorithms

Advantages

• ✅ Fast encoding and decoding
• ✅ Simple implementation
• ✅ Theoretical guarantee: optimal prefix code

Disadvantages

• ❌ Code length must be integer (less efficient than arithmetic coding)
• ❌ Need to store frequency table (overhead for small files)

Best Use Cases

• Speed-priority scenarios
• Real-time compression/decompression
• Embedded devices

Visualization

Encoding result: A=00, B=01, C=10, D=11

Further Reading

• Arithmetic Coding - Approaching the entropy limit
• Range Coding - Integer-based arithmetic coding
• Architecture - How algorithms plug into the buffer layer

References

---

1. Huffman, D. A. (1952). "A Method for the Construction of Minimum-Redundancy Codes". Proceedings of the IRE. 40 (9): 1098–1101. DOI:10.1109/JRPROC.1952.273898 ↩︎