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
- 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)).
- 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.