CS Paper Radar

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.DS ·2026-09-24 ·Jonas Ellert, Lukas Nalbach
similarity 0.60
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

Efficient Lempel-Ziv Prediction with the Run-Length BWT

cs.DS cs.LG ·2026-11-01 ·Ohad Avnery
similarity 0.58
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

A Non-constant Lower Bound for Grammar-Based Compression with Greedy

cs.DS cs.FL ·2026-09-10 ·Danny Hucke
theory similarity 0.55
Abstract

We prove a lower bound of Ω(log n/ log log n) on the approximation ratio of the global grammar-based compression algorithm Greedy. To our knowledge, the previously best lower bound was a constant, and the existence of a nonconstant lower bound had remained open for more than twenty years. Our bound holds on an infinite family of words of length n, over alphabets of growing size, for every execution using left-to-right occurrence replacement and arbitrary tie-breaking. The lower bound is also formally verified in Lean 4.

0.25

zip2zip++: Towards Inference-Time Token Compression with Minimal Quality Loss

cs.CL ·2026-10-09 ·Saibo Geng, Andrea Gentilini, Xinxian Ma, Nathan Ranchin, Yunzhen Yao +1 more
code/data similarity 0.53
Abstract · 27 pages, 12 figures, 13 tables. Code: https://github.com/epfl-dlab/zip2zip-plus-plus

Dynamic vocabularies built on-the-fly via Lempel-Ziv-Welch (LZW) compression let a language model represent the same text in fewer tokens, but prior work shows that this efficiency comes at a cost to reasoning and perplexity. We show that this quality gap is not a fundamental price of compression but can be substantially closed through targeted improvements to the compression layer and LZW codec, without modifying the underlying pretrained language model. Our analysis reveals four key issues: (1) LZW's compression algorithm creates an implicit conflict between the input embedding and the output embedding, a tension that a single shared embedding cannot resolve; (2) naively applying RoPE to LZW-compressed sequences ignores that merged tokens can span multiple tokens; (3) merging certain tokens (notably digits) disproportionately hurts downstream accuracy; and (4) dynamic vocabularies introduce an inherent segmentation ambiguity that confounds standard evaluation. We address these through decoupled input/output dynamic embedding layer, size-aware RoPE positioning, and a modified LZW codec supporting selective merges and multi-view segmentations. Across four models, our recipe improves perplexity on every corpus we evaluated as well as mathematical reasoning accuracy, closing roughly half the quality gap between zip2zip and the uncompressed baseline at a similar compression ratio on general text. This represents a significant step toward lossless adaptive-vocabulary compression for language models.

0.39

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

cs.DC cs.DS ·2026-09-15 ·Yakiv Shavidze
similarity 0.53
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.53
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

Copying along Arithmetic Progressions Cannot Simulate Interleaving with Polylogarithmic Loss

cs.DS cs.FL ·2026-11-16 ·Matthias G. Mayer
code/data similarity 0.53
Abstract · 45 pages. Lean 4 formalisation: https://github.com/matthiasGmayer-research/copying-vs-interleaving-lean

Two classical ways to compress a word are straight-line programs (SLPs), which build it by concatenating smaller pieces, and the Lempel-Ziv 77 (LZ77) factorisation, which copies earlier parts of it; their sizes are measures of repetitiveness. LZ77 approximates the smallest SLP efficiently: it has no more factors than a smallest SLP has size, and yields an SLP at most a logarithmic factor larger in near-linear time. Motivated by online prediction, Kosoy introduced zipline programs, which are analogous to SLPs but interleave their pieces round-robin instead of concatenating them. Her generalisation of LZ77, the arithmetic repetition system, describes a word by copies from one arithmetic progression of positions to a later one. Do arithmetic repetition systems approximate the smallest zipline program as well? Kosoy proved that the least size $\mathrm{ARC}(x)$ of an arithmetic repetition system for a word $x$ of length $n$ is at most a factor $O(n^{1/3})$ larger than the least size $\mathrm{ZLC}(x)$ of a zipline program for it, and asked whether this factor is tight. Her polynomial-time next-letter predictor makes $O(\mathrm{ARC}(x)\log n)$ mistakes, so a polylogarithmic factor would bound its mistakes by $\mathrm{ZLC}(x)\,\mathrm{polylog}(n)$, which no known polynomial-time predictor achieves. We show that the optimal exponent is $1/4$, not $1/3$: $\mathrm{ARC}(x) \le 2n^{1/4}\,\mathrm{ZLC}(x)$ for every word $x$, and at every large enough length $n$ some binary word has $\mathrm{ARC}(x) \ge n^{1/4-o(1)}\,\mathrm{ZLC}(x)$.

0.52

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

cs.IT ·2026-10-08 ·Yingquan "Cody" Wu
code/data similarity 0.52
Abstract · 10 pages, 5 tables, 2 figures. Submitted to the 2027 Data Compression Conference (DCC). Source code: https://github.com/icodywu/WZIP (releas…

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).

0.59