Structure-first compression: coding relations instead of values
A compression research line running since 2021, negatives published first: a measured 56% expansion on high-entropy data, an abandoned degenerate variant, and the entropy boundary as a scoping result.
Koch Laboratory — structure-first compression: coding relations instead of values
This direction asks how much compressibility remains in data when, instead of the statistics of values, one encodes their structure: relations between neighbouring bits and the recurrence of small spatial patterns. Classical compression (the LZ family, entropy coding — Huffman, ANS) models the distribution of symbols; this program tests whether a relational representation — the stream as layers of dependencies, a file as a binary image deduplicated against a pattern dictionary — forms a useful, complementary axis. The limit is known from information theory and treated as a boundary condition, not an obstacle to “work around”: data close to random cannot be losslessly compressed, so any gain can only come from structure that real corpora (documents, scans, telemetry) actually possess.
It is the third iteration of a multi-year research line: frequency analysis and dictionaries over an encoded stream (2021), dictionaries of bit patterns (2024), dependency coding and tile deduplication with a whitepaper dated 2025-04-23 (2025). Each iteration is documented — including why the previous one was not enough.
Method. As in the rest of the lab: problem → hypothesis → falsifiable criterion → method → result with boundary conditions. In this program, negative results are so far the main product — and are published as such.
Publication note (IP). For patentable directions we publish the problem, the state of the art and the success criterion — not the solution’s construction. Where “Construction: withheld” appears, the technical detail is retained as filing material.
1. Direction 1 — dependency coding (relations between neighbouring bits)
Research question. Does a reversible representation of a stream as layers of relations between neighbouring bits — instead of the values themselves — yield, after a classical final coder (RLE / entropy), an output smaller than the input on structured corpora? Why it is hard. A reversible transform removes not a single bit of entropy by itself; any gain can only come from the relational representation being easier to compress for the final coder than the original. Whether that holds is settled exclusively by measurement, not by argument. State of the art (published). Delta/predictive coding, RLE, DEFLATE, modern entropy coders (ANS) — treated as the reference point and as components, not as competition to replace. Success criterion (two-part). (a) Hard, met: full reversibility confirmed by a cryptographic checksum on every decode. (b) Open, unmet: measured ratio on defined corpora against gzip/zstd — the measurement program has not yet been run; until then no compression benefit is claimed. Construction (dependency rule, layer construction, container format): withheld (patent option kept open). Status: POC implemented (reversibility verified); benefit — not demonstrated; next step: the benchmark.
2. Direction 2 — structural deduplication of the binary image (the PGA codec)
Research question. Can the recurrence of small spatial patterns in a binary (1 bit/pixel) rasterization of a file be exploited via a pattern dictionary so that the total of dictionary + reference map + residual layer is smaller than the input — with bit-exact reconstruction? Why it is hard. The approach belongs to the dictionary family (block matching, vector quantization) and is deliberately a different axis from lossy transform coding (JPEG/DCT): there is no perceptual quantization of any kind; the criterion is bit-exact and hash-verified. The cost of the dictionary and the map is real; on data without spatial recurrence the deduplication has nothing to find and the overhead wins. State of the art (published). Dictionary methods and block matching; content deduplication via hashes; residual coding. A deliberate separation from JPEG/DCT at the problem level (bit-exact losslessness vs perception). Success criterion. Bit-exact reconstruction (met, hash-verified) and a positive size balance including dictionary overhead on a structured corpus (unmet on high-entropy data — see the negative result). Construction (tile size and indexing, matching tolerance, residual layer, container format): withheld. Status: POC implemented / in validation.
3. Negative result (published): the entropy limit is hard — and measured
- Measurement. The structural deduplication codec, run on a compressed executable (14.2 MB), produced an output 56% larger than the input (22.2 MB): the high-entropy input contains no repeated tiles, and the overhead of dictionary, map and residual layer dominates. Not an anomaly — theory confirmed on one’s own code.
- Abandoned variant. One early realization of the layer coding turned out to be degenerate — on analysis it encoded no real dependency and was abandoned, together with a record of why. A refuted hypothesis is a document here, not an embarrassment.
- Scoping conclusion. Structural methods are only justified on structurally repetitive corpora; narrowing the program to such corpora (documents, scans, telemetry) is the result of these falsifications, consistent with information theory — not an assumption taken up front.
4. Systematicity: the 2021 → 2024 → 2025 evolution line
Three approaches to the same question, each with a documented reason for moving to the next: frequency analysis and dictionaries over an encoded stream (2021, exploration abandoned), bit-pattern dictionaries with repetition aggregation (2024, expansion on high-entropy data), dependency coding + tile deduplication (2025, whitepaper + prototypes + a measured negative). The recurring motif — gains on repetitive data, expansion on random data — is precisely what moved the program from “a better general-purpose compressor” to structure-first compression of specialized corpora. Program status: active, at the design/POC level; the next stage is a defined benchmark with a disclosed corpus and reference baselines.