Huffman coding

Give common letters short codes and rare letters long ones, so a message takes fewer bits. Huffman's greedy rule, "join the two rarest", builds the best such code.

Time	Extra space	Output
\(O(n \log n)\) for \(n\) different letters	\(O(n)\)	a prefix-free code with the fewest total bits

The idea

A fixed-length code gives every letter the same number of bits: 6 letters need 3 bits each. But if a makes up 45% of a text, giving it a 1-bit code saves a lot, even if rare letters then need 4 bits.

Codes of different lengths must be prefix-free: no code is the start of another, so a stream of bits can be cut into letters without separators. Such a code is a binary tree: letters at the leaves, 0 for a left branch, 1 for a right branch, and a letter's code is its path from the top.

Huffman's rule builds the tree from the bottom:

1. Every letter is a one-node tree, weighted by its count.
2. Take the two lightest trees and join them under a new node whose weight is their sum.
3. Repeat until one tree is left.

The rarest letters end up deepest, with the longest codes.

How it works

1. Put every letter, with its count, into a min-heap.
2. While the heap has more than one tree: pop two, join them, push the result.
3. Walk the final tree to read off the codes.

The code breaks ties by the order trees were made, so all three languages print the same codes. (Different tie rules give different codes, all equally short.)

Code

PythonJavaC++

import heapq


def huffman(freq):
    """Huffman coding: the prefix-free binary code with the fewest total bits for these letter counts.
    freq is a list of (letter, count). Returns {letter: code}. Ties are broken by creation order, so the
    result is the same in every language."""
    heap = []                                # entries (count, id); ids 0..n-1 are the letters
    left, right = {}, {}
    for i, (_, f) in enumerate(freq):
        heapq.heappush(heap, (f, i))
    next_id = len(freq)
    while len(heap) > 1:                     # join the two rarest trees into one
        f1, a = heapq.heappop(heap)
        f2, b = heapq.heappop(heap)
        left[next_id], right[next_id] = a, b
        heapq.heappush(heap, (f1 + f2, next_id))
        next_id += 1
    codes = {}

    def walk(node, path):                    # left edge = 0, right edge = 1
        if node < len(freq):
            codes[freq[node][0]] = path or "0"
        else:
            walk(left[node], path + "0")
            walk(right[node], path + "1")
    walk(heap[0][1], "")
    return codes


if __name__ == "__main__":
    freq = [("a", 45), ("b", 13), ("c", 12), ("d", 16), ("e", 9), ("f", 5)]
    codes = huffman(freq)
    for letter, _ in freq:
        print(letter, codes[letter])
    total = sum(f * len(codes[ch]) for ch, f in freq)
    print("total bits:", total, "fixed 3-bit code:", 3 * sum(f for _, f in freq))
    print("face ->", "".join(codes[ch] for ch in "face"))

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class Huffman {
    static int[] left, right;
    static char[] letters;
    static Map<Character, String> codes;

    /** Huffman coding: the prefix-free binary code with the fewest total bits for these letter counts.
     *  Ties are broken by creation order, so the result is the same in every language. */
    static Map<Character, String> huffman(char[] ls, int[] freq) {
        int n = ls.length;
        letters = ls;
        left = new int[2 * n];
        right = new int[2 * n];
        // entries {count, id}; ids 0..n-1 are the letters
        PriorityQueue<long[]> heap = new PriorityQueue<>((x, y) -> x[0] != y[0] ? Long.compare(x[0], y[0]) : Long.compare(x[1], y[1]));
        for (int i = 0; i < n; i++) heap.add(new long[]{freq[i], i});
        int nextId = n;
        while (heap.size() > 1) {                     // join the two rarest trees into one
            long[] a = heap.poll(), b = heap.poll();
            left[nextId] = (int) a[1];
            right[nextId] = (int) b[1];
            heap.add(new long[]{a[0] + b[0], nextId});
            nextId++;
        }
        codes = new HashMap<>();
        walk((int) heap.peek()[1], "");
        return codes;
    }

    static void walk(int node, String path) {         // left edge = 0, right edge = 1
        if (node < letters.length) codes.put(letters[node], path.isEmpty() ? "0" : path);
        else { walk(left[node], path + "0"); walk(right[node], path + "1"); }
    }

    public static void main(String[] args) {
        char[] ls = {'a', 'b', 'c', 'd', 'e', 'f'};
        int[] freq = {45, 13, 12, 16, 9, 5};
        Map<Character, String> c = huffman(ls, freq);
        int total = 0, all = 0;
        for (int i = 0; i < ls.length; i++) {
            System.out.println(ls[i] + " " + c.get(ls[i]));
            total += freq[i] * c.get(ls[i]).length();
            all += freq[i];
        }
        System.out.println("total bits: " + total + " fixed 3-bit code: " + 3 * all);
        StringBuilder sb = new StringBuilder();
        for (char ch : "face".toCharArray()) sb.append(c.get(ch));
        System.out.println("face -> " + sb);
    }
}

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

vector<int> leftChild, rightChild;
vector<char> letters;
map<char, string> codes;

// Left edge = 0, right edge = 1.
void walk(int node, const string& path) {
    if (node < (int)letters.size()) codes[letters[node]] = path.empty() ? "0" : path;
    else { walk(leftChild[node], path + "0"); walk(rightChild[node], path + "1"); }
}

// Huffman coding: the prefix-free binary code with the fewest total bits for these letter counts.
// Ties are broken by creation order, so the result is the same in every language.
map<char, string> huffman(const vector<char>& ls, const vector<int>& freq) {
    int n = ls.size();
    letters = ls;
    leftChild.assign(2 * n, 0);
    rightChild.assign(2 * n, 0);
    // entries {count, id}; ids 0..n-1 are the letters
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> heap;
    for (int i = 0; i < n; i++) heap.push({freq[i], i});
    int nextId = n;
    while (heap.size() > 1) {                        // join the two rarest trees into one
        auto a = heap.top(); heap.pop();
        auto b = heap.top(); heap.pop();
        leftChild[nextId] = a.second;
        rightChild[nextId] = b.second;
        heap.push({a.first + b.first, nextId});
        nextId++;
    }
    codes.clear();
    walk(heap.top().second, "");
    return codes;
}

int main() {
    vector<char> ls = {'a', 'b', 'c', 'd', 'e', 'f'};
    vector<int> freq = {45, 13, 12, 16, 9, 5};
    map<char, string> c = huffman(ls, freq);
    int total = 0, all = 0;
    for (size_t i = 0; i < ls.size(); i++) {
        cout << ls[i] << " " << c[ls[i]] << "\n";
        total += freq[i] * c[ls[i]].size();
        all += freq[i];
    }
    cout << "total bits: " << total << " fixed 3-bit code: " << 3 * all << "\n";
    string out;
    for (char ch : string("face")) out += c[ch];
    cout << "face -> " << out << "\n";
}

Output: the codes a 0, b 101, c 100, d 111, e 1101, f 1100; total bits: 224 against 300 for a fixed 3-bit code (25% less); and face -> 110001001101. Reading that back: 1100 can only be f, 0 is a, 100 is c, 1101 is e.

When to use it

• Inside real compressors: DEFLATE (zip, gzip, PNG) and JPEG use Huffman codes for their last step.
• Any time symbols have very different frequencies and you can store or agree on the code table.
• As the textbook example of a greedy algorithm with a clean exchange proof.

Common mistakes

• Joining the two most frequent instead of the two least frequent.
• Only one distinct letter: the tree is a single leaf with an empty path; give it the code 0 (as the code does).
• Forgetting to send the code table: the decoder needs the tree, or the counts to rebuild it. Real formats send a compact "canonical" form.
• Expecting compression of random data: if all letters are equally common, Huffman can do little better than a fixed-length code, and nothing at all when the number of letters is a power of 2.

Going deeper

Each part below starts closed; open the ones you want.

Sample walkthrough: a 45, b 13, c 12, d 16, e 9, f 5

Step	Two lightest	New node	Trees left
1	f 5, e 9	14	a 45, b 13, c 12, d 16, (14)
2	c 12, b 13	25	a 45, d 16, (14), (25)
3	(14), d 16	30	a 45, (25), (30)
4	(25), (30)	55	a 45, (55)
5	a 45, (55)	100	one tree

Code lengths: a 1, b 3, c 3, d 3, e 4, f 4. Total bits: \(45 \cdot 1 + (13 + 12 + 16) \cdot 3 + (9 + 5) \cdot 4 = 45 + 123 + 56 = 224\).

The math: optimality and the entropy bound

For counts \(f_x\) and code lengths \(\ell_x\), the cost is \(B = \sum_x f_x \ell_x\), where \(\ell_x\) is the depth of \(x\) in the tree.

Lemma 1 (exchange). Some optimal tree has the two rarest letters \(x, y\) as siblings at the deepest level. Take an optimal tree and two sibling leaves \(p, q\) at the deepest level. Swapping \(x\) with \(p\) changes the cost by \((f_p - f_x)(\ell_x - \ell_p) \le 0\), since \(f_x \le f_p\) and \(\ell_x \le \ell_p\); so the cost does not rise. The same for \(y\) and \(q\).

Lemma 2 (merge). Replace \(x\) and \(y\) by one letter \(z\) with \(f_z = f_x + f_y\). A tree \(T'\) for the smaller alphabet becomes a tree \(T\) for the original by hanging \(x\) and \(y\) under \(z\), and \(B(T) = B(T') + f_x + f_y\). So \(T\) is optimal exactly when \(T'\) is.

Huffman does exactly this merge and then solves the smaller problem the same way, so by induction its tree is optimal.

Kraft's inequality. Lengths \(\ell_x\) belong to some prefix-free binary code exactly when \(\sum_x 2^{-\ell_x} \le 1\).

Entropy bound (Shannon). With \(p_x = f_x / N\), the average code length \(L\) of a Huffman code satisfies

\[H \le L < H + 1, \qquad H = -\sum_x p_x \log_2 p_x.\]

For the example, \(H \approx 2.22\) bits and \(L = 2.24\) bits per letter: very close. Arithmetic coding can get even closer to \(H\) by not rounding each letter to a whole number of bits.

Watch it step by step

Orange: the two lightest trees about to be joined. Red: the new node. The line below lists what is waiting in the heap.

Variations and related ideas

• Canonical Huffman codes: keep only the code lengths, then assign codes in order; the table becomes tiny. DEFLATE does this.
• Two-queue method: if the counts are already sorted, two plain queues replace the heap and the build is \(O(n)\).
• Adaptive Huffman (Faller–Gallager–Knuth, Vitter): the tree changes as the text is read; no table needed.
• Length-limited codes: the package-merge algorithm finds the best code with no code longer than \(L\) bits.
• Shannon–Fano coding, the older top-down method, is not always optimal; Huffman found the bottom-up rule as a student in 1951.

See also

• Binary heap
• Greedy algorithms
• Trie: another tree read by paths

References

• D. A. Huffman, "A method for the construction of minimum-redundancy codes", Proceedings of the IRE 40(9), 1952.
• C. E. Shannon, "A mathematical theory of communication", Bell System Technical Journal 27, 1948.
• T. H. Cormen et al., Introduction to Algorithms, 4th ed., Section 15.3 (Huffman codes).