Prefix Codes as Binary Trees

Binary Strings as Paths in a Tree

A binary code assigns finite strings of 0s and 1s to symbols. When no codeword is the beginning of another, a decoder can identify a codeword as soon as its final bit is read. Rooted binary trees make this structure visible: a 0 or 1 records which child is taken, and a codeword is the path from the root to a leaf. The depth of that leaf is the codeword's length, so frequencies can be used to calculate the total number of bits required.

A binary string is a finite sequence of bits. The empty string, denoted \(\varepsilon\), has length \(0\). For strings \(x\) and \(y\), \(x\) is a prefix of \(y\) if \(y\) begins with all the bits of \(x\); the string is a proper prefix if, in addition, \(x\ne y\). A set \(C\) of distinct binary strings is prefix-free if no member of \(C\) is a proper prefix of another member.

A tree can have vertices with just one child; it need not be a full binary tree. A codeword of length \(k\) labels a leaf at depth \(k\), where depth is the number of edges from the root. The set containing only \(\varepsilon\) is prefix-free and is represented by a tree consisting of a single root, which is also its leaf. The empty set is prefix-free as well, but it cannot label the leaves of a nonempty rooted tree. In the characterization below, the code set is therefore required to be nonempty. One could represent the empty set by separately allowing an empty tree, but that convention is not used here.

The Tree Characterization

Proof. First suppose \(C\) is prefix-free. Take as vertices all prefixes of strings in \(C\), including \(\varepsilon\). Join each nonempty prefix \(x\) to the prefix obtained by deleting its last bit; label that edge by the deleted bit. The resulting graph is connected: repeatedly deleting the last bit takes any vertex to \(\varepsilon\). It has no cycle, since each nonroot vertex has exactly one parent and repeatedly following parents strictly decreases string length until reaching the root. Thus it is a rooted tree. At each vertex there is at most one child labeled 0 and at most one child labeled 1, so it is binary.

Every string \(c\in C\) is a vertex. It is a leaf: if it had a child, then some string in \(C\) would have \(c\) as a proper prefix, contrary to prefix-freeness. Conversely, any leaf is in \(C\). Indeed, every vertex was included because it is a prefix of some \(c\in C\); if a leaf \(x\) were a proper prefix of \(c\), the next bit of \(c\) would give \(x\) a child. Therefore the leaves are exactly the strings in \(C\). This also covers \(C=\{\varepsilon\}\): the only prefix is the root, and it is a leaf.

Now suppose a finite rooted binary tree represents \(C\), with each codeword labeling a leaf. If two distinct leaf path labels \(x\) and \(y\) had \(x\) as a proper prefix of \(y\), then the path for \(y\) would continue past the vertex reached by the path for \(x\). That vertex would have a child, so it would not be a leaf. This contradicts the assumption that \(x\) labels a leaf. Thus no codeword is a proper prefix of another, and \(C\) is prefix-free. \(\square\)

Unique Decoding and the Empty Codeword

Prefix-freeness ensures unique parsing when all codewords are nonempty. Nonemptiness matters: if \(\varepsilon\) is a codeword, then it can be repeated any number of times without changing the concatenated string. For instance, the singleton set \(\{\varepsilon\}\) is prefix-free, but the empty bit string can be parsed as zero copies, one copy, two copies, or any number of copies of its codeword.

Proof. Existence of a parsing is part of the hypothesis that the bit string is a concatenation of codewords. To prove uniqueness, let a string \(w\) have two parsings. If \(w=\varepsilon\), no nonempty codeword can occur in either parsing, so both are the empty sequence of codewords. Now suppose \(w\ne\varepsilon\). Let \(x\) and \(y\) be the first codewords in the two parsings. Each is an initial segment of \(w\), so the shorter one is a prefix of the longer one. Since \(C\) is prefix-free, they cannot be distinct; therefore \(x=y\). Remove this common, nonempty initial segment from \(w\). The two remaining sequences parse the same suffix, whose length is strictly less than the length of \(w\). Induction on the length of \(w\), with the empty string as the base case, shows that the remaining parsings agree. Thus the original parsings agree, and because different symbols have different codewords, their symbol sequences agree as well. \(\square\)

This result concerns parsing strings that are concatenations of codewords; it does not claim that every possible binary string can be parsed. A string that ends partway through a codeword, for example, need not have any parsing. Also, the tree representation theorem permits \(\varepsilon\) in a prefix-free set, whereas the unique-decoding theorem above deliberately excludes it.

Weighted Path Lengths

Suppose symbol \(i\) occurs \(f_i\) times in a data source and is assigned codeword \(c_i\). The weighted path length of the code is the total number of bits used when encoding those occurrences:

If the total number of symbol occurrences is \(F=\sum_i f_i>0\), the average number of bits per symbol is \(L/F\). Equivalently, if \(p_i=f_i/F\) is the proportion of occurrences of symbol \(i\), then the average length is \(\sum_i p_i|c_i|\). The tree gives a direct way to compute these quantities: \(|c_i|\) is the depth of the leaf for symbol \(i\). The formula measures the cost of a specified code; it does not by itself find a code with minimum cost.

A Common Prefix Mistake

A codeword cannot be a leaf if another codeword extends it. For example, the set \(\{0,01\}\) is not prefix-free, because \(0\) is a proper prefix of \(01\). Its prefix tree has vertices \(V=\{\varepsilon,0,01\}\) and edges \(E=\{\varepsilon0,0\,01\}\). The path labeled \(0\) ends at an internal vertex, not at a leaf; the only leaf path label is \(01\). So this tree does not represent both proposed strings as leaf codewords.

A tempting but incorrect calculation is to treat both strings as leaves and assign them lengths \(1\) and \(2\). With frequencies \(f_0=3\) and \(f_{01}=2\), that gives the apparent weighted length \(3\cdot1+2\cdot2=7\). The calculation uses the wrong tree structure: the two proposed codewords are not prefix-free and cannot both label leaves. One prefix-free repair is to replace \(0\) by \(00\). The set \(\{00,01\}\) has tree \(V=\{\varepsilon,0,00,01\}\), \(E=\{\varepsilon0,0\,00,0\,01\}\), and both codewords label leaves. If the frequencies remain \(3\) and \(2\), the repaired assignment has weighted length \(3\cdot2+2\cdot2=10\) bits. The correction changes the code, so its cost must be recalculated from its actual leaf depths.

Tree depth is useful because it turns code length into a visible path measurement, and the weighted sum makes the effect of different symbol frequencies explicit. Prefix-freeness gives both the leaf structure and unambiguous decoding when codewords are nonempty. Finding an optimal prefix code from frequencies is a separate problem; the greedy construction and its proof are treated in the later material on the Huffman algorithm.