CS Paper Radar

WZIP and WLZ4: LZ77 Codecs with Match-Length-Dependent Sliding Windows

Yingquan "Cody" Wu

cs.IT ·submitted 2026-10-08 12:06 UTC · v1
code/data

Abstract

An LZ77 codec bounds every match by one sliding window, trading cheap offsets for short matches against reach for long ones. Match-length-dependent windows refine this trade-off: each match length has its own window, and the decoder infers the offset range from the decoded length. We present two such codecs: WLZ4, a byte-aligned LZ4-class format with one-byte and flagged offsets, and WZIP, an entropy-coded Zstandard-class format. Each block begins with its decoded length, from which WZIP derives its widest window and a decoder sizes its output. LZ4 blocks may expand incompressible input by 0.4%; WLZ4 adds at most 15 bytes, WZIP 2. We describe the formats, threaded match finders, decoders and parser. On Silesia, WLZ4 reaches a ratio up to 16% above LZ4HC's, decoding more slowly, and WZIP exceeds Zstandard 22's ratio while its trusted decoder runs at 91% of Zstandard's speed (87% checked; on enwik9, about as fast).

Comment
10 pages, 5 tables, 2 figures. Submitted to the 2027 Data Compression Conference (DCC). Source code: https://github.com/icodywu/WZIP (release v1.0.0). Distinct from arXiv:2610.06530, which analyzes length-dependent window schedules in theory; this paper presents two complete codecs, their formats, parser and decoders, and measurements against LZ4, Zstandard, Brotli and xz

Closest papers

Nearest neighbours by meaning across the whole index.

The Price of Random Access: Measuring Block Granularity Across Four Compressed Formats

cs.DC cs.DS ·2026-09-15 ·Yakiv Shavidze
similarity 0.69
Abstract · 7 pages, 5 figures, 6 tables. Sixth paper in the ACEAPEX series (see arXiv:2606.04268, 2606.18900, 2606.24531, 2607.18541, 2608.10188). Code…

Random access into compressed data is normally bought with density. We measure the exchange rate. Across four formats and nine axes on a common corpus, the cost of cutting a 254 MB archive into independently addressable 16 KiB units is 1.632% of the archive for an absolute-offset format against 6.57% for seekable zstd, and the gap widens as the unit shrinks: at 4 KiB, 5.33% against 10.06%. Because the cost is small, several properties follow that are usually unavailable: splitting an archive is free and occasionally profitable (-0.28% on tiled input), append needs no format change, seek latency does not depend on position, and one archive is read by both a CPU and a GPU decoder. We give three structural results with proofs and bit-perfect verification - that the repeat-distance chain of an LZ77 parse forms a substitution monoid and is therefore prefix-scannable without touching the bitstream, that self-overlapping matches are periodic rather than chained, and that dependency depth admits an encoder-enforced bound - and we report each measured limit together with the mechanism that sets it. Seventeen rejected directions are listed with their numbers, including one that improved density by 26% and was declined. Every claim carries a level: reproducible by command, measured with a stated reason, or estimated. The measurement tool is released separately (DOI 10.5281/zenodo.22713364) with 435 provenanced records.

0.50

Lempel-Ziv Parsing with Match-Length-Dependent Windows: Universality and Limits

cs.IT ·2026-10-05 ·Yingquan, Wu
similarity 0.66
Abstract · 39 pages, 4 figures, 3 tables. v2: rewritten for clarity, with a new title (v1 was "Improved LZ77 Compression with Match-Length-Dependent Sl…

LZ77 coders spend the same number of bits on the distance of every match, although short matches rarely pay off at long distances. With match-length-dependent windows, used in several practical codecs, a match of length $\ell$ may refer back at most $W(\ell)$ symbols: short matches get short distance fields, while long matches keep the full window $W$. This breaks the suffix closure that classical LZ77 analyses rely on: the tail of an admissible match need not be admissible. We bound the cost of this loss, and of matches missed by a practical hash search, by the phrase count of a single-window reference parse. Consequently, when the full window starts at length $O(\log W)$, greedy parsing keeps the convergence rates and the optimal finite-input rates of LZ77 under substring-complexity constraints, and when it starts at length $o(\log W)$, greedy parsing is universal for stationary ergodic sources. We then delimit what the windows gain. A calibrated schedule never increases the minimum code length and saves a polynomially small rate on some iid sources. The leading redundancy term is set by the length code instead: on uniform iid data, with logarithmic-cost lengths and a fixed full-window threshold, it is at least of order $(\log\log W)/\log W$ whatever windows the short matches use, and a short codeword for a growing longest match reduces it to $O((\log\log\log W)/\log W)$. We also quantify the gains of coding single-symbol runs by count and of Huffman coding the token fields, and obtain a consistent entropy-rate estimator by selecting the window.

0.50

What Actually Serializes GPU LZ77 Decode: Three Decoders, Three Mechanisms, and an Encode-Time Lever That Removes the Last One

cs.DC cs.PF ·2026-08-10 ·Yakiv Shavidze
similarity 0.60
Abstract · 7 pages, 13 figures. Fifth paper in the ACEAPEX series (see arXiv:2606.04268, 2606.18900, 2606.24531, 2607.18541). Code and data: DOI 10.528…

The sequential part of GPU LZ77 decode is not where the field assumes it is. Across three decoder architectures on an H100 we measure that parse, not copy, holds 64-72% of device-resident decode time; that bounding back-reference chain depth - provable, and costing 0.006% in ratio - moves latency by at most 2.8% and, for the file's own latency spike, provably by nothing at all, since a byte-level comparison of all 15,499 blocks shows the cap alters none of the 181 blocks involved; that self-overlapping matches are periodic fills rather than dependency chains, which makes them fully parallel and speeds the match layer by 2.75-8.42x bit-perfect; and that the last genuinely sequential element, a four-entry distance history, can be removed by the encoder for 0.540% of ratio, growing the dependency-free parse run from 4 commands to 706. We also report the floor the format runs into: with a median match of 7 bytes against a 128-byte cache line, bus efficiency is 4.4% and a coalesced write of the same data is 39x faster. A separate section records ten hypotheses these measurements refuted, including one methodological error of our own. Every reproducible claim carries a machine-checkable record: a fresh clone of the tagged release passes 17 of 17 checks reachable without a GPU, none failing.

0.07

pigzpp: Fast, Parallel, Portable Compression for the Whole Stack

cs.DC ·2026-08-25 ·Thamme Gowda
similarity 0.59
Abstract

pigz is a widely deployed parallel gzip utility, but its process-global mutable state means that it was not designed as a reentrant, directly embeddable library. pigzpp is a from-scratch C++23 rewrite that turns the design into a thread-safe library with one accelerated DEFLATE core exposed to C++, Python, WebAssembly, Go, and Rust. As application-level conveniences built on that same core, it also provides multi-entry ZIP archives and a fast PNG codec. Its portable zlib-ng backend preserves gzip/zlib's ratio; its Intel ISA-L backend is an x86-64-only fast path that produces about 10% larger output at level 6 on our text corpus. In that configuration, zlib-ng reaches 2.1 times the CLI throughput of pigz and 16 times that of Python's in-memory gzip; ISA-L reaches 8.5 times and 50 times, respectively. Outputs remain standards-compliant and cross-decode with gzip, pigz, and unzip. The result is a self-contained, multi-platform compression stack and a case study in AI-assisted modernization under automated compatibility tests.

0.31

Tetra: Serving Leech-Lattice Quantized LLMs at 2.7 Bits per Parameter

cs.LG ·2026-09-28 ·Pier-Jean Malandrino
code/data similarity 0.57
Abstract · 15 pages, 4 figures, 8 tables. Code, measurement logs and preregistrations: https://github.com/pjmalandrino/llvq

Leech-lattice quantization gives good quality at two bits per weight, but its codebooks hold more than 10^14 points, too many for a lookup table. Our earlier kernel expanded the codes at load time and read 4.804 bits per weight from GPU memory for 2 bits of code. We present Tetra, a new codebook on the same lattice. A 24-weight block still takes 48 bits, most of which index a 64-state trellis of the Golay code and one shared 16 KiB table. The kernel decodes a block with six table loads and two small lookups inside the matrix-vector product, and reads 2.148 bits per weight. For full models, we retrain one scale per matrix row, store the matrices that lose the most as 4-bit integers, and pay for them with 4-bit embedding tables. Our Qwen3-4B, 8B and 14B files hold 2.73, 2.70 and 2.73 bits per parameter over the whole model. They score 63.37, 69.58 and 75.66 on the full MMLU test set, 4.76, 4.21 and 2.46 points below 4-bit AWQ at 5.3 to 6.0 bits per parameter. They generate 113.8, 95.0 and 57.2 tokens per second in our engine. On GSM8K, through the served kernel, they lose 9.63, 4.62 and 3.26 points to FP16. At 4B our file scores 23.6 points above llama.cpp's IQ2_XXS (2.48 bits per parameter). Every number we measured for a table or figure comes from one NVIDIA L40S GPU. We preregistered the main experiments.

0.33

Efficient Lempel-Ziv Prediction with the Run-Length BWT

cs.DS cs.LG ·2026-11-01 ·Ohad Avnery
similarity 0.56
Abstract · 21 pages, 1 table

Lempel-Ziv Plurality (LZP) is an algorithm of Kosoy that predicts the next symbol of a string by using its Lempel-Ziv factorization, and makes at most $O(z\log n)$ mistakes on every string of length $n$ with $z$ LZ77 phrases. We give efficient online implementations of LZP and of a new variant of it. Our first implementation maintains a run-length encoded Burrows-Wheeler transform (RLBWT) of the reversed history. It implements LZP, uses $O(z\log z\log^2 n)$ bits, and has worst-case update and prediction times $O(\log z+\log\log n)$ and $O(σ(\log z+\log\log n))$, respectively, where $σ$ is the size of the alphabet. This is an exponential improvement over Kosoy's implementation, whose update time is $O(z\log^7 n)$. We then introduce the Lempel-Ziv Majority (LZM) predictor, which has the same mistake bound and update time, and predicts in $O(1)$ time independently of $σ$. These two predictors accept new symbols at any time, without knowing the alphabet in advance. For an alphabet known in advance, a different data structure gives $O(σ(1+\log z/\log\log n))$ time per symbol, which is constant when $σ=O(1)$ and $z=\mathrm{polylog}(n)$.

0.25

blaris: Windowless Random-Access LZSS for Constrained Microcontrollers

cs.AR cs.IT ·2026-11-17 ·Ihor Lukianov
code/data similarity 0.55
Abstract · 4 pages, 1 figure, 2 tables. Source code and benchmark suite available at https://github.com/lis05/blaris

Embedded LZ77 decompressors (such as heatshrink and tamp) require an in-RAM sliding window that couples memory usage to compression ratio and incurs high latency on random-access reads. We present blaris, a lightweight, windowless LZSS decompressor for execute-in-place (XIP) random access on constrained microcontrollers. By partitioning tokens into bidirectionally traversable streams with power-of-two checkpoints, blaris resolves back-references directly in the compressed payload, achieving compression ratios comparable to high-window heatshrink and tamp configurations without allocating a RAM window. Targeting compress-on-host, decompress-on-device workflows, blaris assumes trusted build-time payloads and omits runtime error and bounds checks. On RV32IMC, it requires just 548-784 B of Flash and 104-112 B of total RAM, achieving orders-of-magnitude faster small-slice random reads than ratio-matched, block-indexed heatshrink and tamp.

0.30

Practical and Space-Efficient LZ77 and LZ Pre-Compression via String Synchronizing Sets

cs.DS ·2026-09-24 ·Jonas Ellert, Lukas Nalbach
similarity 0.55
Abstract · 17 pages, 6 figures, 4 tables. Full version of the ALENEX 2027 paper

The Lempel-Ziv (LZ77) factorization decomposes a text into the least possible number $z$ of phrases that each refer to an earlier occurrence. It is this phrase count, rather than the encoded size, that governs the size of LZ-based compressed indexes, and computing a factorization with few phrases is a time and space bottleneck in their construction. In practice, computing LZ77 quickly typically requires the suffix array. In theory, the exact LZ77 factorization, and a 3-approximation of it, can be computed more space-efficiently without the full suffix array [SPIRE 2023]. These algorithms have remained unimplemented, because two of their components resist a direct implementation: a lookup table that degenerates to patterns of length at most two for realistic inputs, and an orthogonal range reporting data structure that is impractical. We replace both, fine-tune every remaining stage, and obtain the first practical implementation, which runs in space close to the text rather than to the suffix array. On one thread, our 3-approximation factorizes 12-19x faster than the classical LPF algorithm while using 14x less memory; on 32 threads, even our exact algorithm is 1.4-2.9x faster than parallel LPF, at 9x less memory. In practice the approximation ratio stays far below 3. As a side result, passing only the perfect phrases of our 3-approximation to a downstream compressor yields a precompressor that is on par with the state of the art [Dinklage, SEA 2026] in compression ratio, and better in memory consumption and parallel throughput.

0.19