PHASE 02 · MODULE 08
Compression.
Compression is prediction: guess what comes next, then spend bits only on the surprise.
Nearly every mainstream codec combines two ideas: repeat removal, which replaces text seen before with a short back-reference, and entropy coding, which gives common symbols short codes and rare ones long codes. Choosing a codec is then arithmetic: minimise compress time plus transfer time plus decompress time, across everyone who reads the data.
Start lesson 1Basics
- Lossless and lossy
- Shannon entropy
- Huffman coding
- Run-length encoding
Depth
- LZ77 parsing
- Hash chains
- Window sizing
- Arithmetic coding
- tANS and FSE
- Streaming flush modes
- Why encrypted data does not compress
Current
- Shared dictionaries over HTTP
- zstd at the edge
- Columnar and float compression
- KV-cache compression in inference
Lessons
- 01Entropy: why some data compresses and some never willInformation is surprise. Learn Shannon's measure, why it sets a hard floor on compressed size, and why random and encrypted data cannot be shrunk at all.
- 02Entropy coding: Huffman, arithmetic coding and ANSTurn probabilities into bits. Build a Huffman code by hand, see where its one-bit minimum wastes space, and learn how arithmetic coding and ANS spend fractions of a bit.
- 03LZ77: replacing repeats with back-referencesMost real data repeats itself. LZ77 replaces a repeat with “copy n bytes from d back”. Learn the parse, the window, and how DEFLATE and zstd combine it with entropy coding.
- 04Choosing a codec: gzip, Brotli, zstd, LZ4 or XZEvery codec trades ratio against speed. Learn the decision rule, compress time plus transfer time plus decompress time across all readers, and apply it to APIs, assets and storage.
- 05Dictionaries: compressing small messagesA 300-byte message barely compresses alone, because the codec has no history. Give it a trained dictionary and it does. Then see how HTTP now uses the previous response as the dictionary for the next.
- 06Length oracles, context compaction and KV cachesCompression leaks information through size, and that broke HTTPS twice. Then the agent view: compaction is lossy compression of context, prompt caching is not compression at all, and inference servers compress their caches.
Module lab
- Implement Huffman coding and a toy LZ77 in about 200 lines.
- Run
zstd -b1 -e19on your own data and plot ratio against speed. - Train a dictionary on real tool results and measure the gain.
- Reproduce a length oracle in a small script, then defeat it with per-response masking.
Interview questions
gzip, Brotli or zstd for a dynamic API?
Argue from CPU per request and client support.
Why LZ4 in one layer and zstd in another?
Hot paths want speed, cold storage wants ratio.
How can compression leak a secret?
Walk through a length oracle: attacker-controlled text that matches the secret compresses smaller.
Read
- RFC 1951: DEFLATE
- RFC 7932: Brotli
- RFC 8878: Zstandard
- Yann Collet's Finite State Entropy blog posts
- Data Compression Explained, Matt Mahoney