← All Cracked Math projects
PM-I09NOT STARTEDINTERMEDIATEMATHPYTHONIMPACT ★★☆☆☆

Arithmetic coding: land within 0.1% of the entropy you predicted

Compression is prediction: make the bits on disk match your model's cross-entropy.

EST.14 h
REWARD+300 XP
AFTERMatt Mahoney

ML-ARENA BENCHMARKS

PROOF: BENCH
METRICINDUSTRYMINE
Compressed bytes on enwik7; overhead = (actual bits - model cross-entropy)
GOAL · Coder overhead < 0.1% of the model cross-entropy; the blended order-3 model beats bzip2 -9 on enwik7; lossless round trip verified by SHA-256 (a file fingerprint, so the decoded output must match the input exactly)
gzip -9 / bzip2 -9 / xz -9 on the same file · measured locally (LTCB, the Large Text Compression Benchmark, full-enwik8 reference: gzip 36,445,248; bzip2 29,008,736; xz 24,703,772 bytes)—
no results yet
YOUR RESULTS

Your recorded results appear here.

Brief

An arithmetic coder turns a model's probabilities into bits: a symbol with probability p costs about -log2(p) bits, so a better predictor gives a smaller file. Implement a 32-bit integer range/arithmetic coder (encoder and decoder, with a bit-exact round trip) driven by adaptive order-0 to order-3 context models (an order-k model predicts the next byte from the previous k bytes). Combine the orders using escape/blending: fall back to a shorter context when the long one has not been seen before, or mix the predictions of several orders. Run it on enwik7, the first 10^7 bytes of enwik8 (a Wikipedia dump used as a compression benchmark). Report the achieved size next to the model's own cross-entropy (the total bits the model's probabilities imply), so that coder overhead and model quality are measured separately.

VICTORY CONDITIONS

  1. Coder overhead < 0.1% of the model cross-entropy; the blended order-3 model beats bzip2 -9 on enwik7; lossless round trip verified by SHA-256 (a file fingerprint, so the decoded output must match the input exactly) (Compressed bytes on enwik7; overhead = (actual bits - model cross-entropy)).
  2. A public repository with a README that shows your result and how to reproduce it.

Terms in plain words

Arithmetic coding
A compression method that encodes a whole message as one number in an interval, spending almost exactly -log2(p) bits per symbol.
Cross-entropy
The average number of bits per symbol a model's probabilities imply for the actual data; the ideal size of the compressed file.
Order-k context model
A model that predicts the next byte from counts of what followed the previous k bytes.
Escape / blending
Ways to handle contexts with few counts: escape to a shorter context, or mix predictions from several context lengths.
Coder overhead
The extra bits the coder spends beyond the model's cross-entropy, caused by finite-precision arithmetic.

Why it rates ★★☆☆☆

Good information-theory grounding. Beating bzip2 is not news, but it sets up W04.