Source-linked AI summary
At the Roots of Dictionary Compression: String Attractors
Dominik Kempa, Nicola Prezza
TL;DR
Highly repetitive texts expose limitations of entropy-based compression, motivating a unifying model for dictionary compressors and their compressed-computation structures. The paper introduces string attractors, relates them to existing compressors, analyzes their complexity and approximability, and proves optimal random-access support. Its universal attractor-based structure transfers the random-access result across several dictionary-compression schemes.
Problem
High-order entropy is a weak model for texts containing long repetitions, motivating dictionary compressors and a common account of their fragmented landscape.
Method
The paper introduces string attractors, reduces dictionary-compression measures to and from attractors, studies k-attractor complexity and approximation, and builds random-access structures on attractors.
Results
String attractors unify dictionary compressors, yield approximation relations and complexity results, and support optimal random access through a universal data structure.
Takeaways & Limitations
The attractor framework makes compressed computation independent of the underlying dictionary-compression scheme for the supported random-access setting.
Takeaways & Limitations
The best polynomial-time approximation ratio for minimum string attractors and optimal approximation for some k-attractor cases remain open.
Abstract
from arXiv · showhide
A well-known fact in the field of lossless text compression is that high-order entropy is a weak model when the input contains long repetitions. Motivated by this, decades of research have generated myriads of so-called dictionary compressors: algorithms able to reduce the text's size by exploiting its repetitiveness. Lempel-Ziv 77 is one of the most successful and well-known tools of this kind, followed by straight-line programs, run-length Burrows-Wheeler transform, macro schemes, collage systems, and the compact directed acyclic word graph. In this paper, we show that these techniques are different solutions to the same, elegant, combinatorial problem: to find a small set of positions capturing all text's substrings. We call such a set a string attractor. We first show reductions between dictionary compressors and string attractors. This gives the approximation ratios of dictionary compressors with respect to the smallest string attractor and uncovers new relations between the output sizes of different compressors. We show that the $k$-attractor problem: deciding whether a text has a size-$t$ set of positions capturing substrings of length at most $k$, is NP-complete for $k\geq 3$. We provide several approximation techniques for the smallest $k$-attractor, show that the problem is APX-complete for constant $k$, and give strong inapproximability results. To conclude, we provide matching lower and upper bounds for the random access problem on string attractors. The upper bound is proved by showing a data structure supporting queries in optimal time. Our data structure is universal: by our reductions to string attractors, it supports random access on any dictionary-compression scheme. In particular, it matches the lower bound also on LZ77, straight-line programs, collage systems, and macro schemes, and therefore closes (at once) the random access problem for all these compressors.
1 Introduction
The paper positions dictionary compression as a response to entropy’s weakness on repetitive texts and introduces string attractors as a common combinatorial foundation. It relates compressors to attractors, studies attractor complexity and approximation, and uses attractors to unify random-access results.
- Motivation: Entropy-based compression becomes inadequate for highly repetitive texts, motivating dictionary compressors that replace repeated substrings with dictionary references.The paper situates grammar, pointer, and LZ77-based methods within this repetitive-text compression paradigm.
- String attractors: String attractors are position sets whose elements are crossed by occurrences of all distinct substrings, providing a common model of repetitiveness.The paper interprets dictionary compressors as naturally inducing attractors bounded by their associated repetitiveness measures.
- Relations and approximations: Reductions between attractors and dictionary compressors yield approximation rates and relations such as g*, z ∈ O(c*log^2(n/c*)), c* ∈ O(b*log(n/b*)) ∩ O(r log(n/r)), and b* ∈ O(c*log(n/c*)).These reductions also provide efficient approximation algorithms for minimum attractors.
- Complexity: The k-attractor problem is NP-complete for k ≥ 3, while minimum k-attractors admit approximation results including a linear-time 2k-approximation for constant k.The paper also gives polynomial-time O(log k)-approximations and establishes APX-completeness for constant k.
- Compressed computation: String attractors support optimal random access, and the resulting universal structure transfers these bounds to dictionary-compressed representations.The structure supports substring extraction with configurable space-time trade-offs and matches the relevant lower bounds.
2 Preliminaries
The preliminaries define the paper’s main compression representations and their parameters, including LZ77, macro schemes, collage systems, suffix-based structures, and run-length BWT. They also establish the notation used for strings, suffix arrays, and compressed representations.
- Notation: A substring T[i..j] denotes positions i through j of a string T ∈ Σ^n, whose alphabet size is σ.The paper uses “string” and “text” interchangeably.
- LZ77: LZ77 greedily parses a string left to right into longest previous factors, using earlier non-overlapping sources when phrases have positive length.Its phrase count is denoted z, and this parsing is smallest among parsings whose sources appear earlier in the text.
- Macro schemes: A macro scheme uses copy directives T[i..j] ← T[i′..j′] or character assignments T[i] ← c that unambiguously reconstruct the text.A bidirectional parse is a macro scheme whose non-overlapping left-hand sides cover the whole text; LZ77 is a special case.
- Collage systems: A collage system combines terminal, concatenation, repetition, and substring-extraction rules, generalizing SLPs and run-length SLPs without cycles.Its size is the number of rules, while nonterminal height is defined recursively from the derivation structure.
- Suffix-based structures: The suffix array orders suffixes lexicographically, while BWT is the last column of the sorted cyclic-rotation matrix and supports the LF mapping.Runs in BWT reflect repetitions in the text and can be represented by run-length pairs; the CDAWG recognizes all text substrings.
3 String Attractors
String attractors are position sets whose occurrences collectively cross every substring, providing a common combinatorial lens for dictionary compressors and their reductions.
- String Attractors: A string attractor is a set of positions such that every substring has an equal occurrence crossing at least one selected position.The attractor need not be unique; selecting every position always works, while strings of distinct characters require all positions.
- Reductions from Dictionary Compressors: Dictionary compressors induce attractors whose sizes are bounded by their representation sizes, including collage systems, macro schemes, LZ77, BWT runs, and compact suffix automata.The bounds are c, 2b, z, r, and e respectively for the corresponding compressor or structure.
- Reductions to Dictionary Compressors: Attractor-to-compressor reductions construct a bidirectional parse and collage system of size O(γ log(n/γ)), and an SLP of size O(γ log^2(n/γ)).These constructions turn a size-γ attractor into compact dictionary-compression representations.
- Approximation Relations: The reductions yield approximation algorithms for minimum attractors, although only the LZ77-induced approximation is polynomial-time unless P=NP.The paper then motivates asymptotically better polynomial-time approximations.
4 Computational Complexity
The paper establishes the computational complexity of k-attractors through reductions from set cover and analyzes approximation limits for minimum k-attractors. For k ≥ 3, the decision problem is NP-complete, while the optimization problem is APX-complete for constant k and has strong inapproximability results.
- Decision complexity: The reduction maps a k-SETCOVER instance to a string T_C whose attractor size encodes whether a cover of size at most p exists.For constant k, T_C has length O(uk^2 + tk + t′), and the cover exists exactly when T_C has a k-attractor of size at most 4u(k −1) + p + 6t −3m.
- Decision complexity: k-ATTRACTOR is NP-complete for every k ≥3, including constant and non-constant k.The proof reduces k-SETCOVER and shows equivalent attractor-size thresholds; for constructed instances, minimum k- and k′-attractor sizes coincide for k ≤ k′ ≤ |T_C|.
- Approximation complexity: For constant k ≥3, MINIMUM-k-ATTRACTOR is APX-complete and therefore admits constant-factor approximation but no PTAS unless P=NP.The hardness proof reduces from bounded-degree vertex cover through minimum k-set cover.
- Inapproximability: For every constant ϵ >0 and every k ≥3, approximating MINIMUM-k-ATTRACTOR within 11809/11808 −ϵ is NP-hard.This rules out a PTAS under the stated complexity assumption and applies even when k is not constant.
- Approximation algorithms: Polynomial-time approximation achieves factor H(k(k + 1)/2) for k ≥3, with an improved factor H(k(k + 1)/2) −1/2 for constant k.Here H(p) denotes the p-th harmonic number; the general minimum-attractor case receives factor H(n(n + 1)/2).
5 Optimal-Time Random Access
String attractors support optimal-time random access across several dictionary-compression schemes. The paper matches an Ω(log n / log log n) lower bound with a parameterized data structure whose space-time trade-offs depend on attractor size.
- Lower bounds: The lower bound extends from SLPs because reductions provide representations in other compression schemes without larger relevant size.The extension covers string attractors, RLSLPs, collage systems, LZ77, and macro schemes.
- Lower bounds: Ω(log n / log log n) time is necessary for random access within O(α polylog n) space, where α can be several compression measures.The measures include string attractors, RLSLPs, collage systems, LZ77 parses, and macro schemes.
- Data structure: A string-attractor data structure stores O(γτ log_τ(n/γ)) words and extracts length-ℓ substrings in O(log_τ(n/γ) + ℓ log(σ)/w) time.Here γ is attractor size, τ ≥ 2 is a tunable parameter, σ is alphabet size, and w is word size.
- Data structure: The structure uses levels of context blocks around attractor positions, storing references until a final level of explicitly packed characters.Blocks are mapped to occurrences crossing attractor positions, enabling recursive extraction.
- Trade-offs: For τ = log^ε n, the structure uses O(γ polylog n) space and achieves optimal O(log(n/γ) / log log n) random-access time.For τ = (n/γ)^ε, space becomes O(γ^(1−ε)n^ε) words while query time is optimal in the packed setting.
- Trade-offs: With τ = log^ε n, optimal random access applies to string attractors, SLPs, RLSLPs, LZ77, collage systems, and macro schemes.This is stated as a corollary of the data structure and the reductions between representations.
6 Conclusions
The paper presents string attractors as a unifying theory for dictionary compression and shows that they support optimal random access across many compression schemes. It also identifies open limits in approximation quality, algorithmic efficiency, and support for more complex queries.
- Contributions: String attractors provide a common theory for known dictionary-compression techniques and support optimal random access on most of them.The conclusion connects this property to compressed computation independently of the underlying compression scheme.
- Future directions: Smallest k-attractors are proposed as a possible compressibility measure analogous to k-th order empirical entropy.The paper notes that k-attractors exhibit a similar regularity.
- Approximation landscape: LZ78 can have an Ω(√n) approximation ratio relative to the smallest attractor on unary strings, whereas LZ77 achieves an O(polylog n) ratio.These bounds motivate comparing compression algorithms by how well they approximate the smallest attractor.
- Limitations: Whether the smallest attractor admits an o(log n)-approximation in polynomial time remains open, and the presented set-cover implementation takes cubic time.The open approximation question concerns all strings.
- Future directions: The paper establishes random access for string attractors but leaves indexing and other more complex compressed queries for future work.The conclusion explicitly asks whether the attractor property suffices for indexing.
- Future directions: For minimum 3-attractors, the paper gives an approximation lower bound of 11809/11808 and an upper bound of 1.95.The complexity of 2-attractors and the optimal approximation ratio for 3-attractors remain unresolved.