r/compression • u/Glittering_Gap_9891 • 1d ago
A "zero-prior" context-mixing compressor
I built UCZ (v0.1.0-beta.1), a personal TypeScript research project, to explore a question: many high-performance compressors—paq8px, zstd with dictionaries, domain-specific tools—rely on built-in world knowledge such as word lists, pretrained weights, magic numbers, or format-specific preprocessors. What if a compressor is strictly forbidden any external prior knowledge and told only that “the input is a raw byte sequence”?
To test this, I defined a “9-Point Constitution” (no built-in dictionaries, pretrained tables, filename/magic-number sniffing, or format-specific preprocessing) and implemented an online context-mixing engine that discovers structure at runtime:
For tabular/vertical-text streams, it learns delimiter density and tracks row/column alignment.
For 2D binary rasters, it searches the decoded prefix for causal scanline autocorrelations—e.g., locking onto the 216-byte scanline structure of the Canterbury ptt5 fax image and reaching 5.25% compression without header parsing.
For multi-channel/periodic signals, it tries de-interleaving with strides s=2–64, plus delta encoding and bit-plane decomposition.
For incompressible inputs (e.g., .png, since it may not re-inflate DEFLATE), an “error-EMA gate” freezes context training and reverts to STORE mode to avoid learning from noise.
To separate “general online learning” from “algorithmic priors,” every structural assumption is documented in PRIOR_REGISTRY.md, and two modes measure their impact.
UCZ --max includes online delimiters/column alignment, stride de-interleaving for s∈[2,64], causal 2D scanline detection, relative jump transforms, and the error-EMA freeze gate:
Canterbury Corpus (11 files): 369,447 B (13.14%; xz -9e: 17.54%)
UCI Tabular Corpus (6 files): 375,359 B (5.73%; xz -9e: 8.80%)
Complete E. coli genome: 1.951 bits/input-byte (~1.990 bits/base)
UCZ --strict / --strict-zero-prior disables ASCII character-class partitioning, relative jump transforms, 2D scan-period detection, and arithmetic delta/gradient specifications; it also tests a random permutation π(X) of the byte alphabet:
Canterbury Corpus: 375,283 B (13.35%; 1.58% higher than --max)
For structured binary data (9.H: +6.3%), tabular floating-point data (+14.5%), and 2D fax rasters (ptt5: +62.5%), these results quantify each structural operator’s gains.
Because the model tracks prequential predictive code cost (−log2 P(x_t|x_<t)) every 512 bytes, I built two utilities:
ucz inspect: a “residual microscope” showing where the online model is surprised—useful for high-entropy pockets in unknown blobs or regime shifts.
ucz ncd: a conditional-complexity dissimilarity matrix that keeps the context table “warm” across file boundaries.
Caveats: it is slow and memory-intensive—the 2.8 MB Canterbury Corpus takes ~105 s and ~1.9 GiB RAM, roughly 100× slower than xz -9e; README lists wall-clock time and peak RSS with each ratio. Even in --strict mode, exact alphabet-bijection invariance C(π(X))=C(X) holds only within an empirical ~3.4% drift, due to 24-bit hash-bucket collisions and APM quantization; details are in CONSTITUTION.md. The codebase (src/lib/codec.ts, coder.ts) evolved over ~37 iterations and is not elegant.
Specialized tools with domain priors still win in their domains (paq8px for English prose, AC2 for proteins, GeCo3 for DNA); documenting this gap was the main objective. If you have unusual binary blobs, telemetry logs, or edge-case files for round-trip integrity tests or the “microscope” tool (npm run bench:quick gives a ~10 s, 6-stream check; a local single-file Web UI via npm run build:web), I welcome bug reports, critiques, and mathematical/code suggestions.(https://github.com/no-nova/UCZ)