  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.
