← All Base Form Math projects
BM-26NOT STARTEDBASE FORM · PROBABILITYMATHPYTHON

Text compressor

Build Huffman and arithmetic coding, compress books, and compare yourself with zlib and the entropy limit.

EST.8 h
REWARD+100 XP
AFTERoriginal

ML-ARENA BENCHMARKS

YOUR NUMBER VS THE INDUSTRY'S
METRICINDUSTRYMINE
compressed size
GOAL · within 1% of the entropy bound; report vs zlib
zlib · measured locally—
no results yet
YOUR RESULTS

Your recorded results appear here.

Brief

A compressor is a probability model plus a coder. The model says how likely each symbol is. The coder spends few bits on likely symbols and more on rare ones. In this project you build two coders, Huffman and arithmetic, give them the simplest model (how often each byte appears in the book), and see how close they get to the limit.

That limit is the entropy. If byte ss appears with probability psp_s, the entropy is H=−∑spslog⁡2psH = -\sum_s p_s \log_2 p_s bits per byte, and a book of nn bytes needs at least nHnH bits with this model. English text comes out at roughly 4.5 bits per byte, a bit more than half of the 8 it is stored in. Huffman gives each byte a whole number of bits, so its average length LL satisfies H≤L<H+1H \le L \lt H + 1. Arithmetic coding avoids that rounding and gets within a few bits of nHnH for the whole file.

zlib will still win. It does not assume each byte is independent: it finds repeated strings and refers back to them. The entropy bound you compute is only a bound for your model. A better model, one that uses context, has a lower bound. That gap is the main lesson of the project.

VISUALFig. 1
interval [0, 1); next symbol B A 0 B 0.5 C 0.8 1 interval [0.5, 0.8); next symbol A A 0.5 B 0.65 C 0.74 0.8 interval [0.5, 0.65); next symbol C A 0.5 B 0.575 C 0.62 0.65 "BAC" → [0.62, 0.65), width 0.03 ≈ 5.1 bits
Arithmetic coding of BAC with P(A) = 0.5, P(B) = 0.3, P(C) = 0.2. Each symbol keeps its slice of the current interval. The final width is the message's probability, 0.03, which costs about 5.1 bits. Why it's here: Arithmetic coding is hard to picture from code; the shrinking interval is the whole idea.
HINT · OBJECTIVE 2
Stuck? Hints stay hidden until you ask.
HINT · OBJECTIVE 4
Stuck? Hints stay hidden until you ask.

DATA · Project Gutenberg books

Objectives

0 / 5 CLEARED

Read-only. Log in to update progress.

VICTORY CONDITIONS

  1. The arithmetic-coded payload, not counting the header, is within 1% of n·H for every book. Record the worst ratio with `python tools/mlarena.py record BM-26 "<payload / bound>"`.
  2. Decoding gives back the exact original bytes for every file.
  3. The comparison table includes zlib at level 9 and a paragraph on why it does better than your order-0 bound.

Side quests

Make the model adaptive and condition on the previous two bytes. Watch your coder beat zlib.
Compress book B with the counts from book A. Measure the extra bits and check they equal the KL divergence between the two distributions.
Add lzma and bz2 from the standard library to the table.

Terms in plain words

Entropy
The average surprise of a source, H = −Σ p log₂ p bits per symbol. No lossless code that uses the same probabilities can average fewer bits.
Prefix code
A code where no codeword is the start of another, so a stream of bits can be decoded without separators.
Huffman coding
Builds the best prefix code by repeatedly merging the two least frequent symbols into one node of a tree.
Arithmetic coding
Encodes a whole message as one number inside an interval that shrinks with each symbol, so symbols can cost fractions of a bit.
Cross-entropy
The average bits per symbol when data from distribution p is coded with a code built for q. It is never less than the entropy of p.