Huffman coding
What is Huffman Coding?
Huffman coding is a lossless compression technique that reduces file size by assigning shorter binary codes to frequently occurring characters and longer codes to rarely occurring ones. In standard fixed-length encoding, every character uses the same number of bits regardless of how often it appears. Huffman coding replaces this with variable-length codes tailored to the actual frequency pattern of the data.
Because frequent characters appear many times in the file, even a small reduction in their code length produces a large overall saving. The original data can always be reconstructed exactly - no information is lost.
Building, Reading, and Decoding a Huffman Tree
A Huffman tree is a binary tree that defines the variable-length code for every character. Three skills are needed: building the tree from frequency data, reading a character's code by tracing a path through it, and decoding a compressed bit stream back into the original text.
Worked Example: Compressing "banana"
The word "banana" contains six characters but only three distinct letters. Count the frequency of each:
| Character | Frequency |
|---|---|
| a | 3 |
| n | 2 |
| b | 1 |
The Huffman algorithm repeatedly combines the two nodes with the lowest frequency into a new parent node:
- Sort by frequency: b(1), n(2), a(3).
- Combine lowest two: b(1) + n(2) → new node bn(3). Resort: a(3), bn(3).
Note: a and bn are now tied at frequency 3. Either can go left or right - both produce a valid tree with the same total bits. - Combine remaining two: a(3) + bn(3) → root(6). Tree complete.
Codes read root to leaf: a = 0, n = 10, b = 11
Encoding "banana": b=11, a=0, n=10, a=0, n=10, a=0 → 110100100 (9 bits).
| Method | Bits per character | Total bits |
|---|---|---|
| Fixed-length | 2 (for 3 characters) | 6 × 2 = 12 bits |
| Huffman | Variable (1, 2, or 2) | 9 bits |
Huffman coding saves 3 bits - a 25% reduction - simply because the most frequent character (a) gets a 1-bit code.
The word contains m(1), p(2), i(4), s(4) across 11 characters. Four distinct characters means three merge steps and at least one tiebreaking decision. Build the Huffman tree, find each character's code, and calculate the total bits. How does the saving compare to "banana"? Why is it so much smaller?
Reading Codes from the Tree
To find the code for any character: trace the path from the root to that character's leaf node. At every branch, going left adds a 0 and going right adds a 1. The full sequence of bits along the path is the Huffman code.
The worked tree below uses four characters to illustrate the interpretation process clearly, including a deeper three-level path:
Left = 0, right = 1. Trace root to leaf to read each code.
| Char | Freq | Code | Code length | Total bits |
|---|---|---|---|---|
| A | 6 | 0 | 1 | 6 × 1 = 6 |
| B | 3 | 10 | 2 | 3 × 2 = 6 |
| C | 2 | 110 | 3 | 2 × 3 = 6 |
| D | 1 | 111 | 3 | 1 × 3 = 3 |
| Huffman total | 21 bits | |||
| Fixed-length (2 bits × 12) | 24 bits | |||
The Prefix-Free Property
Huffman codes are prefix-free: no code is a prefix (the beginning) of another code. Because A = 0, no other code can begin with 0 - so B, C, and D all begin with 1. This property guarantees that a decoder can always identify exactly where one character's code ends and the next begins, without needing any separator bits between them.
Decoding "banana" Back from Bits
Using the banana tree (a=0, n=10, b=11), the receiver reads the compressed bit stream 110100100 one bit at a time. At each step they traverse the tree from the root; when they reach a leaf node they output that character and restart from the root.
| Bits read | Tree traversal | Result | Output |
|---|---|---|---|
1 | Root → right (internal bn) | Not a leaf - continue | - |
11 | → right → leaf b | Leaf reached - restart | b |
0 | Root → left → leaf a | Leaf reached - restart | a |
1 | Root → right (internal bn) | Not a leaf - continue | - |
10 | → left → leaf n | Leaf reached - restart | n |
0 | Root → left → leaf a | Leaf reached - restart | a |
1 | Root → right (internal bn) | Not a leaf - continue | - |
10 | → left → leaf n | Leaf reached - restart | n |
0 | Root → left → leaf a | Leaf reached - restart | a |
Decoded message: banana. The prefix-free property ensures no ambiguity at any step - each bit either continues the current path or completes a character, with no backtracking needed.
Key Takeaways
- Huffman coding is lossless: frequent characters get short codes, rare ones get longer codes - total bits are reduced without any data loss.
- The Huffman tree is built bottom-up: repeatedly combine the two nodes with the lowest frequencies until one root remains.
- To read a code: trace root to leaf, adding 0 for left branches and 1 for right branches.
- Huffman codes are prefix-free: no code is a prefix of another, so the decoder can always identify character boundaries without separators.
- To decode: read the bit stream bit by bit, traversing the tree; when a leaf is reached, output the character and restart from the root.
- Savings are greatest when frequency distribution is highly unequal. If frequencies are nearly equal, the benefit over fixed-length encoding is small.