Compression Research

Research on anchor-based dictionary compression: how anchor placement, reference dependencies, and resident-source limits affect phrase counts, encoded bytes, and decoding schedules. This repository is for researchers and programmers who want to read the studies, inspect their data, or reproduce the experiments. It includes exact Python models, experimental byte codecs, and a C++/Rust lossless baseline.

Studies, proofs, and papers

• Anchor placement and independent frontiers: exhaustive analysis of 131,068 binary strings, minimal counterexamples, direction controls, and metadata sensitivity.
• Anchor expansion benchmark: a negative result across six synthetic corpus classes; zstd-1 outperformed the Python anchor implementation in encoded size and measured encode/decode speed.
• Resident-cache parsing: complete byte accounting, negative controls, and a finite scheduling separation.
• Bounded-switch theorem: a direct proof of a 2W+2 switch bound when the frontier window is shorter than a match.
• Related papers: dictionary compression, LZRR, string attractors, bit-optimal parsing, bicriteria compression, and bounded access. These references place the experiments in context without a novelty claim.

The research guide connects the definitions, studies, source, and datasets. Scientific measurements include negative results and limitations; structural gains do not imply practical compression or runtime gains.

Try an exact experiment

Requires Python 3.11 or newer; the exact reference tools use the standard library. From the repository root:

PYTHONPATH=ppc/research python3 -m anchor_compression.exhaustive \
  --max-length 7 --anchor-length 2 --min-match 2 \
  --output /tmp/anchor-exhaustive.json

To analyze a small slice of your own file:

PYTHONPATH=ppc/research python3 -m anchor_compression.cli input.bin \
  --offset 0 --length 24 --anchor-length 2 --min-match 2

Exact search grows expensive rapidly. Start with short slices; 24 bytes is an example, not a guaranteed runtime limit. Exhaustive enumeration examines exponentially many strings. See tool usage for the byte codecs, cache experiments, and dataset checks.

Build the PPC1 lossless baseline

With Rust and Cargo:

cargo test --manifest-path ppc/rust/Cargo.toml --workspace --release
cargo build --manifest-path ppc/rust/Cargo.toml --release -p ppc-cli
ppc/rust/target/release/ppc-rs c input.bin output.ppc
ppc/rust/target/release/ppc-rs d output.ppc restored.bin
cmp input.bin restored.bin

Or with CMake 3.19+ and a C++20 compiler:

cmake -S ppc -B ppc/build -DCMAKE_BUILD_TYPE=Release
cmake --build ppc/build -j
ctest --test-dir ppc/build --output-on-failure
ppc/build/ppc c input.bin output.ppc
ppc/build/ppc d output.ppc restored.bin
cmp input.bin restored.bin

Both CLIs accept - for stdin/stdout but buffer whole inputs; this is not bounded-memory streaming. PPC1 is a deterministic experimental format, not a production archive format. It has no checksum or configurable decode-allocation limit. Use trusted files and retain originals. See the format.

Troubleshooting

• Python cannot import anchor_compression: run from the repository root with PYTHONPATH=ppc/research as shown above.
• A search takes too long: reduce slice length or --max-length; all-anchor exact search and binary enumeration are intentionally small-input tools.
• Empty slice or anchor exceeds input: check the file offset and use an anchor no longer than the selected nonempty slice.
• Missing build tools or dependencies: use the Python experiments without a compiler, or install the toolchain for your chosen native implementation. Rust's FFI crate uses libc; Cargo needs that dependency available locally when running offline.
• Malformed stream: PPC1, ABC1, and ACR1 are different formats. Use the matching decoder. Format rejection is not cryptographic integrity protection.
• Missing optional benchmark comparison: the Python benchmark records unavailable zstandard or native-compiler comparisons as skipped.