From Hello World
to Huffman Coding
How can a computer store the same message with fewer bits—and still know exactly where every symbol ends?
Can we spend fewer bits?
We will start with familiar character storage, discover why arbitrary short codes fail, and build a prefix-free code from a binary tree.
The message stays unchanged. Only its representation changes.
What does a computer store?
For this lesson, use the exact 11-character message Hello World (including the space).
Byte-oriented ASCII
Each character is stored in one 8-bit byte in this simple model.
One character, eight bits
H has ASCII decimal value 72.
ASCII uses 7-bit values; a common storage format places each value in an 8-bit byte.
Each tile represents one character in the message, including the blank space.
Not every symbol appears equally often.
A fixed 8 bits for every character ignores useful patterns in the message.
Frequency table
| Symbol | Frequency | ASCII bits |
|---|
There are 8 distinct byte values in this exact, case-sensitive message.
Give common symbols shorter codes?
A short code table can look compact, but the decoder needs a reliable way to find each symbol boundary.
An ambiguous example
| H | 0 |
| E | 1 |
| O | 11 |
| D | 110 |
Does this mean O + H, or D?
The prefix problem
11 is the beginning of 110.
Without extra separators, a decoder cannot know when to stop reading one code and start the next.
Put every symbol at a leaf.
In a binary tree, label left edges 0 and right edges 1. A symbol’s code is the path from the root to its leaf.
Why decoding works
You only emit a symbol when you reach a leaf. No leaf can sit halfway along another symbol’s path.
The tree shape determines code lengths; leaf labels determine which symbols use them.
Merge the two lightest trees.
Repeatedly combine the two lowest frequencies. Their parent gets the sum. This greedy process builds an optimal prefix code.
Start with one leaf per symbol
Each leaf stores a character and its frequency. Press Next Merge to build the tree.
The tree becomes a codebook.
Frequent symbols tend to sit closer to the root. Their paths use fewer bits.
Huffman codebook
| Symbol | Count | Code | Bits used |
|---|
Tied frequencies can swap left/right or merge order. Codes may differ, while the minimum total length stays the same.
The bitstream is grouped by character below for readability. Real compressed data is stored as a continuous sequence of bits.
Same message. Fewer bits.
For this exact message and a valid Huffman tree, the encoded length is the sum of frequency × code length.
Storage comparison
63.6% fewer bits in this small example.
No information lostPrefix-freeWhat makes the code good?
Frequent symbols get short paths.
Rare symbols can get longer paths.
The weighted path length (WPL) is the sum of each leaf’s frequency multiplied by its depth. Huffman’s greedy merges minimize this sum.
Questions for the room: What if every symbol appeared equally often? What information must a file keep so another computer can decode it?