Huffman Coding

Text is stored with fixed-length codes: ASCII uses 8 bits for every character. But in English text, e is far more common than z. Huffman coding (David Huffman, 1952) gives frequent characters short codes and rare characters long codes, producing an optimal compression for a given set of frequencies. It is used inside ZIP, gzip, PNG and JPEG.

#Prefix-free codes

To decode a bit stream without separators, no code may be a prefix of another. If a = 0 and b = 01, then 01 could be "ab…" or "b". Huffman codes are always prefix-free because every character sits at a leaf of a binary tree.

#The algorithm

1. Create a leaf node for each character with its frequency, and put them all in a min-priority queue.
2. Repeat until one node remains:
   • Remove the two lowest-frequency nodes.
   • Create a new internal node with these two as children and frequency = their sum.
   • Insert it back into the queue.
3. The remaining node is the root. Label left edges 0 and right edges 1; each character's code is the path from the root.

The greedy choice is "merge the two rarest symbols first", which pushes them deepest into the tree.

#Example

Merges: f(5)+e(9)=14 → c(12)+b(13)=25 → 14+d(16)=30 → 25+30=55 → a(45)+55=100.

#include <iostream>
#include <queue>
#include <vector>
#include <map>
#include <string>
using namespace std;

struct Node {
    char ch;
    int freq;
    Node *left, *right;
    Node(char c, int f, Node *l = nullptr, Node *r = nullptr) : ch(c), freq(f), left(l), right(r) {}
};

struct ByFreq {
    bool operator()(Node *a, Node *b) const {
        return a->freq != b->freq ? a->freq > b->freq : a->ch > b->ch;   // min-heap, ties broken by char
    }
};

void collect(Node *n, const string &code, map<char, string> &codes) {
    if (!n->left) { codes[n->ch] = code.empty() ? "0" : code; return; }
    collect(n->left, code + "0", codes);
    collect(n->right, code + "1", codes);
}

int main() {
    vector<pair<char, int>> freq = {{'a', 45}, {'b', 13}, {'c', 12}, {'d', 16}, {'e', 9}, {'f', 5}};
    priority_queue<Node *, vector<Node *>, ByFreq> pq;
    for (auto [c, f] : freq) pq.push(new Node(c, f));
    char nextId = '1';                       // labels for internal nodes, used only for tie-breaking
    while (pq.size() > 1) {
        Node *x = pq.top(); pq.pop();
        Node *y = pq.top(); pq.pop();
        pq.push(new Node(nextId++, x->freq + y->freq, x, y));
    }
    map<char, string> codes;
    collect(pq.top(), "", codes);
    int bits = 0, total = 0;
    for (auto [c, f] : freq) {
        cout << c << " (freq " << f << "): " << codes[c] << endl;
        bits += f * codes[c].size();
        total += f;
    }
    cout << "Huffman bits: " << bits << ", fixed 3-bit code: " << total * 3
         << ", saving " << 100 - bits * 100 / (total * 3) << "%" << endl;
    return 0;
}

a (freq 45): 0
b (freq 13): 101
c (freq 12): 100
d (freq 16): 111
e (freq 9): 1101
f (freq 5): 1100
Huffman bits: 224, fixed 3-bit code: 300, saving 26%

The program's codes may differ from the diagram in which child goes left (ties can be broken either way), but the code lengths and total bits are always the same: 224 bits versus 300 for a fixed 3-bit code.

#Analysis

• n − 1 merges, each doing O(log n) priority-queue operations → O(n log n).
• Huffman's code is optimal among prefix codes: no other prefix code gives a smaller total Σ freq × code length.

#Decoding

Start at the root; read bits, going left on 0 and right on 1; when you reach a leaf, output its character and return to the root. With the codes in the diagram, 0101100 splits in only one way, 0 | 101 | 100, and decodes to abc.