10.3 Prefix Codes, Huffman Trees, and Decision Trees

Section 10.2 used rooted-tree order to visit and evaluate every vertex. This section places weights on tree leaves and asks a different optimization question: a frequently used symbol or a likely decision outcome should be reached by a short root-to-leaf path, while a rare one can tolerate a longer path.

This idea connects binary trees, the probabilities of Chapter 9, and greedy algorithms.

From symbols to bit strings

An alphabet is a finite set of symbols to encode. Let

A bit is either $0$ or $1$. A bit string is a finite sequence of bits, such as $0$, $101$, or $1110$. We write

for the set of all finite bit strings, including the empty string $\varepsilon$. The superscript star means “any finite length,” not multiplication.

A binary code is a function

that assigns a bit string, called a codeword, to each source symbol.

For example,

The encoded message $ABD$ is the concatenation

The receiver sees only the continuous bit stream, so codeword boundaries must be recoverable.

Prefix-free codes decode immediately

A bit string $x$ is a prefix of bit string $y$ when $y$ begins with all bits of $x$. For example, $01$ is a prefix of $0110$.

A code is prefix-free when no codeword is a prefix of a different codeword.

The example code is prefix-free. Once the decoder reads $0$, it knows the symbol is $A$ because no longer codeword begins with $0$. If the first bit is $1$, the decoder continues until reaching $10$, $110$, or $111$.

Contrast this with

The stream $01$ can mean $B$, or it can be split as $0\mid1$ and mean $AC$. Because $0$ is a prefix of $01$, decoding is ambiguous.

A prefix code is a binary tree

Represent a code with a rooted binary tree:

• label every left edge $0$ and every right edge $1$;
• place source symbols only at leaves;
• obtain a symbol's codeword by reading edge labels from the root to its leaf.

Why must symbols be leaves? If a symbol occupied an internal vertex, its root path would be a prefix of every codeword below it. Placing symbols only at leaves guarantees the prefix-free property.

For the example code, the paths are:

Decoding follows edges from the root. Every time a leaf is reached, output its symbol and return to the root for the next bits.

Kraft's inequality as a capacity check

Let codeword lengths be $\ell_1,\ell_2,\ldots,\ell_m$. Every binary prefix code satisfies

This is Kraft's inequality. A leaf at depth $\ell_i$ occupies a fraction $2^{-\ell_i}$ of all branches at a common deeper level. Prefix-free leaf regions do not overlap, so their fractions cannot exceed the whole tree.

The length set $1,2,3,3$ gives

The equality means the code tree uses its available leaf capacity completely. The inequality checks possible lengths; it does not by itself assign symbols to particular bit strings.

Operate a binary radio decoder with editable codewords and a live bit stream. The decoding cursor walks the tree, emits a symbol at each leaf, and exposes both prefix collisions and unfinished suffixes. Learners can repair an ambiguous codebook rather than merely being told it is invalid.

Expected code length

Suppose symbol $s_i$ occurs with probability $p_i$, where

If its codeword length is $\ell_i$, the number of bits used for one random symbol is a discrete random variable. By the expected-value definition from Chapter 9, the expected code length is

Shortening a frequent symbol reduces $L$ more than shortening a rare symbol by the same amount. This motivates variable-length codes.

When raw frequencies $f_i$ are given instead of probabilities, define the weighted path length

Because $p_i=f_i/\sum_j f_j$,

Minimizing $W$ and minimizing $L$ are therefore the same problem for a fixed frequency table.

Huffman's greedy merging algorithm

Huffman coding builds a prefix tree with minimum weighted path length among binary prefix codes for the given frequencies.

Begin with one leaf per symbol. Each leaf's weight is its frequency. Then repeat:

1. choose the two currently smallest weights; 2. make them children of a new parent; 3. give the parent their summed weight; 4. return the parent to the collection.

Stop when only one tree remains. Label each pair of child edges $0$ and $1$. Swapping left and right changes codewords but not their lengths or expected cost.

During the algorithm, the current collection is a forest of partial code trees: every merge joins two roots and reduces the number of components by one. Chapter 11 will reuse this forest viewpoint for graph algorithms, but Huffman's rule is specific—always merge the two lightest roots.

A complete Huffman example

Suppose the symbol frequencies are

The merge sequence is

One resulting tree gives lengths

Its weighted path length is

The frequencies sum to $100$, so the expected length is

Why merge the two smallest weights?

In some optimal full prefix tree, the two least frequent symbols can be placed as deepest sibling leaves. If two symbols occupy deeper positions than lighter symbols, swapping their locations cannot increase the weighted path length; putting smaller weights deeper is at least as good.

Merge those siblings into one temporary symbol whose weight is their sum. Any optimal tree for the smaller merged problem expands back into an optimal tree for the original problem. This creates the greedy structure:

Ties can produce different Huffman trees and codewords, but all valid tie choices preserve optimal weighted cost.

Build the Huffman forest by selecting two tokens to merge at every round. Legal lightest-pair choices grow a visible binary tree; an expensive choice remains reversible and shows its cost penalty. The completed forge derives codewords, depths, weighted path length, and expected bits per symbol.

Prefix codes are binary decision trees

A binary decision tree asks a yes-or-no question at each internal vertex. Each answer selects one child edge, and each leaf gives a final outcome. The number of questions used for an outcome equals its leaf depth.

If outcome $i$ has probability $p_i$ and depth $d_i$, the expected number of questions is

This is the same formula as expected code length: a $0/1$ code edge is a binary decision. Huffman coding therefore builds an optimal binary decision tree when any binary partition question is allowed and the goal is to minimize expected depth.

There is an important boundary: real decision problems may restrict which questions are legal. For example, a diagnostic system may only have access to certain tests. Huffman's unrestricted optimum is then a benchmark, not automatically a feasible decision procedure.

Expected depth and worst-case depth are also different objectives. Huffman minimizes the probability-weighted average, but a rare outcome may receive a long path. A system with a strict worst-case response limit may need a different tree.

Chapter 10 synthesis

1. A tree is connected and acyclic, so every vertex pair has a unique path.

2. Rooting creates hierarchy, depth, height, and ordered child positions.

3. Traversals turn tree structure into deterministic sequences and bottom-up computations.

4. Prefix trees turn root-to-leaf routes into unambiguous bit strings.

5. Huffman merging minimizes probability-weighted leaf depth.

Chapter 11 generalizes beyond trees to graphs. Cycles, multiple paths, degrees, connectivity, traversal, shortest routes, and minimum-cost connection backbones will all be studied in networks that no longer have the tree's unique-path restriction.