From Frequencies to a Code
Huffman coding assigns short codewords to frequent symbols and longer codewords to less frequent ones. The construction is a sequence of tree merges: at each step, the two lowest-weight available nodes become children of a new node. In this workshop, we will keep track of every merge, read codewords from the finished tree, and check the number of bits used. We will also see why different choices among tied weights can give different representations with the same cost.
Assume throughout that the alphabet is finite and has at least two symbols, and that every symbol has a positive integer frequency. The tree is a rooted, ordered, full binary tree: each internal vertex has exactly two children, designated left and right. Unless stated otherwise, an edge to a left child contributes bit \(0\), and an edge to a right child contributes bit \(1\). A leaf is labelled by one alphabet symbol; an internal vertex is labelled by the sum of the frequencies below it.
The Huffman construction begins with one leaf per symbol, weighted by its frequency. Repeatedly choose two available nodes of minimum weight, make them the children of a new parent, and give the parent the sum of their weights. Replace the chosen nodes by the parent. When one node remains, it is the root. If several nodes tie for minimum weight, any eligible pair may be selected; ties can affect the tree and the individual codewords.
Why the Tree Gives a Usable Code
Proof. Suppose the codeword for leaf \(x\) were an initial segment of the codeword for a different leaf \(y\). The path from the root to \(y\) would then begin with the entire path from the root to \(x\). Thus \(x\) would lie on the root-to-\(y\) path and would not be a leaf, since the path continues past \(x\). This contradicts the fact that \(x\) is a leaf. Therefore no leaf codeword is a prefix of another. \(\square\)
Prefix-freeness explains how to decode a bit string without separators. Starting at the root, follow the edge named by each bit. Whenever a leaf is reached, record its symbol and return to the root for the next bit. No completed symbol can be mistaken for the start of a longer codeword, because no codeword is a prefix of another. A valid complete encoded message ends at a leaf; a string that ends at an internal node is incomplete.
Proof. Fix a symbol \(i\) with frequency \(f_i\). The leaf for \(i\) has exactly \(\ell_i\) internal ancestors: one for each edge on its root-to-leaf path. At each such ancestor, the frequency \(f_i\) is included in that internal vertex's weight, because the weight is the sum of the frequencies of all leaves below it. Therefore \(f_i\) is counted exactly \(\ell_i\) times when the internal weights are summed. Summing this count over all symbols gives \(\sum_i f_i\ell_i\), which is the weighted bit cost. If there are at least two leaves, every leaf has at least one internal ancestor, and the argument includes all leaves and all internal vertices. \(\square\)
Worked Example: Six Symbols
Worked Example: Six Symbols
Take the frequency table \(A:45,\ B:13,\ C:12,\ D:16,\ E:9,\ F:5\). At each step, the available weights are the unmerged leaves and the roots of the subtrees already formed. The table records the selected pair and its new parent weight.
| Step | Two minimum-weight nodes | New node | New weight |
|---|---|---|---|
| 1 | F:5 and E:9 | FE | 5 + 9 = 14 |
| 2 | C:12 and B:13 | CB | 12 + 13 = 25 |
| 3 | FE:14 and D:16 | FED | 14 + 16 = 30 |
| 4 | CB:25 and FED:30 | CBFED | 25 + 30 = 55 |
| 5 | A:45 and CBFED:55 | root | 45 + 55 = 100 |
For definiteness, put the first selected node on the left and the second on the right at each merge. The resulting tree has \(A\) on the root's left and the subtree \(CBFED\) on its right. Within that right subtree, \(CB\) is left and \(FED\) is right; \(C\) is left of \(B\), and \(FE\) is left of \(D\), with \(F\) left of \(E\). Reading each path gives these codewords:
| Symbol | Frequency | Codeword | Length | Frequency times length |
|---|---|---|---|---|
| A | 45 | 0 | 1 | 45 × 1 = 45 |
| B | 13 | 101 | 3 | 13 × 3 = 39 |
| C | 12 | 100 | 3 | 12 × 3 = 36 |
| D | 16 | 111 | 3 | 16 × 3 = 48 |
| E | 9 | 1101 | 4 | 9 × 4 = 36 |
| F | 5 | 1100 | 4 | 5 × 4 = 20 |
The total cost is \(45+39+36+48+36+20=224\) bits. As an independent check using the proposition, add the internal weights: \(14+25+30+55+100=224\). The frequency total is \(45+13+12+16+9+5=100\), matching the root weight.
For example, the string \(FACE\) is encoded by concatenating \(F=1100\), \(A=0\), \(C=100\), and \(E=1101\): \(1100|0|100|1101=110001001101\). Its length is \(4+1+3+4=12\) bits, the same as the length of the displayed concatenation.
Ties and Different Valid Trees
A tie does not mean that a frequency table determines a unique tree. The algorithm requires that two minimum-weight nodes be selected, but if more than two nodes share the minimum weight, several selections may satisfy that rule. The resulting codewords can differ in length, while the weighted cost may remain the same.
Worked Example: Two Tie Choices
Use the frequency table \(A:1,\ B:1,\ C:2,\ D:2\). First merge \(A\) and \(B\), producing a node \(X\) of weight \(1+1=2\). There are now three available nodes of weight \(2\): \(X\), \(C\), and \(D\).
Choice 1: Merge \(X\) with \(C\), producing \(Y\) of weight \(2+2=4\). Merge \(D\) with \(Y\), producing a root of weight \(2+4=6\). Put \(D\) on the left of the root and \(Y\) on the right; within \(Y\), put \(X\) on the left and \(C\) on the right; within \(X\), put \(A\) on the left and \(B\) on the right. The codewords are \(D=0,\ A=100,\ B=101,\ C=11\). The cost is \(2\cdot1+1\cdot3+1\cdot3+2\cdot2=2+3+3+4=12\).
Choice 2: Instead, merge \(C\) and \(D\), producing a node \(Z\) of weight \(2+2=4\). Merge \(X\) and \(Z\), producing a root of weight \(2+4=6\). Put \(X\) on the left and \(Z\) on the right, with \(A,B\) as the left and right children of \(X\), and \(C,D\) as the left and right children of \(Z\). The codewords are \(A=00,\ B=01,\ C=10,\ D=11\). The cost is \(1\cdot2+1\cdot2+2\cdot2+2\cdot2=2+2+4+4=12\).
Check: Both constructions combine two available nodes of minimum weight at every step. Their codewords differ, but each has cost \(12\). The merge-weight check gives \(2+4+6=12\) for either construction. The differing lengths in the first construction are balanced by the frequencies: its less frequent \(A\) and \(B\) have longer codewords than \(D\).
Encoding and Decoding Conventions
Worked Example: Decode and Reverse the Bit Convention
Return to the six-symbol tree, where \(B=101\), \(E=1101\), and \(A=0\). To decode \(10111010\), start at the root and read until reaching a leaf. The first three bits follow right, left, right, reaching \(B\); reset to the root. The next four bits follow right, right, left, right, reaching \(E\); reset again. The final bit \(0\) reaches \(A\). Thus the decoding is \(B,E,A\), with the grouping \(101|1101|0\).
Now reverse the convention, using \(1\) for a left edge and \(0\) for a right edge, while leaving the tree itself unchanged. Each codeword is bitwise complemented: \(A=1,\ B=010,\ C=011,\ D=000,\ E=0010,\ F=0011\). Under this convention, the message \(B,E,A\) is \(010|0010|1=01000101\). Decoding with the reversed convention follows \(010\) to \(B\), \(0010\) to \(E\), and \(1\) to \(A\). The tree's leaf paths have not changed; only the labels assigned to the two edge directions have changed.
Check: The first encoding of \(B,E,A\) has \(3+4+1=8\) bits. The reversed-convention encoding has \(3+4+1=8\) bits as well. A receiver must use the same convention as the sender: for instance, reading the first bit \(0\) of the original code for \(A\) as a right edge under the reversed convention moves to an internal vertex, not to the leaf \(A\).
Common Errors to Avoid
Assuming a tie forces a unique code. In the four-symbol example, one valid code assigns \(A=100\), while another assigns \(A=00\). These are not conflicting answers: the tied minimum weights permit different merge choices. Check that each step merged two minimum-weight nodes, then calculate the cost for the tree actually constructed.
Reading internal weights as code symbols. In the six-symbol tree, the root's weight is \(100\), but \(100\) is not a codeword for a symbol. It is the sum of the leaf frequencies below the root. Codewords belong to leaves; internal labels help track the merges.
Changing the bit convention on only one side. The convention determines how a path becomes a bit string. If the tree uses left \(=0\) and right \(=1\), replacing one codeword by its complemented version without changing the receiver's convention will generally lead to different paths. State the convention before encoding or decoding, and use it consistently.
Forgetting the one-symbol case. The construction described here assumes at least two symbols. With one symbol, the tree consists of a single leaf and the root-to-leaf path has length zero. Some applications assign that symbol the one-bit code \(0\) so that repetitions can be represented in a bit stream; that is an additional convention, not a merge produced by the algorithm.
Check Your Understanding
For each question, state any left/right bit convention you use and show enough intermediate work to verify the result.
- For frequencies \(A:4,\ B:5,\ C:7,\ D:9\), list the Huffman merges and give the weighted bit cost.
- For the first tie-choice tree in the four-symbol example, decode the bit string \(011\).
- Explain why the codewords from a leaf-labelled binary tree are prefix-free.
- For the six-symbol tree, use the internal weights to check its total weighted bit cost.
- Under the reversed convention, give the codeword for \(C\) in the six-symbol example and explain how you obtained it.