1. Introduction
Definition – Huffman code
A variable-length code for compressing information, proposed by David Huffman in 1952. Instead of storing every character on 8 bits (ASCII), frequent characters get short codes and rare characters get longer ones. On average this reduces the file size (often to about half).
- Used e.g. inside JPEG compression (WinZip uses a different algorithm).
2. Huffman Coding Algorithm
The 5 phases
- Count the occurrences of each character in the text → list of symbols with their frequencies.
- Sort the list by decreasing number of occurrences.
- Build a binary tree (the Huffman tree): each character is a leaf whose weight is its number of occurrences. Repeatedly take the two lowest weights and join them under a new internal node whose weight is the sum of its children.
- Continue until only one node is left — the root.
- Read the codes from root to leaves: 0 for a left arc, 1 for a right arc.
Worked example – phases 1 & 2 (838 characters)
| Char | E | T | A | O | I | N | S | R | H | L | D | C | U |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Occ. | 125 | 93 | 80 | 76 | 73 | 71 | 65 | 61 | 55 | 41 | 40 | 31 | 27 |
Worked example – phases 3 & 4 (merges)
| Step | Two smallest | New node | Remaining list (sorted) |
|---|---|---|---|
| 1 | C 31 + U 27 | 58 | 125 93 80 76 73 71 65 61 58 55 41 40 |
| 2 | D 40 + L 41 | 81 | 125 93 81 80 76 73 71 65 61 58 55 |
| 3 | H 55 + (CU) 58 | 113 | 125 113 93 81 80 76 73 71 65 61 |
| 4 | R 61 + S 65 | 126 | 126 125 113 93 81 80 76 73 71 |
| 5 | N 71 + I 73 | 144 | 144 126 125 113 93 81 80 76 |
| 6 | O 76 + A 80 | 156 | 156 144 126 125 113 93 81 |
| 7 | (DL) 81 + T 93 | 174 | 174 156 144 126 125 113 |
| 8 | 113 + E 125 | 238 | 238 174 156 144 126 |
| 9 | 126 + 144 | 270 | 270 238 174 156 |
| 10 | 156 + 174 | 330 | 330 270 238 |
| 11 | 238 + 270 | 508 | 508 330 |
| 12 | 330 + 508 | 838 (root) | – |
flowchart TD R838((838)) -->|0| N330((330)) R838 -->|1| N508((508)) N330 -->|0| N156((156)) N330 -->|1| N174((174)) N156 -->|0| A["A 80"] N156 -->|1| O["O 76"] N174 -->|0| N81((81)) N174 -->|1| T["T 93"] N81 -->|0| D["D 40"] N81 -->|1| L["L 41"] N508 -->|0| N270((270)) N508 -->|1| N238((238)) N270 -->|0| N126((126)) N270 -->|1| N144((144)) N126 -->|0| R["R 61"] N126 -->|1| S["S 65"] N144 -->|0| N["N 71"] N144 -->|1| I["I 73"] N238 -->|0| E["E 125"] N238 -->|1| N113((113)) N113 -->|0| N58((58)) N113 -->|1| H["H 55"] N58 -->|0| C["C 31"] N58 -->|1| U["U 27"]
Worked example – phase 5 (codes)
| Char | Occ. | Code | Bits |
|---|---|---|---|
| E | 125 | 110 | 3 |
| T | 93 | 011 | 3 |
| A | 80 | 000 | 3 |
| O | 76 | 001 | 3 |
| I | 73 | 1011 | 4 |
| N | 71 | 1010 | 4 |
| S | 65 | 1001 | 4 |
| R | 61 | 1000 | 4 |
| H | 55 | 1111 | 4 |
| L | 41 | 0101 | 4 |
| D | 40 | 0100 | 4 |
| C | 31 | 11100 | 5 |
| U | 27 | 11101 | 5 |
⚠️ Which child goes left/right, and how ties are broken, are conventions: different choices give different codes but the same total length (all are optimal). On an exam, follow the convention used in class and keep it consistent.
3. Decoding
Principle
Read the bit string left to right, starting at the root of the Huffman tree: go left on 0, right on 1, until a leaf is reached → output that character, then restart from the root.
Worked example – decode 0111101010
| Bits read | Path | Leaf reached |
|---|---|---|
| 0 1 1 | 838 → 330 → 174 → T | T |
| 1 1 0 | 838 → 508 → 238 → E | E |
| 1 0 1 0 | 838 → 508 → 270 → 144 → N | N |
Message: TEN.
4. Unique Prefix Property
Definition – Unique prefix (prefix-free) code
An encoding has the unique prefix property if no code is the prefix of another code.
This guarantees no ambiguity when decoding: as soon as the last bit of a code is read, the character is known.
Theorem – Huffman codes are prefix-free
In the Huffman tree, characters sit only at leaves, and every proper prefix of a code leads to an internal node. Hence no code can be a prefix of another.
Worked example: H = 1111, so 1, 11, 111 are internal nodes (508, 238, 113) — no letter has those codes.
Counter-example (not prefix-free): codes A = 0, B = 01, C = 1. The string 01 could be “AC” or “B” → ambiguous.
5. Compression Ratio
Definition – Average size per symbol
where = code length of symbol , = its occurrences, = total occurrences.
Definition – Compression ratio
Compression percentage .
Worked example
Grouped: bits.
With 8-bit ASCII originally ( bits):
→ the file is compressed to 45% of its size, i.e. by 55%.
Fixed-length code optimization
A fixed code only needs bits, = number of distinct symbols.
Worked example: 13 symbols → bits → bits. Huffman (3036 bits) still saves compared with this optimized fixed code.
⚠️ The compressed file must also store the tree (or code table) to be decodable; for small files this overhead can cancel the gain.