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

  1. Count the occurrences of each character in the text → list of symbols with their frequencies.
  2. Sort the list by decreasing number of occurrences.
  3. 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.
  4. Continue until only one node is left — the root.
  5. Read the codes from root to leaves: 0 for a left arc, 1 for a right arc.

Worked example – phases 1 & 2 (838 characters)

CharETAOINSRHLDCU
Occ.125938076737165615541403127

Worked example – phases 3 & 4 (merges)

StepTwo smallestNew nodeRemaining list (sorted)
1C 31 + U 2758125 93 80 76 73 71 65 61 58 55 41 40
2D 40 + L 4181125 93 81 80 76 73 71 65 61 58 55
3H 55 + (CU) 58113125 113 93 81 80 76 73 71 65 61
4R 61 + S 65126126 125 113 93 81 80 76 73 71
5N 71 + I 73144144 126 125 113 93 81 80 76
6O 76 + A 80156156 144 126 125 113 93 81
7(DL) 81 + T 93174174 156 144 126 125 113
8113 + E 125238238 174 156 144 126
9126 + 144270270 238 174 156
10156 + 174330330 270 238
11238 + 270508508 330
12330 + 508838 (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)

CharOcc.CodeBits
E1251103
T930113
A800003
O760013
I7310114
N7110104
S6510014
R6110004
H5511114
L4101014
D4001004
C31111005
U27111015

⚠️ 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 readPathLeaf reached
0 1 1838 → 330 → 174 → TT
1 1 0838 → 508 → 238 → EE
1 0 1 0838 → 508 → 270 → 144 → NN

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.