At the Roots of Dictionary Compression: String Attractors

Abstract

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\ge 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.

In Proceedings of 50th Annual ACM SIGACT Symposium on the Theory of Computing (STOC'18)

References in corpus (2)

• Time-Space Trade-Offs for Lempel-Ziv Compressed Indexing
• Representing the suffix tree with the CDAWG

Cited by in corpus (19)

• Universal Compressed Text Indexing
• Resolution of the Burrows-Wheeler Transform Conjecture
• Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space
• Optimal Construction of Compressed Indexes for Highly Repetitive Texts
• Indexing Highly Repetitive String Collections
• Near-Optimal Search Time in $\delta$-Optimal Space, and Vice Versa
• String Attractors and Combinatorics on Words
• Novel Results on the Number of Runs of the Burrows-Wheeler-Transform
• On repetitiveness measures of Thue-Morse words
• A New Class of Searchable and Provably Highly Compressible String Transformations
• Grammar Index By Induced Suffix Sorting
• Fast and Space-Efficient Construction of AVL Grammars from the LZ77 Parsing
• Contextual Pattern Matching
• Hypersuccinct Trees -- New universal tree source codes for optimal compressed tree data structures and range minima
• On the approximation ratio of LZ-End to LZ77
• A Separation of $\gamma$ and $b$ via Thue--Morse Words
• Compressed Communication Complexity of Hamming Distance
• Grammar-compressed Self-index with Lyndon Words
• LZRR: LZ77 Parsing with Right Reference