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

What it claims

The named replacements and their measured payoffs, which the summary compresses into "replacing two components." Ellert's sublinear-space LZ77 algorithms (exact in O(n/log_σ n + z log^{3+ε} z) time, 3-approx in O(n/log_σ n) time, both O(n/log_σ n) words) stayed unimplemented because two components resist implementation: the short-pattern lookup table degenerates to patterns of length ≤2 on realistic inputs, and the insertion-only orthogonal range one-reporting (IO-OROR) structure is impractical. This paper replaces both, tunes every remaining stage, and ships a tool called ssszip.

How it works

• 3-approximation: the degenerate lookup table becomes a tunable rolling Karp-Rabin hash index mapping fingerprints of multiple pattern lengths to previous-occurrence positions, combined with an optimized LPF-phrase computation. It emits 1.40–2.02z phrases in practice — far below the 3z worst case.
• Exact: IO-OROR is implemented with a simple grid, and the instance is decomposed into σ smaller ones (Theorem 4.4), shrinking effective grid area by up to a factor of σ.
• Interval sampling: the other exact-path bottleneck (sparse SA/PA intervals) is cut by precomputing hash tables over adaptively chosen pattern lengths, giving expected O(1) interval lookups.

Evidence

• Interval sampling reduces total exact running time by 1.7–3.2×.
• Parallelization yields 2.8–6.3× for the 3-approximation and 13–26× for the exact algorithm on 32 threads.
• The single-thread and 32-thread speed/memory figures vs. LPF are as the summary states (12–19× / 14× memory; 1.4–2.9× / 9× memory).
• As a precompressor, ssszip paired with bsc matches the state-of-the-art alz [6] in compression ratio and beats it on memory and parallel throughput.

How to use it

The tool is ssszip; the paper pairs it with the bsc compressor (libbsc.com). Intended as a building block for LZ-based compressed indexes, grammar compression, and compressed computation, where phrase count — not encoded byte size — bounds both index size and downstream running time.

Limits

The fetched text cuts off mid-Section 3.2 (exact-algorithm invariants), so absolute throughput numbers, input corpora, and the ssszip/bsc/alz comparison table are not visible here — the ratios above are what the abstract and contributions list state. No install command or license appears in the captured text.