1What is lossless compression?
Compression stores data in less space by exploiting patterns. Lossless compression guarantees that decoding gives back the original bytes exactly, which is what you need for documents, source code, databases and executables. Lossy compression (a typical JPEG photo or MP3) throws away detail people are unlikely to notice.
BANANA6 bytes = 48 bits1101001009 bits + codebookBANANAidentical bytes- Bit
- A single 0 or 1.
- Byte
- Eight bits; one ASCII letter.
- Encoder / decoder
- The programs that compress and restore data. Together they form a codec.
- MiB
- 1,048,576 bytes (220).
We use the word BANANA throughout because it contains both patterns this tutorial explores:
Some letters are more common
A appears 3 times, N twice, B once. Entropy coding gives frequent symbols shorter codes.
A: 3 N: 2 B: 1
Some sequences repeat
ANA appears twice. Dictionary coding replaces a repeat with a pointer to earlier data.
BANANA → BANANA
2Entropy: the limit for symbol-by-symbol coding
Shannon's entropy measures the average information per symbol under a probability model. If symbol s has probability ps, then
H = − Σs ps · log2 ps bits per symbol.
No lossless code that assigns a whole number of bits to each symbol independently can average fewer than H bits per symbol, and Huffman's code is within 1 bit of it. For BANANA, with p(A)=1/2, p(N)=1/3, p(B)=1/6:
H = ½·1 + ⅓·log23 + ⅙·log26 ≈ 0.500 + 0.528 + 0.431 ≈ 1.46 bits/symbol
| Representation | Bits | Bits/symbol |
|---|---|---|
| ASCII bytes | 48 | 8.00 |
| Fixed 2-bit code | 12 | 2.00 |
| Huffman code | 9 | 1.50 |
| Entropy bound (6·H) | ≈ 8.75 | 1.46 |
3Huffman coding with a min-heap
Huffman's algorithm (1952) builds an optimal prefix code: no codeword is the start of another, so the decoder can read bits until it reaches a leaf of the code tree and then start again at the root.
- Count how often each symbol occurs (one pass over the input, O(n)).
- Put one leaf per distinct symbol into a min-heap keyed by count.
- Repeatedly pop the two lightest nodes, make them children of a new node whose weight is their sum, and push it back.
- When one node remains it is the root. Label edges 0/1; a symbol's code is the path from the root.
function BuildHuffman(text):
freq ← count of each symbol in text // O(n)
heap ← empty min-heap ordered by (weight, id)
for each symbol s in freq: heap.push(Leaf(s, freq[s])) // k pushes
while heap.size > 1: // k − 1 merges
x ← heap.pop(); y ← heap.pop() // O(log k) each
heap.push(Node(weight = x.w + y.w, children = x, y))
return heap.pop() // root
function AssignCodes(node, prefix, table):
if node is a leaf: table[node.symbol] ← prefix (or "0" if prefix is empty)
else:
AssignCodes(node.child0, prefix + "0", table)
AssignCodes(node.child1, prefix + "1", table)
Child-order convention used here and in our slides: the heavier child of each merge gets bit 0; on a tie, the node popped first gets bit 0. Any consistent choice yields an optimal code of the same length; this one gives A=0, N=10, B=11.
Try it: step through the heap
Heap array
Heap as a tree
Code tree
4LZ77: sliding-window matches
LZ77 (Ziv & Lempel, 1977) keeps a window of recently processed data. When the upcoming bytes already appeared in the window, it emits a (length, distance) pair meaning "go back distance bytes and copy length bytes". Otherwise it emits a literal byte.
For BANANA the encoder emits B, A, N, then copy(length=3, distance=2). The distance (2) is shorter than the length (3): the copy overlaps the bytes it is writing, so the third copied byte reads the A written by the first. This is legal as long as the decoder copies one byte at a time, front to back.
Like DEFLATE, we use the LZSS-style variant: literals and matches are separate tokens. The original 1977 paper emitted (offset, length, next-character) triples.
function Lz77Decode(tokens):
out ← empty byte array
for each token in tokens:
if token is Literal(b): out.append(b)
else: // Match(length, distance)
if distance = 0 or distance > out.length: error "invalid distance"
start ← out.length − distance
for i ← 0 to length − 1: // byte by byte, so overlaps work
out.append(out[start + i])
return out
Try it: watch the decoder copy
Encoder output
byte being read byte being written
Demo encoder: greedy longest match, minimum length 3, window 32 bytes, nearest match on ties.
Finding matches fast: hash chains
Scanning the whole window at every position costs O(W·L) comparisons per search (W = window size, L = maximum match length). Real compressors such as zlib instead hash the next 3 bytes and keep, for each hash bucket, a chain of earlier positions with that hash, newest first. The encoder walks only that chain, checks the actual bytes (different strings can share a hash), and stops after C candidates.
0: ABX3: ABY6: ABZ9: ABXQ ← current
- Bucket headpoints to newest
- 6 · ABZcollision: skip
- 3 · ABYcollision: skip
- 0 · ABXmatch, length 3
This makes each search O(C·L) instead of O(W·L). For DEFLATE the window is 32 KiB and the maximum match is 258 bytes; zlib's default level visits at most 128 candidates, so it inspects a tiny fraction of the window per search. The window plus the hash index take O(W) memory.
5Arithmetic coding and ANS
Huffman must spend a whole number of bits per symbol. When one symbol is very likely (say p = 0.95, which carries only 0.07 bits), that rounding wastes space. Arithmetic coding and asymmetric numeral systems (ANS) encode the whole sequence at once and get arbitrarily close to the entropy. Both examples below use P(A) = 0.75 and P(B) = 0.25.
Arithmetic coding
Start with the interval [0, 1). Each symbol shrinks it to the sub-interval matching its probability. Any number inside the final interval identifies the message, provided the decoder knows its length.
"AB": [0, 1) → A → [0, 0.75) → B → [0.5625, 0.75)
The final width is 0.75 × 0.25 = 0.1875, so about −log2 0.1875 ≈ 2.4 bits suffice: the 3-bit binary fraction 0.1012 = 0.625 lies inside.
rANS (range ANS)
The whole message lives in one integer state x. With total M and symbol frequency fs starting at slot cs:
encode: x′ = ⌊x / fs⌋ · M + cs + (x mod fs)
decode: slot = x mod M → s; x = fs · ⌊x / M⌋ + slot − cs
With M = 4, f(A) = 3, c(A) = 0, f(B) = 1, c(B) = 3: encoding A from state 5 gives ⌊5/3⌋·4 + 0 + 2 = 6; decoding 6 gives slot 2 → A and state 3·1 + 2 = 5. Real coders also renormalize to keep x bounded. Zstandard's FSE is a table-driven (tANS) variant.
6LZ78 and LZW: growing a phrase dictionary
Instead of pointing back into a window, LZ78 (1978) and its variant LZW (Welch, 1984) build an explicit dictionary of phrases while they read the input. A trie stores it: each phrase is a path from the root, so extending the current match by one symbol is a single child lookup.
LZ78 on BANANA
Emit (index of longest known phrase, next symbol); add that phrase + symbol to the dictionary.
| Output | New entry |
|---|---|
| (0, B) | 1 = B |
| (0, A) | 2 = A |
| (0, N) | 3 = N |
| (2, N) | 4 = AN |
| (2, end) | — |
LZW on BANANA
Start with every single byte in the dictionary (A=65, B=66, N=78); emit only codes; new phrases get 256, 257, …
| Output | New entry |
|---|---|
| 66 (B) | 256 = BA |
| 65 (A) | 257 = AN |
| 78 (N) | 258 = NA |
| 257 (AN) | 259 = ANA |
| 65 (A) | — |
7What the data structures buy
Big O describes how work or memory grows with input size. Here n = input length, k = distinct symbols, W = window size, L = maximum match length, C = candidate cap.
| Task | Without the structure | With the structure | Space |
|---|---|---|---|
| Huffman tree build | Unsorted list, scan for 2 minimums each merge: O(k²) | Binary min-heap: O(k log k) | O(k) |
| Huffman encode / decode | Frequency pass and bit output are O(n) either way; decoding walks the tree one bit at a time (real decoders use lookup tables) | O(k) | |
| LZ77 match search (per position) | Scan the window: O(W·L) | Hash chain capped at C: O(C·L) | O(W) |
| LZ77 whole input | O(n·W·L) | O(n·C·L) | O(W) |
| LZ78 / LZW phrase lookup | Search a list of phrases | Trie: one child lookup per symbol, O(n) total with hashed children | O(dictionary size) |
For byte data, k ≤ 256, so the O(n) counting pass dominates and the heap matters less. It matters for larger alphabets, such as DEFLATE's 286-symbol literal/length alphabet or word-level coders. For LZ77 the gain is large in practice: C (e.g. 128) is far smaller than W (32,768 in DEFLATE).
8Implementation challenges
Huffman bitstream
- The decoder needs the code. Dynamic DEFLATE blocks send only code lengths; both sides rebuild the same canonical codes from them.
- Codes are capped at 15 bits, so very skewed frequencies need length-limiting.
- A bit buffer packs codes across byte boundaries and reads them back.
LZ77 search and copy
- Hash collisions: always verify the bytes at a candidate.
- Cap the chain length; lazy matching checks whether the next position yields a longer match before committing.
- Validate every distance against available history: untrusted input must not read outside the buffer.
- Copy byte-by-byte (or carefully in chunks) so overlapping matches work.
ANS / arithmetic
- The state grows with every symbol; renormalization emits low bits to keep it in range, and the decoder reads them back.
- rANS decodes in reverse order of encoding, so encoders work backward over a block.
- Probabilities must be quantized to integer frequencies summing to M.
9How real formats combine both ideas
Modern formats run a dictionary stage to find matches, then entropy-code the resulting literals, lengths and distances.
| Format | Match stage | Entropy stage | Where you meet it |
|---|---|---|---|
| DEFLATE (gzip, zlib, ZIP, PNG) | LZ77, 32 KiB window | Huffman codes for literals/lengths and distances | .tar.gz archives, HTTP gzip |
| Zstandard | LZ77-style sequences, large windows | Huffman for literals; FSE (tabled ANS) for sequence symbols | .tar.zst, HTTP zstd (window ≤ 8 MB, RFC 9659), Parquet pages |
| Brotli | LZ77 plus a built-in static dictionary of common words | Context-dependent Huffman code selection | HTTP br for text assets |
BANANA as one DEFLATE block
DEFLATE's simplest block type uses fixed Huffman codes defined in RFC 1951, so no code table has to be sent. LZ77 turns BANANA into B, A, N, copy(length=3, distance=2), and each token gets a fixed code:
| Part | Fixed code | With match | Six literals |
|---|---|---|---|
| Block header (final flag + type) | — | 3 | 3 |
| Literals | 8 bits each (values 0–143) | 3 × 8 = 24 | 6 × 8 = 48 |
| Length 3 | code 257, 7 bits | 7 | — |
| Distance 2 | distance code 1, 5 bits | 5 | — |
| End of block | code 256, 7 bits | 7 | 7 |
| Total | 46 bits → 6 bytes | 58 bits → 8 bytes |
The match saves 12 bits, but the block still pads to 6 bytes, the same as the input. Headers and end markers are fixed overhead, so compression only pays off once the input is long enough to repeat itself many times. A gzip file adds another 18 bytes of header and checksum on top.
Which one is "best" depends on the deployment: an archiver cares about footprint and restore throughput, HTTP delivery about bytes transferred and client memory, a cloud data pipeline about storage cost and how fast pages can be re-scanned.
10Our benchmark
We compressed three synthetic inputs (7.2–7.6 MiB each) with the command-line tools, decompressed each five times, and verified that every result reproduced the original bytes exactly (all nine passed).
| Input | gzip −6 | zstd −3 | Brotli q5 |
|---|---|---|---|
| JavaScript (7,542,036 B) | 10.0% · 605 MiB/s · 1.3 MiB | 9.7% · 1,001 MiB/s · 5.2 MiB | 8.4% · 609 MiB/s · 9.9 MiB |
| JSON logs (7,619,603 B) | 10.5% · 1,426 MiB/s · 1.3 MiB | 12.8% · 792 MiB/s · 5.5 MiB | 10.3% · 892 MiB/s · 10.0 MiB |
| Mixed tar (8,007,680 B) | 43.9% · 2,049 MiB/s · 1.3 MiB | 44.6% · 1,267 MiB/s · 6.0 MiB | 43.3% · 551 MiB/s · 10.3 MiB |
What we found, and its limits
- Brotli produced the smallest output on all three inputs, but decoded the mixed archive slowest. Smaller files can cost more to decode.
- zstd decoded the JavaScript fastest; gzip decoded the logs and the archive fastest and used the least memory.
- The mixed tar is about 37% random bytes (3,000,000 of 8,007,680), which no codec can shrink, so all three land near 43–45%.
- Caveats. Inputs are small, so timing includes process start-up and file reading, which favors lightweight binaries. Memory is the peak resident size of the whole decoder process, not just its working buffers. Each codec ran at one level, and the levels are not equivalent. Results are for this test on one Apple Silicon Mac (Apple gzip 479, zstd 1.5.7, Brotli 1.2.0), not general rankings.
11Paper, authors and references
Read the full paper
The review paper (PDF) will be linked here once it is compiled.
Tutorial mirrors
This tutorial is published on each author's site.
- James Abarca
- Cyril Lorenzo
- Andrew Villorente
Individual contributions
References
- C. E. Shannon, "A Mathematical Theory of Communication," Bell System Technical Journal, 1948. doi
- D. A. Huffman, "A Method for the Construction of Minimum-Redundancy Codes," Proc. IRE, 1952. doi
- I. H. Witten, R. M. Neal, J. G. Cleary, "Arithmetic Coding for Data Compression," CACM, 1987. doi
- J. Duda, "Asymmetric Numeral Systems," 2013. arXiv:1311.2540
- J. Ziv, A. Lempel, "A Universal Algorithm for Sequential Data Compression," IEEE Trans. Inf. Theory, 1977. doi
- J. Ziv, A. Lempel, "Compression of Individual Sequences via Variable-Rate Coding," IEEE Trans. Inf. Theory, 1978. doi
- T. A. Welch, "A Technique for High-Performance Data Compression," Computer, 1984. doi
- P. Deutsch, "DEFLATE Compressed Data Format Specification," RFC 1951, 1996. rfc
- P. Deutsch, "GZIP File Format Specification," RFC 1952, 1996. rfc
- Y. Collet, M. Kucherawy (eds.), "Zstandard Compression and the application/zstd Media Type," RFC 8878, 2021. rfc
- J. Alakuijala, Z. Szabadka, "Brotli Compressed Data Format," RFC 7932, 2016. rfc
- "Window Sizing for Zstandard Content Encoding," RFC 9659, 2024. rfc
- GNU tar manual, "Creating and Reading Compressed Archives." gnu.org
- Apache Parquet, "Compression." parquet.apache.org