cmix-lite — a small context-mixing compressor

A from-scratch C++ context-mixing compressor with binary arithmetic coding and adaptive logistic mixing across multiple order-N + sparse + word context models.

This is a simplified cousin of the paq8/cmix family of compressors that hold the Hutter Prize records on enwik9. The goal: a single .cpp file (~400 LoC) that beats xz -9e and brotli -q11 on Wikipedia text without LSTMs, transformers, or any of the heavy machinery cmix uses.

Results

Tested on Wikipedia text from Matt Mahoney's large text compression benchmark, on a 2017 Dell Inspiron 7577 (Intel i7-7700HQ, 16 GB RAM, dual-channel DDR4).

enwik6 (1 MB)

Compressor	size	bpb	speed
gzip -9	371 KB	2.831	0.4 s
xz -9e	303 KB	2.310	0.4 s
brotli -q 11	293 KB	2.236	~3 s
cmix_lite v1	287 KB	2.189	4 s
cmix_lite v2	273 KB	2.080	5 s

enwik7 (10 MB)

Compressor	size	bpb	speed
gzip -9	3.86 MB	2.947	0.8 s
xz -9e	2.84 MB	2.169	8 s
brotli -q 11	2.83 MB	2.157	~30 s
cmix_lite v1	2.69 MB	2.080	25 s
cmix_lite v2	2.61 MB	1.989	34 s

enwik8 (100 MB)

Compressor	size	bpb	speed
gzip -9	36.5 MB	2.918	7 s
brotli -q 11	25.7 MB	2.059	~3 min
xz -9e	24.8 MB	1.987	105 s
cmix_lite v1	25.2 MB	2.016	212 s
cmix_lite v2	24.0 MB	1.922	372 s
cmix v18 (reference)	~14.7 MB	~1.18	days
NNCP (Bellard)	~13.1 MB	~1.05	hours
fast-cmix (SOTA 2024)	~10.7 MB	~0.86	days

Summary

• cmix_lite v2 beats xz -9e and brotli -q11 on every test file.
• On enwik6 we're 10 % smaller than xz.
• On enwik7 we're 8 % smaller than xz.
• On enwik8 we're 3 % smaller than xz (~800 KB difference on 100 MB).
• Hutter-prize SOTA (~0.86 bpb) is still ~2× more compression than us.

Architecture

   raw byte stream
        │
        ▼
   For each byte, encode as 8 bits MSB-first.
   For each bit:
       ┌─────────────────────────────────────────────────┐
       │  v2 model bank (10 inputs to mixer):            │
       │   1. order-0 (no context)                       │
       │   2. order-1 (last byte)                        │
       │   3. order-2 (last 2 bytes)                     │
       │   4. order-3 (last 3 bytes, hashed)             │
       │   5. order-5 (last 5 bytes, hashed)             │
       │   6. order-8 (last 8 bytes, hashed)             │
       │   7. sparse-2 (byte at offset -2)               │
       │   8. sparse-3 (byte at offset -3)               │
       │   9. sparse-5 (byte at offset -5)               │
       │  10. word context (running hash of letters)     │
       │  Each gives P(bit=0) by counting bytes          │
       │  consistent with the prefix.                    │
       └────────────────────┬────────────────────────────┘
                            │
        ┌───────────────────┼───────────────────┐
        │ Logistic mixer (paq-style):           │
        │   s = Σ wᵢ · stretch(pᵢ)              │
        │   p = squash(s)                       │
        │   Online gradient-descent on log-loss │
        └───────────────────┬───────────────────┘
                            │
                            ▼
                 Binary arithmetic coder
                            │
                            ▼
                     compressed bitstream

After encoding each bit, the actual bit value is fed back to update both the context-model byte counters and the mixer weights. No offline training, no parameter tuning per file, no preprocessing -- single pass, fully online.

Build

clang++ -O3 -std=c++17 -o cmix_lite cmix_lite.cpp     # v1, simpler
clang++ -O3 -std=c++17 -o cmix_v2   cmix_v2.cpp       # v2, with sparse + word

Or with MSVC:

cl /O2 /std:c++17 /EHsc cmix_lite.cpp
cl /O2 /std:c++17 /EHsc cmix_v2.cpp

Usage

./cmix_v2 c input.txt input.cm     # compress
./cmix_v2 d input.cm output.txt    # decompress

Memory use

Model	bits per slot	slots	size
order-0 (direct)	16	256	0.5 KB
order-1 (direct)	16	65536	128 KB
order-2 (direct)	16	16777216	32 MB
order-3 hash	16	1048576	512 MB
order-5 hash	16	1048576	512 MB
order-8 hash	16	1048576	512 MB
sparse-2 / sparse-3 / sparse-5	16	262144	128 MB each
word hash	16	1048576	512 MB
total v2			~2.5 GB

Reduce the bits argument in the HashModel constructors if you need to fit in less memory; expect a small bpb regression.

Path to state of the art

This implementation reaches ~2.0 bpb on Wikipedia text with very simple techniques. The Hutter Prize record (~0.86 bpb on enwik9) requires substantially more machinery:

1. More context models. cmix uses ~300 distinct context functions including word+context joint contexts, indirect contexts (context = a hash of two contexts), match models, etc.
2. Secondary symbol estimation (SSE). Take the mixer's predicted probability and look it up in a context-conditioned table to refine. Worth ~0.2 bpb.
3. Multi-stage mixing. Several mixers in series, each refining the previous prediction in a different context space.
4. Neural-network predictor. NNCP (2019) replaces the context models with a small transformer trained online on the data being compressed. fast-cmix (2024) combines an LSTM ensemble with classical contexts.
5. Pre-processors. WRT (Word-Replacing Transform) replaces common English words with short codes before compression, gaining ~5 % on text -- this is what cmix does.

A realistic next step from this baseline would be (effort vs. expected gain):

step	est. bpb	est. effort
(done) v1: 6 byte-orders + logistic mix	2.05	--
(done) v2: + sparse-2/3/5 + word context	1.99	hours
add SSE (one stage)	~1.7	hours
add cmix-style match model (find longest exact match)	~1.55	day
add small online-trained LSTM as another mixer input	~1.15	week
swap byte-count predictors for transformer (NNCP-style)	~0.95	weeks
full ensemble á la fast-cmix + WRT	~0.86	months, record territory

Files

• cmix_lite.cpp — minimal C++ compressor (6 inputs)
• cmix_v2.cpp — enhanced C++ compressor (10 inputs, sparse + word)
• compressor.py — slow Python reference (~200× slower; useful for understanding/debugging)
• acoder.py — Python binary arithmetic coder
• test_acoder.py— round-trip tests for the Python coder

Honest disclosure

This was built in a single session as an educational baseline, not a serious record-breaking attempt. The Hutter Prize community has spent years refining cmix; competing with that requires their level of domain knowledge and weeks of CPU time per encode. The numbers above are real and reproducible, but understand the gap to SOTA: roughly 2× more compression (2.0 bpb → 0.86 bpb), 30+ years of incremental research, and large compute budgets.