Data Compression Explained: A Visual Guide to the Whole Book

Source note: This post is an original visual study guide based on Matt Mahoney's book. It paraphrases and organizes the ideas for blog reading. It is not a redistributed copy of the book. Historical benchmark numbers and tool rankings should be read in the context of the source's 2013 update.

The Whole Book in One Picture

flowchart LR
    A[Raw data] --> B{Can we expose structure?}
    B -->|Yes| C[Transform]
    B -->|No| D[Model]
    C --> D[Model predicts what comes next]
    D --> E[Coder maps probability to bits]
    E --> F[Archive or stream]
    F --> G[Decoder]
    G --> H[Inverse transform]
    H --> I[Original data or acceptable approximation]

    J[Benchmarks] -. measure .-> C
    J -. measure .-> D
    J -. measure .-> E
    K[Human perception] -. lossy path .-> B

Compression looks like file shrinkage, but the book frames it as a deeper engineering problem:

The shortest honest summary:

Compression is the search for shorter descriptions. Coding is mostly solved. Modeling is the hard part. Transforms make modeling easier. Lossy compression adds a model of human perception.

Fast Mental Models

1. Bits Measure Surprise

If an event has probability p, the ideal code length is:

ideal bits = log2(1 / p) = -log2(p)

Visual rule:

common symbol     -> short code
rare symbol       -> long code
unknown pattern   -> expensive code
understood pattern -> tiny description

2. Compression Is Prediction

flowchart TD
    H[History already decoded] --> M[Model]
    M --> P[Probability for next bit or symbol]
    P --> C[Coder]
    C --> O[Compressed output]
    O --> D[Decoder repeats same model]
    D --> H2[Recovered next bit or symbol]

The compressor and decompressor must make the same predictions from the same history. The compressed file mainly stores the information that the model could not predict.

3. Lossy Compression Is Perception-Aware Prediction

Lossless: recover exactly the same bits.
Lossy: recover something humans judge close enough.

That one change moves the problem from pure information theory into psychology, vision, hearing, language, and AI.

Chapter Map

1. Information Theory

Compression Starts with a Count

There are 2^n different binary strings of length n. There are fewer than 2^n shorter binary strings. Therefore, no lossless compressor can make every n-bit input shorter while still allowing perfect decompression.

All n-bit inputs:

[000...000] [000...001] [000...010] ... [111...111]
       count = 2^n

Possible shorter outputs:

[] [0] [1] [00] [01] ... [length < n]
       count = 2^n - 1

One-to-one decoding cannot map more inputs into fewer outputs.

The key result:

Why Meaningful Data Compresses

Most possible strings are random. Most strings people store are not:

Compression works because our data is not drawn uniformly from all possible bit strings. It comes from processes with structure.

Coding Is Bounded

If a model says a symbol has probability p, the best possible code length is approximately -log2(p) bits. You can choose a bad coder and waste bits, but no coder can beat the model's information content for all data drawn from that model.

flowchart LR
    A[Model says symbol is likely] --> B[Short code]
    C[Model says symbol is rare] --> D[Long code]
    E[Model is wrong] --> F[Compressed size penalty]

The lesson is subtle:

Modeling Is Not Computable

A better model can turn a long string into a tiny description. For example, a million digits of pi can be treated as random-looking decimal digits, or as "compute the first million digits of pi." The second description is dramatically shorter, but it requires recognizing the source.

weak model:
314159265358979323846...
-> "digits look independent"
-> many bits

strong model:
314159265358979323846...
-> "this is pi"
-> short program or description

The book connects this to Kolmogorov complexity: the shortest program that outputs a string is an ideal compressed representation, but there is no general algorithm that can always find it.

Compression and AI

Prediction is a sign of understanding:

This is why compression and AI meet. A compressor that understands a data source can describe it more compactly. A perfect general compressor would need a very broad kind of understanding.

Chapter 1 Takeaways

2. Benchmarks

What Benchmarks Actually Measure

Compression benchmarks compare compressors on a chosen data set under chosen rules.

flowchart TD
    A[Benchmark] --> B[Data set]
    A --> C[Rules]
    A --> D[Metrics]
    D --> E[Compressed size]
    D --> F[Compression speed]
    D --> G[Decompression speed]
    D --> H[Memory use]
    C --> I[Can include decompressor?]
    C --> J[Can tune to files?]
    C --> K[Single file or archive?]

The big triangle:

         smaller output
               /\
              /  \
             /    \
            /      \
           /        \
less memory -------- faster speed

You usually cannot optimize all three at once. Maximum compression tools are often slow and memory-hungry. Practical formats often give up ratio to win speed, streaming, random access, or compatibility.

Bits Per Character

The book often uses bpc, or bits per character, for byte-oriented corpora.

Benchmark Landscape

Why Rankings Shift

Two compressors can trade places when any of these changes:

Visual: Benchmark as a Dashboard

+--------------------------------------------------+
| Compressor: example                              |
+-------------------+------------------------------+
| Size              | 1.95 bpc                     |
| Compression time  | slow                         |
| Decompression     | medium                       |
| Memory            | high                         |
| Decoder included  | yes                          |
| Data set          | text-heavy                   |
| Good use case     | archival / research          |
+-------------------+------------------------------+

Chapter 2 Takeaways

3. Coding

Coder Job Description

A coder receives probabilities from a model and emits bits close to the theoretical ideal.

flowchart LR
    A[Symbol] --> B[Model probability]
    B --> C[Coder]
    C --> D[Bitstream]
    D --> E[Decoder]
    E --> F[Same symbol]

The coder must be:

Huffman Coding

Huffman coding builds a prefix tree. Frequent symbols sit near the root. Rare symbols sit deeper.

    root
   /    \
common   *
        / \
    medium rare

Core idea:

Strengths:

• Simple.
• Fast.
• Widely used.
• Good with static or block models.

Limits:

• Code lengths are whole numbers of bits.
• Binary alphabets cannot be compressed by basic Huffman alone.
• A full table or canonical description may need to be stored.

Arithmetic Coding

Arithmetic coding represents an entire message as a subinterval inside [0, 1).

Initial interval:
[0 ------------------------------------------------ 1)

After likely symbol:
[0 -------- 0.7)

After next symbol:
[0.28 --- 0.42)

After more symbols:
[0.314159 ----------------)

Output a binary number inside the final interval.

Why it matters:

Asymmetric Binary Coding

Asymmetric binary coding is another way to code predicted bits efficiently. It uses a single integer-like state rather than arithmetic coding's interval endpoints. It matters because the same theory can be implemented with different machine-level tradeoffs.

Numeric Codes

Some values are not arbitrary symbols. They are counts, offsets, lengths, or prediction errors. Numeric codes exploit common number distributions.

These appear in systems where the model says "small numbers are common, large numbers are rare."

Archive Formats

A compression algorithm is not the whole file format. Archives also need structure.

flowchart LR
    A[Archive header] --> B[File metadata]
    B --> C[Compressed payload]
    C --> D[Error check]
    D --> E[Optional encryption metadata]

Important archive concerns:

Error Detection

Error detection is not compression, but production archives need it.

Chapter 3 Takeaways

4. Modeling

The Hard Part

A model estimates what comes next. Once we have a good probability, coding is mechanical. The model decides whether compression is mediocre or excellent.

history:  "the quick brown "
model:    next symbol is likely "f", "d", "c", ...
coder:    short code for likely next symbol

Static vs adaptive:

Fixed-Order Models

An order n model predicts the next symbol from the previous n symbols.

Order 0: no context
P(next)

Order 1: one previous symbol
P(next | previous)

Order 3: three previous symbols
P(next | previous_3, previous_2, previous_1)

Example:

Why fixed order breaks:

Bytewise, Bitwise, and Indirect Models

Variable-Order Models

Variable-order models keep statistics for multiple context lengths and choose or mix them.

flowchart TD
    A[Long context] --> B{Seen enough?}
    B -->|Yes| C[Use long-context prediction]
    B -->|No| D[Back off]
    D --> E[Medium context]
    E --> F{Seen enough?}
    F -->|Yes| G[Use medium-context prediction]
    F -->|No| H[Short context]

DMC

Dynamic Markov Coding predicts bits with a state machine that grows as it observes data. It can split states when histories diverge.

Visual:

state A --0--> state B
state A --1--> state C

if state A is too vague:
state A becomes A1 and A2

PPM

Prediction by Partial Matching uses byte contexts and backs off from longer to shorter contexts. It is a classic text-compression idea.

Try context "tion"
if unknown, try "ion"
if unknown, try "on"
if unknown, try "n"
if unknown, try order 0

The hard detail is handling symbols that have not appeared in a context, often called the escape or zero-frequency problem.

CTW

Context Tree Weighting mixes context tree predictions in a principled bitwise way. Instead of choosing only one context, it combines evidence across a tree.

Context Mixing

Context mixing uses many predictors at once.

flowchart LR
    A[Text model] --> M[Mixer]
    B[Match model] --> M
    C[Low-order model] --> M
    D[File-format model] --> M
    E[Image/audio heuristic] --> M
    M --> P[Final probability]
    P --> Coder[Arithmetic coder]

The mixer can learn which predictors are useful in each situation.

Why Context Mixing Can Beat Single Models

Different predictors notice different kinds of structure:

Compression improves when the mixer learns which predictor is trustworthy right now.

Chapter 4 Takeaways

5. Transforms

What a Transform Does

A transform rewrites data so a simpler model can compress it.

flowchart LR
    A[Original data] --> B[Transform]
    B --> C[More model-friendly symbols]
    C --> D[Model]
    D --> E[Coder]
    E --> F[Compressed file]
    F --> G[Decoder]
    G --> H[Inverse transform]
    H --> I[Original data]

Ideal transform:

Run Length Encoding

RLE replaces repeated symbols with a symbol plus a count.

AAAAAABBBBCCCCCCCC

becomes

(A,6) (B,4) (C,8)

Best for:

LZ77 and the Match Family

LZ77 replaces repeated strings with pointers to previous occurrences.

Input:
ABRACADABRA

Later "ABRA" can become:
(go back 7, copy 4)

Visual:

sliding history buffer        lookahead
[ABRACAD]                     [ABRA...]
   ^^^^^
   match reused by pointer

Why it is popular:

LZSS

LZSS improves practical LZ77 by only emitting pointers when they save space. Short non-saving matches remain literals.

Deflate

Deflate combines LZ77-style matches with Huffman coding. It powers common zip/gzip-style compression and survives because it is fast, widely implemented, and compatible.

flowchart LR
    A[Bytes] --> B[LZ77 literals and matches]
    B --> C[Huffman coding]
    C --> D[Deflate bitstream]

LZMA

LZMA pushes stronger modeling around LZ-style matches, often improving ratio at the cost of more CPU and memory.

LZX, ROLZ, LZP, Snappy, Deduplication

LZW and Dictionary Encoding

Dictionary methods replace strings with dictionary references.

dictionary:
1 -> the
2 -> compression
3 -> model

text:
the compression model

encoded:
1 2 3

Dictionary types:

LZW is a dynamic dictionary method historically associated with formats like GIF-era compression. Its broader lesson is that both sides can build the same dictionary without transmitting every entry.

Dictionary Encoding for Text

Text-specific dictionaries can model:

The stronger the text model, the more the compressor behaves like a small language-aware system.

Symbol Ranking and Move-to-Front

Move-to-front keeps a list of symbols ordered by recency. If the same few symbols keep appearing in a context, their ranks stay small.

alphabet list:
[A B C D E ...]

read C -> output rank 2, move C to front
[C A B D E ...]

read C again -> output rank 0

This works well after transforms like BWT, where local neighborhoods tend to reuse a small set of symbols.

Burrows-Wheeler Transform

BWT sorts rotations of a block so characters with similar right contexts cluster together. After BWT, a fast local model can often compress well.

Tiny example, conceptually:

Original block:
banana$

Sort rotations:
$banana
a$banan
ana$ban
anana$b
banana$
na$bana
nana$ba

Take last column:
annb$aa

The output is not obviously shorter, but it groups context-related symbols. It is usually followed by move-to-front, run-length coding, and entropy coding.

flowchart LR
    A[Input block] --> B[BWT context sort]
    B --> C[Move-to-front]
    C --> D[Run-length coding]
    D --> E[Huffman or arithmetic coding]

Predictive Filtering

Numeric data often compresses better as prediction errors.

samples:
100, 103, 105, 106, 108

predict next as previous:
100, +3, +2, +1, +2

Small errors are easier to encode than raw values.

Specialized Transforms

Chapter 5 Takeaways

6. Lossy Compression

The Big Shift

Lossless compression asks:

Can we reproduce the original bits exactly?

Lossy compression asks:

Can we reproduce something humans accept as the same?

That makes perception the model.

flowchart LR
    A[Original signal] --> B[Human perception model]
    B --> C[Discard hard-to-notice detail]
    C --> D[Quantize]
    D --> E[Lossless coding of remaining data]
    E --> F[Compressed media]

Images

Digital images are already approximations of continuous light. Lossy image compression removes detail that the visual system is less sensitive to.

Image Format Map

JPEG as a Visual Pipeline

flowchart LR
    A[RGB pixels] --> B[Color transform]
    B --> C[Chroma subsampling]
    C --> D[8x8 blocks]
    D --> E[DCT frequency transform]
    E --> F[Quantization]
    F --> G[Zigzag ordering]
    G --> H[Run-length and entropy coding]
    H --> I[JPEG file]

Mental picture:

left side of block frequency table  = broad smooth shape
right side of table                 = fine detail

JPEG keeps more of the left side and throws away more of the right side.

Why artifacts happen:

JPEG Recompression

JPEG files are already compressed. Recompressors look for remaining structure:

The chapter surveys historical approaches such as Stuffit, PAQ-based methods, WinZip behavior, and PackJPG. Treat the named results as historical context.

Video

Video compression adds time.

flowchart LR
    A[Frame 1] --> B[Predict frame 2 from frame 1]
    B --> C[Encode motion]
    C --> D[Encode residual error]
    D --> E[Repeat across frames]

Why video compresses:

NTSC and MPEG

Frame types as a mental model:

I-frame: self-contained image
P-frame: predicted from previous frames
B-frame: predicted from past and future reference frames

Tradeoff:

Audio

Audio compression uses psychoacoustics: what the ear can and cannot notice.

Audio pipeline:

flowchart LR
    A[PCM samples] --> B[Frequency analysis]
    B --> C[Psychoacoustic masking model]
    C --> D[Quantization and bit allocation]
    D --> E[Entropy coding]
    E --> F[Compressed audio]

Chapter 6 Takeaways

The Grand Unifying Model

flowchart TD
    A[Data source] --> B{Lossless or lossy?}
    B -->|Lossless| C[Preserve every bit]
    B -->|Lossy| D[Preserve perceptual meaning]
    C --> E{Transform useful?}
    D --> F[Perception transform and quantization]
    F --> E
    E -->|Yes| G[Expose patterns]
    E -->|No| H[Model directly]
    G --> H[Predict next symbol or bit]
    H --> I[Code using probability]
    I --> J[Package with metadata, checks, maybe encryption]

Every concrete compressor can be placed in this frame:

Practical Reading Paths

If You Want to Build a Compressor

If You Want to Choose a Format

If You Want to Understand AI Through Compression

Read Chapter 1 and Chapter 4 together. The essential loop is:

understand pattern -> predict better -> encode surprise only -> shorter file

Compression is not just storage optimization. It is a measurable way to ask how much structure a system has discovered.

Cheat Sheets

Glossary

Algorithm Selection Sketch

Mostly repeated bytes?
-> LZ-style match coding

Mostly text?
-> PPM, context mixing, dictionary transforms, or modern language-aware modeling

Mostly smooth numeric samples?
-> predictive filtering plus entropy coding

Mostly photos?
-> perceptual image codec

Mostly backups or VM images?
-> deduplication plus compression

Already encrypted or compressed?
-> expect little or no gain

Red Flags When Evaluating Compression Claims

Closing

The book's central message is practical and philosophical at the same time:

To compress data, find structure. To find structure, predict. To predict well, understand the source.

That is why the same field contains Huffman trees, probability intervals, dictionaries, suffix sorting, image transforms, psychoacoustics, benchmark politics, and AI. They are all different ways of answering one question:

What is the shortest description that still lets us recover what matters?

Source and Further Reading

• Matt Mahoney, Data Compression Explained, last updated Apr. 15, 2013.
• For current tool rankings, consult up-to-date benchmark leaderboards directly; the rankings in the source are historical.
• For implementation practice, start with a simple RLE or Huffman coder, then build toward adaptive modeling, LZ-style matching, or arithmetic/range coding.