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 appears with probability , the entropy is bits per byte, and a book of bytes needs at least 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 satisfies . Arithmetic coding avoids that rounding and gets within a few bits of 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.
DATA · Project Gutenberg books
Objectives
Read-only. Log in to update progress.
VICTORY CONDITIONS
- 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>"`.
- Decoding gives back the exact original bytes for every file.
- The comparison table includes zlib at level 9 and a paragraph on why it does better than your order-0 bound.
Side quests
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.