Huffman coding

Why it exists

Text, images and files are stored as bit strings. A fixed-length code gives every symbol the same number of bits ($\lceil \log_2 n \rceil$ for $n$ symbols), which wastes space when some symbols are far more frequent than others (the letter $e$ against $z$). Huffman coding gives frequent symbols short code words and rare ones long ones, in the best possible way: it produces the prefix code with the smallest average length. The algorithm is a textbook greedy algorithm (always merge the two least frequent), its proof is an exchange argument, and its implementation is a heap, so it is where the greedy method and the priority queue meet.

Prerequisites

You need the greedy method and its exchange proofs (greedy method) and the min-heap (binary heap).

Precise definitions

Code and code word. A code assigns to each symbol a string of bits, its code word. A message is encoded by concatenating the code words of its symbols.

Prefix code. No code word is a prefix (beginning) of another. Then the bit string can be decoded from left to right with no separators and no look-ahead: when the bits read so far equal a code word, that symbol is output. A prefix code corresponds to a binary tree whose leaves are the symbols; the code word of a leaf is the path from the root (0 for left, 1 for right).

Cost. For frequencies $f_i$ and code word lengths $\ell_i$ (the depth of the leaf), the cost is $B = \sum_i f_i \ell_i$ (the number of bits of the encoded message, if $f_i$ counts the occurrences). The average code length is $B / \sum f_i$. An optimal code minimises it.

Kraft inequality. A prefix code with code word lengths $\ell_1, \ldots, \ell_n$ exists if and only if $\sum_i 2^{-\ell_i} \le 1$. It holds with equality exactly for full binary trees (every internal node has two children), and an optimal code is always full.

Entropy. $H = -\sum_i p_i \log_2 p_i$ with $p_i = f_i / \sum f_j$. No code can have an average length below $H$, and the Huffman code satisfies $H \le \text{average length} < H + 1$.

How it works

The algorithm

1. Make a node for each symbol, with its frequency as weight.
2. While more than one node is left: remove the two nodes of smallest weight, make a new node with them as children (the smaller on the left, say) and the sum of their weights as weight, and insert it back.
3. The last node is the root. Read the code words from the root: $0$ for left, $1$ for right.

With a min-heap each of the $n - 1$ merges costs $O(\log n)$ (two extractions and one insertion): total $O(n \log n)$. With a plain sorted array or list it is $O(n^2)$; the C program below uses the simple version because it is short, with the same result.

The program runs the algorithm for six symbols with the frequencies $A = 35$, $B = 22$, $C = 17$, $D = 11$, $E = 9$, $F = 6$ (per $100$ symbols), prints every merge and the forest after it, then the code words.

#include <stdio.h>
 
#define MAXN 16
 
static int weight[2 * MAXN], left_[2 * MAXN], right_[2 * MAXN], total_nodes;
static char symbol[2 * MAXN];
 
static void show(int node) {                    /* prints a tree as nested parentheses: (left right) */
    if (left_[node] < 0) { printf("%c", symbol[node]); return; }
    printf("(");
    show(left_[node]);
    printf(" ");
    show(right_[node]);
    printf(")");
}
 
static void assign(int node, char *prefix, int depth, char codes[][MAXN]) {
    if (left_[node] < 0) { prefix[depth] = 0; for (int i = 0; i <= depth; i++) codes[symbol[node] - 'A'][i] = prefix[i]; return; }
    prefix[depth] = '0'; assign(left_[node], prefix, depth + 1, codes);
    prefix[depth] = '1'; assign(right_[node], prefix, depth + 1, codes);
}
 
int main(void) {
    const char *names = "ABCDEF";
    int freq[6] = {35, 22, 17, 11, 9, 6};
    int live[2 * MAXN], nlive = 6, cost = 0;
    for (int i = 0; i < 6; i++) { weight[i] = freq[i]; symbol[i] = names[i]; left_[i] = right_[i] = -1; live[i] = i; }
    total_nodes = 6;
    for (int step = 1; nlive > 1; step++) {
        int lo = 0, lo2 = -1;                              /* positions in live[] of the smallest and second smallest weight */
        for (int i = 1; i < nlive; i++) if (weight[live[i]] < weight[live[lo]]) lo = i;
        for (int i = 0; i < nlive; i++) if (i != lo && (lo2 < 0 || weight[live[i]] < weight[live[lo2]])) lo2 = i;
        int x = live[lo], y = live[lo2], z = total_nodes++;
        weight[z] = weight[x] + weight[y];
        left_[z] = x;
        right_[z] = y;
        cost += weight[z];
        printf("step %d: merge ", step); show(x); printf(":%d and ", weight[x]); show(y); printf(":%d -> %d (cost so far %d)\n", weight[y], weight[z], cost);
        live[lo] = z;                                      /* the new node replaces the first, the last live node fills the gap */
        live[lo2] = live[nlive - 1];
        nlive--;
        printf("  forest:");
        for (int i = 0; i < nlive; i++) { printf(" "); show(live[i]); printf(":%d", weight[live[i]]); }
        printf("\n");
    }
    char codes[6][MAXN], prefix[MAXN];
    assign(live[0], prefix, 0, codes);
    int bits = 0;
    for (int i = 0; i < 6; i++) {
        int len = 0;
        while (codes[i][len]) len++;
        bits += freq[i] * len;
        printf("code %c freq %2d %s\n", names[i], freq[i], codes[i]);
    }
    printf("total bits per 100 symbols: %d (fixed length: %d)\n", bits, 300);
    return 0;
}

step 1: merge F:6 and E:9 -> 15 (cost so far 15)
  forest: A:35 B:22 C:17 D:11 (F E):15
step 2: merge D:11 and (F E):15 -> 26 (cost so far 41)
  forest: A:35 B:22 C:17 (D (F E)):26
step 3: merge C:17 and B:22 -> 39 (cost so far 80)
  forest: A:35 (D (F E)):26 (C B):39
step 4: merge (D (F E)):26 and A:35 -> 61 (cost so far 141)
  forest: (C B):39 ((D (F E)) A):61
step 5: merge (C B):39 and ((D (F E)) A):61 -> 100 (cost so far 241)
  forest: ((C B) ((D (F E)) A)):100
code A freq 35 11
code B freq 22 01
code C freq 17 00
code D freq 11 100
code E freq  9 1011
code F freq  6 1010
total bits per 100 symbols: 241 (fixed length: 300)

The two smallest at first are $F = 6$ and $E = 9$, merged into $15$; then $D = 11$ with that $15$ gives $26$; $C = 17$ and $B = 22$ give $39$; $26$ and $A = 35$ give $61$; at last $39$ and $61$ give the root, $100$. The final tree (in nested notation) is $((C\ B)\ ((D\ (F\ E))\ A))$.

Reading the tree: $A = 11$, $B = 01$, $C = 00$, $D = 100$, $E = 1011$, $F = 1010$. The frequent symbols have two bits, the rare ones four.

The cost without the code words. Each merge creates one internal node whose weight is the sum of the frequencies below it; a symbol at depth $\ell$ is counted in $\ell$ internal nodes (all its ancestors). So $B = \sum_i f_i \ell_i = \sum_{\text{internal nodes}} \text{weight}.$ Here $15 + 26 + 39 + 61 + 100 = 241$: 241 bits per 100 symbols, an average of $2.41$ bits, against $300$ (3 bits each) for a fixed-length code, a saving of $19.7\%$. (The merge table shows this running sum.)

Decoding. Read bits until they equal a code word: $1\,1\,0\,1\,0\,0\,1\,0\,1\,1$ is $11\,01\,00\,1011$ = $A\,B\,C\,E$. Because no code word is a prefix of another, the first match is the only possible one.

Why it is optimal

Greedy choice. Let $x$ and $y$ be the two least frequent symbols. In an optimal tree the deepest leaves are the least frequent symbols (otherwise swapping a deeper, more frequent symbol with a shallower, less frequent one lowers the cost: an exchange argument), and the deepest level contains two sibling leaves (an optimal tree is full). So there is an optimal tree in which $x$ and $y$ are siblings at the deepest level: merging them first loses nothing.

Optimal substructure. Replace $x$ and $y$ by one symbol $z$ of frequency $f_x + f_y$. The cost of a tree for the original symbols equals the cost of the corresponding tree for the smaller alphabet plus $f_x + f_y$ (the extra depth of the two leaves). So an optimal tree for the original problem comes from an optimal tree for the smaller problem; by induction on $n$, Huffman's algorithm is optimal. $\blacksquare$

The result was also tested exhaustively: for random frequency sets the Huffman cost equalled the minimum over all code length assignments that form a complete prefix code.

Properties and shapes

• The code is not unique. Ties between equal weights, and the choice of which child is $0$, give different trees; all have the same cost (the minimum) but possibly different code word lengths.
• Number of nodes. $n$ leaves and $n - 1$ internal nodes (a full binary tree), so $n - 1$ merges.
• Equal frequencies, $n = 2^k$: every code word has $k$ bits: Huffman gives the fixed-length code. For other $n$ with equal frequencies the lengths are $\lfloor \log_2 n \rfloor$ or $\lceil \log_2 n \rceil$.
• Most skewed tree: the Fibonacci frequencies $1, 1, 2, 3, 5, 8, \ldots$ give a chain: the rarest symbols get codes of $n - 1$ bits.
• Entropy: the average length $L$ satisfies $H \le L < H + 1$. For frequencies that are all powers of $1/2$ (such as $\tfrac12, \tfrac14, \tfrac18, \tfrac18$) it equals $H$ exactly.
• Assumptions: it is optimal among codes that give each symbol a separate code word, for a known, fixed frequency table (which must also be stored or transmitted); adaptive and block-based codes can do better.

Worked examples

Cheat box

Traps and GATE patterns

Connections

Huffman's algorithm is a greedy algorithm (greedy method) that uses a min-heap (binary heap, heap applications). Like activity selection and fractional knapsack its proof is an exchange argument.

PYQs

Consider the string abbccddeee. Each letter in
the string must be assigned a binary code
satisfying the following properties:
For any two letters, the code assigned to one
letter must not be a prefix of the code assigned
to the other letter.
For any two letters of the same frequency, the
letter which occurs earlier in the dictionary order
is assigned a code whose length is at most the
length of the code assigned to the other letter.
Among the set of all binary code assignments
which satisfy the above two properties, what is
the minimum length of the encoded string?

A message is made up entirely of characters from
the set X = {P,Q,R,S,T} . The table of
probabilities of each character is shown below :

Character
Probability
P
0.22
Q
0.17
R
0.34
S
0.19
T
0.08
Total
1.00
A message of 100 characters over X is encoded
using Huffman coding. Then the excepted length
of the encoded message in bits is

Suppose the letters a, b, c, d, e, f have probabilities
1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively.
What is the average length of the Huffman code for
the letters a,b,c,d,e,f?

Suppose the letters a, b, c, d, e, f have probabilities
1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively.
Which of the following is the Huffman code for
the letter a, b, c, d, e, f?

The characters a to h have the set of frequencies
based on the first 8 Fibonacci numbers as
follows
a:1, b:1, c:2, d:3, e:5, f:8, g:13, h:21
A Huffman code is used to represent the
characters. What is the sequence of characters
corresponding to the following code?
110111100111010

Self-check

Revision card

References