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

1 Introduction

• Conventional compressors prioritize encoded byte size and speed over minimizing phrase count, a trade-off suited to comparatively small, low-redundancy files.For highly repetitive text, the resulting compression can be inadequate.Source: §1 · p. 1
• Phrase count controls LZ-index size, and a factorization with few phrases is a time-and-space bottleneck in index construction.Phrase count also bounds the running time and space of several computations built on LZ-like factorizations.Source: §1 · p. 2

1.1 Our contributions.

• The implementation replaces a short-pattern lookup table that degenerates on realistic inputs and an impractical range-reporting structure in Ellert’s exact and 3-approximation algorithms.Ellert’s algorithms use O(n / logσ n) words of space; the paper targets practical LZ-based indexes, grammar compression, and compressed computation.Source: §1.1 · p. 2
• The optimized LPF-phrase computation factorizes 12–19× faster than the classical LPF algorithm on one thread, uses 14× less memory, and produces only 1.40–2.02 z phrases.Source: §1.1 · p. 2
• 1.4–2.9× faster than parallel LPF on 32 threads, the exact algorithm uses 9× less memory.The practical exact algorithm implements IO-OROR with a grid and decomposes the instance into σ smaller ones.Source: §1.1 · p. 2
• 1.7–3.2× lower total running time, interval sampling uses hash tables for adaptively chosen pattern lengths to make interval lookups expected O(1).Sparse SA- and PA-interval computation is a bottleneck apart from IO-OROR queries.Source: §1.1 · p. 2
• The algorithms parallelize every stage, achieving 2.8–6.3× speedups for the 3-approximation and 13–26× for the exact algorithm on 32 threads.The parallel gap factorization falls back to the sequential algorithm when g/n ≤ 0.2.Source: §1.1 · p. 2
• The perfect phrases of the 3-approximation yield ssszip, a precompressor that, paired with bsc, matches alz in compression ratio and improves memory use and parallel throughput.The paper identifies alz as the state of the art.Source: §1.1 · p. 2

2 Preliminaries.

• An LZ77 factorization partitions T into phrases; an LZ-like factorization allows referencing phrases shorter than the longest prior match.An LZ77 reference uses an earlier occurrence, and exact LZ77 references are maximal.Source: §2 · p. 3
• The LPF algorithm obtains each longest previous factor by comparing the LCEs with the suffix-array positions given by PSV and NSV, then extracts the factorization in a left-to-right pass.The required suffix-array arrays and constant-time LCE structure can be computed in O(n) time and words.Source: §2 · p. 3
• Karp–Rabin fingerprints assign equal fingerprints to equal substrings, while unequal substrings can collide with probability O(1/n) for a uniformly random base.The stated setup chooses a prime q = Θ(n^c), c > 1, and a base b ∈ [σ, q).Source: §2 · p. 3
• A τ-synchronizing set selects equal-position samples in equal substrings of length at least 2τ, and its density condition guarantees |S| = Θ(n/τ).The definition uses a periodicity condition on substrings of length 3τ − 2.Source: §2 · p. 3
• Sparse suffix and prefix arrays order sampled suffixes and prefixes, while sparse LCP, PSV/NSV, and LPF arrays are defined over the sampled positions.The sparse suffix-array interval for a pattern can be found by binary search using constant-time LCE queries.Source: §2 · pp. 3–4
• With a synchronizing set using τ = logσ n, sparse structures support O(1)-time LCE queries in O(n / logσ n) space.The recalled prior algorithms compute a 3-approximation and then the exact LZ77 factorization on top of it.Source: §2 · p. 4, §3 · p. 4

3 Algorithms

• A phrase is perfect if it is the final phrase or extending it by the next phrase’s first character has no earlier occurrence; there are at most z perfect phrases.This criterion identifies phrases that are maximal in the current LZ-like factorization.Source: LZ77 3-approximation · p. 4
• The 3-approximation proposed in computes an LZ-like factorization with perfect and non-perfect phrases; at most z phrases are perfect, meaning maximal-length phrases or the final phrase.Source: LZ77 3-approximation · p. 4
• Perfect phrases provide the maximal-match component of the approximation; non-perfect phrases complete its LZ-like factorization.The passage distinguishes these phrase types by whether a one-character extension has an earlier occurrence.Source: LZ77 3-approximation · p. 4

LZ77 3-approximation

• A gapped factorization combines maximal perfect phrases at samples with sample-free gaps and optional referencing phrases.Its phrase count is at most z; the approximation then closes gaps, shortening long periodic ones and resolving short ones.Source: LZ77 3-approximation · p. 4
• The 3-approximation produces at most 3z phrases in O(n/ logσ n) time and space.At most two non-perfect phrases are added per gap, yielding z′′ ≤ 3z.Source: LZ77 3-approximation · p. 4

3.2 Exact LZ77 Algorithm

• For exact phrase searches, the algorithm builds a δ-dense, leftmost-substring-covering sample set and maintains an insertion-only orthogonal range one-reporting structure.The range structure supports insertion and rectangle queries over sampled suffix and prefix array positions.Source: §3.2 · pp. 4–5
• The exact algorithm computes LZ77 in O(n/ logσ n + z log3+ϵ z) time and O(n/ logσ n) space.It builds on the 3-approximation and constructs a sample set before computing phrases.Source: §3.2 · p. 5
• The exact algorithm searches close sources directly and far sources by splitting a candidate phrase into a head and tail, then querying for a matching sample.A reported point from the range query identifies a source for the candidate phrase.Source: §3.2 · p. 5

4 Algorithmic Optimizations

• The approximation processes gaps in a second left-to-right pass using a rolling hash index after computing LPF phrases.The implementation uses a synchronizing set with τ = 512.Source: §4.1 · p. 6, §4 · p. 6

4.1 3-Approximation

• Extending an LPF phrase left across a preceding gap and skipping covered samples are practical optimizations for the 3-approximation.The synchronizing condition ensures skipped samples contribute nothing beyond the later LPF phrase.Source: §4.1.1 · p. 6

4.1.1 LPF-Phrase Computation

• The LPF-phrase stage skips samples covered by a later phrase and runs only gap-closing Phase 3, since Phase 2 did not improve practical time or approximation ratio.Source: §4.1.1 · p. 6, §4.1.2 · p. 6

4.1.2 Gap Factorization

• A rolling Karp–Rabin hash index replaces a lookup table limited to patterns of length at most two for practical inputs.It checks fingerprints of multiple pattern lengths against prior occurrences and extends the best match using LCE.Source: §4.1.2 · p. 6
• Selective sampling between distant phrase endpoints reduces the sample set C size by approximately 30% versus the generic construction.The implementation inserts extra samples only when consecutive endpoints in E are farther apart than δ.Source: §4.2.1 · p. 7

Orthogonal Range One-Reporting

• A fixed insertion order lets exact LZ77 use static weighted OROR; arbitrary query weights eliminate close-source method 1 and let threads factorize separate text parts.The fixed-order IO-OROR instance is reduced to SW-OROR by assigning insertion-order weights.Source: Orthogonal Range One-Reporting · p. 7
• The grid structure stores points sorted by cell and weight, using O(N + (N/D)^2) words; queries check fully contained cells and then boundary points.Points in each cell are sorted by weight, so cells whose first point exceeds the query weight can be skipped.Source: Orthogonal Range One-Reporting · p. 7
• Under a uniform character distribution, character-wise decomposition reduces effective grid area by factor σ, allowing smaller cells or a smaller structure at unchanged cell width.The global instance is split into σ independent instances.Source: Orthogonal Range One-Reporting · pp. 7–8
• For narrow query rectangles, the algorithm scans the smaller rank interval using precomputed Π and Ψ arrays, a method reported faster than the grid for short ranges.The scan checks the corresponding rank mapping and sample bound.Source: Orthogonal Range One-Reporting · p. 8

4.2.3 Sparse Prefix- and Suffix-Array Inter-

• Adaptive sampling precomputes hash tables for selected pattern lengths, giving expected O(1) interval lookup; unsampled lengths use tighter brackets for binary search.For prefix intervals, the sampled-length budget is θ = 2|C| and λmax = δ.Source: §4.2.3 · pp. 8–9

4.3 Parallelization

• Gap factorization splits gap positions into blocks processed in batches across at most K iterations because the rolling index state cannot be split directly among threads.Block size is B = max(4096, n/(K · p)).Source: §4.3 · p. 9
• Parallel gap factorization can reduce compression ratio by up to factor 2, especially for 0.1 < g/n < 0.5; it falls back to sequential when g/n ≤ 0.2.The exact algorithm instead partitions the text into 16p regions, each producing perfect phrases except possibly its last, for at most z + 16p phrases.Source: §4.3 · pp. 9–10

5.1 LZ Factorization Performance

• The 3-approximation produces 1.40–2.02 z phrases and uses 1.17–1.19n bytes, 14× less memory than LPF.The exact variants use 1.31–1.38n and 1.80–1.88n bytes, respectively.Source: §5.1 · p. 10, Figure 5.1 · p. 11
• On one thread, sss-3aprx is 12–19× faster than LPF; interval sampling makes sss-exact-smpl 1.7–3.2× faster than sss-exact.From 1 to 32 threads, sss-3aprx speeds up by 2.8–6.3×, while the exact variants speed up by 20.5–22.8× and 13–26×.Source: §5.1 · p. 10
• ssszip-bsc reaches 1.3–94× the compression ratio of the best general-purpose compressor per text, at 2.8–27× xz’s and 3.3–30× 7z’s compression throughput.The ratio advantage is largest on chr19, where long-range repetitions evade window-, block-, or dictionary-limited compressors.Source: §5.1 · p. 11, Figure 5.2 · p. 12
• Against alz-bsc, ssszip-bsc has similar compression ratios but uses 1.25× less memory and is 1.7–3.9× faster on 32 threads.The throughput factors are 1.9× on sars2, 3.9× on chr19, and 1.7× on dewiki.Source: §5.1 · p. 12, Figure 5.2 · p. 12
• At decompression, ssszip-bsc uses 0.06–0.12n bytes; bsc uses 15–50× as much and is 8× slower on sars2 and 16× slower on chr19.bsc is faster only on dewiki.Source: §5.1 · p. 12, Figure 5.2 · p. 12
• On 32 threads, the 3-approximation is 4.5–13.6× faster than the classical algorithm, and the exact algorithm is 1.4–2.9× faster, using 9× less memory.The paper also reports 14× less memory for the 3-approximation.Source: §6 · p. 12

A Omitted Proof

• The proof sets μ = χ(3) and ν = χ(λmax), then chooses λj from LCP′ entries and sets λM = λmax.The passage gives the construction in terms of C[⌊μ + jM(ν − μ)⌋].Source: A Omitted Proof · p. 15
• Choosing M = ⌊(2θ + μ − ν)/(μ + ν)⌋ ensures condition (i) and gives M ≥ 1 when θ ≥ ν.The proof derives the bound for condition (i) from this choice.Source: A Omitted Proof · p. 15
• The proof states that conditions (ii) and (iii) hold in expectation under its assumptions on j.The appendix also says it explains the choices for the implementation’s eight tunable parameters.Source: A Omitted Proof · p. 15, B Parameter Choice and Tuning · p. 15

B Parameter Choice and Tuning

• The tuning corpus is disjoint from the evaluation texts in size and, for four of eight texts, also in content.It includes texts with g/n from 0.0003 to 0.70.Source: §B.1 · p. 15
• Parameters were swept one at a time over powers of two, selecting values best or tied for best on most of the corpus across throughput, peak memory, and applicable approximation ratio..Source: §B.1 · p. 15
• Because the tuning corpus is smaller than the 50 GB evaluation texts, parameter values are expressed relative to n, z, |C|, or g to transfer across input scales..Source: §B.1 · p. 15

B.1 Tuning Methodology

• For the synchronizing-set parameter τ, τ ≥ 512 lowers memory and raises throughput on non-periodic texts without changing which phrases are perfect.τ = 128 or 256 can be faster on texts with long periodic regions; the authors choose τ = 512.Source: §B.1 · p. 15

B.3 Rolling Hash Index Size h

• The rolling-hash index budget uses g/3 on unrepetitive texts and n/10 on repetitive texts, where the smaller g/3 budget would cause collisions to dominate.The index can also use memory already allocated and released by the LPF phase without increasing peak memory.Source: §B.3 · pp. 15–16

B.4 Pattern Lengths L of the Rolling Hash Index

• The rolling hash index uses five pattern lengths: 2, a length tracking ρ, and three intermediate lengths, balancing short-gap matches against unproductive long patterns.The schedule’s ρ term decays from 2^10 at g/n = 0 to 8 at g/n = 1.Source: §B.4 · p. 16

B.5 Grid Cell Width D

• For the grid, D = 2^14 gives the best measured query throughput; γ = 4096 is the crossover where scanning narrow rectangles beats grid random accesses.The character decomposition can shrink the effective grid area by up to σ, making a small D affordable.Source: §B.5 · p. 16

B.7 Fingerprint Sampling Rate s

• Fingerprint sampling uses s = 16 with 32-bit fingerprints, costing n/4 bytes while keeping the extension loop within a few cache lines.Lookups verify fingerprint matches with an LCE query.Source: §B.7 · p. 16
• The interval budget θ = 2|C| is the largest tested budget whose added memory was repaid by reduced runtime.Suffix-interval sampling extends to the mean approximate phrase length, capped at the largest LCPC entry.Source: §B.7 · p. 16
• Parallel gap factorization uses K = 512, the smallest tested value at which compression ratio had converged; when g/n ≤ 0.2, it falls back to sequential processing to avoid a ratio cost.Large K costs time, while small K costs compression ratio.Source: §B.9 · p. 16

• Tables C.1 and C.2 list the numbers behind Figures 5.1 and 5.2.Source: C Detailed Measurements · p. 16

• Table C.1 reports factorization throughput, peak memory including the text, and approximation ratio on p threads.Its columns cover sss-3aprx, sss-exact, sss-exact-smpl, LPF, and KKP2.Source: Table C.1 · p. 17
• KKP2 and gzip, bzip2, and lz4 are sequential; decompression is single-threaded throughout.Source: Table C.1 · p. 17, Table C.2 · p. 17
• Table C.2 reports compression and decompression throughput, peak memory, and compression ratio for one or 32 threads.Compression ratio is uncompressed size divided by compressed size.Source: Table C.2 · p. 17