CV LAB / DATA COMPRESSION
Use arrow keys to navigate01 / 08
A visual lesson · 01

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?

Today’s question

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.

Learning path
BytesFrequencyPrefix-freeGreedy mergingDecode

The message stays unchanged. Only its representation changes.

01 · A message in memory

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.

11 × 8 = 88 bits
8 bits per characterNo compression yet

One character, eight bits

H has ASCII decimal value 72.

01001000

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.

02 · Look for repetition

Not every symbol appears equally often.

A fixed 8 bits for every character ignores useful patterns in the message.

Frequency table

SymbolFrequencyASCII bits
Count it
8 symbols

There are 8 distinct byte values in this exact, case-sensitive message.

The repeated l and o give us a chance to use shorter codes where they matter most.
03 · The tempting shortcut

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

H0
E1
O11
D110
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.

Design rule: no symbol’s code may be the prefix of another symbol’s code.
04 · Make boundaries visible

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.

rootnodenodeABCD010101

Why decoding works

You only emit a symbol when you reach a leaf. No leaf can sit halfway along another symbol’s path.

Prefix-free

The tree shape determines code lengths; leaf labels determine which symbols use them.

05 · Build the Huffman tree

Merge the two lightest trees.

Repeatedly combine the two lowest frequencies. Their parent gets the sum. This greedy process builds an optimal prefix code.

Step 0 of 7

Start with one leaf per symbol

Each leaf stores a character and its frequency. Press Next Merge to build the tree.

06 · Read the paths

The tree becomes a codebook.

Frequent symbols tend to sit closer to the root. Their paths use fewer bits.

Huffman codebook

SymbolCountCodeBits used

Tied frequencies can swap left/right or merge order. Codes may differ, while the minimum total length stays the same.

Encode the message

The bitstream is grouped by character below for readability. Real compressed data is stored as a continuous sequence of bits.

Press Encode to reveal the bitstream.

07 · Compare and reflect

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

Byte ASCII88 bits
Huffman32 bits

63.6% fewer bits in this small example.

No information lostPrefix-free

What 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.

Compression saves space when symbol frequencies are uneven. Real image and file formats also use other techniques, often before entropy coding.

Questions for the room: What if every symbol appeared equally often? What information must a file keep so another computer can decode it?