String Attractors
Nicola Prezza

arXiv:1709.05314v2 [] 19 Sep 2017

Technical University of Denmark, DTU Compute
npre@dtu.dk

Abstract. Let S be a string of length n. In this paper we introduce the notion of string attractor : a
subset of the string’s positions [1, n] such that every distinct substring of S has an occurrence crossing
one of the attractor’s elements. We first show that the minimum attractor’s size yields upper-bounds
to the string’s repetitiveness as measured by its linguistic complexity and by the length of its longest
repeated substring. We then prove that all known compressors for repetitive strings induce a string
attractor whose size is bounded by their associated repetitiveness measure, and can therefore be considered as approximations of the smallest one. Using further reductions, we derive the approximation
ratios of these compressors with respect to the smallest attractor and solve several open problems related to the asymptotic relations between repetitiveness measures (in particular, between the the sizes
of the Lempel-Ziv factorization, the run-length Burrows-Wheeler transform, the smallest grammar, and
the smallest macro scheme). These reductions directly provide approximation algorithms for the smallest string attractor. We then apply string attractors to solve efficiently a fundamental problem in the
field of compressed computation: we present a universal compressed data structure for text extraction
that improves existing strategies simultaneously for all known dictionary compressors and that, by
recent lower bounds, almost matches the optimal running time within the resulting space. To conclude,
we consider generalizations of string attractors to labeled graphs, show that the attractor problem is
NP-complete on trees, and provide a logarithmic approximation computable in polynomial time.

1

Introduction

Being able to determine the level of repetitiveness of a string is of critical importance in areas such
as computational biology, data compression, stringology, and cryptography. In biology, genome repetitions often indicate the presence of transposable elements and represent an important source of
genetic variation. In data compression and stringology, repetitions are exploited to represent the
string in a more compact form and to study properties such as periodicity and maximal repeats.
In cryptography, repetitions in pseudo-random generators or in the encrypted messages should be
avoided as they can produce easier-to-break codes. Typical definitions of repetitiveness either look
at the string’s composition in terms of distinct k-mers or rely on the output of particular compressors. An example of the former case is linguistic complexity [34, 35]: the rate between the number
of distinct substrings and the maximum number of distinct substrings that can appear in a string
of the same length on the same alphabet. The linguistic complexity of a string is of relevance in
computational biology, where is often used to determine the complexity of a genome [34,35]. Despite
intuitively capturing the degree of repetitiveness of a string, however, linguistic complexity does
not tell us anything about how repetitions could be used to remove redundancy from the string.
More empirical definitions—mostly used in the realms of data compression and stringology—define
a string to be repetitive when its compressed representation is small when compared to the string’s
original size. Despite being intuitive (although somewhat circular), this definition presents an important issue: the landscape of data compression is composed of myriads of different compressors
for repetitive strings—each coming with its distinct repetitiveness measure—so it is not always
clear which one should be used given a particular string. One effective compression strategy of this

kind is, for example, to build a context-free grammar that generates only the string. The grammar
takes the name of Straight Line Program (SLP) if all rules have the form X → AB, or run-length
SLP (RLSLP) if also rules of the form X → Aℓ are allowed, for any ℓ > 2. The problems of finding
∗ —are NP-complete [19],
the smallest SLP—of size g∗ —and the smallest run-length SLP—of size grl
but fast and effective approximation algorithms are known, e.g. LZ78 [37], LZW [36], Re-Pair [22],
Bisection [20]. Another strategy, more powerful than grammar compression, is that of replacing
repetitions with pointers to other locations in the string. The most powerful and general scheme
falling into this category takes the name of pointer macro scheme [33], and consists in a set of
substring equalities that allow to unambiguously reconstruct the string. Finding the smallest such
system—of size b∗ —is also NP-complete [18]. However, if we add the constraint of unidirectionality
(i.e. text can only be copied from previous positions), then the optimal such scheme [23] of size z can
be computed in linear time [14] with a greedy algorithm known as LZ77. Other effective techniques
to compress repetitive strings include the run-length Burrows-Wheeler transform [11] (RLBWT)
and the Compact Directed Acyclic Word Graph [9,15] (CDAWG). With the first technique, we sort
all circular string permutations in a n × n matrix; the BWT is the last column of this matrix. The
BWT contains few equal-letter runs if the string is very repetitive, therefore run-length compression often significantly reduces the size of this string permutation [25]. The number r of runs in the
BWT is yet another good measure of repetitiveness. Finally, one could build an automaton recognizing the string’s suffixes, and indicate with e its number of edges. Also the size e∗ of the smallest
such automaton—the CDAWG—grows sublinearly with n if the string is very repetitive [6]. Both
RLBWT and CDAWG can be computed in linear time [4,16,26,27]. Few relations are known among
these measures. Rytter [32] proved that g∗ ∈ O(z log(n/z)) by showing a reduction from grammars
to unidirectional parses, and Belazzogui et al. [5, 6] showed that g∗ , z, r ∈ O(e∗ ). In practice, e∗ is
much larger (by about one order of magnitude) than the other repetitiveness measures [6].
At this point, it is natural to ask the following questions: what common principle—if any—
stands at the basis of these compressors? how is the compressed string’s size related with the
string’s linguistic complexity? In this paper, we propose an answer to these questions. We introduce
the notion of string attractor : a set of the string’s positions such that all distinct substrings have
an occurrence crossing one of the attractor’s elements. We show an upper-bound to the string’s
linguistic complexity and a lower bound on the length of the longest repeated substring as a
function of the smallest attractor size for that string: in particular, a smaller attractor implies
a more repetitive string. We furthermore prove that these combinatorial objects are a natural
generalization of all known compressors for repetitive strings: grammars, LZ77, macro schemes,
RLBWT, and automata recognizing the string’s suffixes (e.g. the CDAWG and the suffix tree)
induce string attractors whose sizes are bounded by their associated repetitiveness measures, and
can therefore be interpreted as approximations of the smallest one. We provide techniques to derive
a macro scheme and a grammar from any string attractor, and use these reductions to derive the
approximation rates of the above compressors with respect to the smallest string attractor. Using
the same techniques, we moreover uncover new relations between repetitiveness measures: we show
that g ∗ , z ∈ O(b∗ log2 (n/b∗ )) and g ∗ , z ∈ O(r log2 (n/r)), thus providing the first bounds relating
these measures and solving an open problem explicitly stated in [31].
After introducing and studying the properties of string attractors, we present an application
of these combinatorial objects to the domain of compressed data structures. We start by noticing
that our conversion technique yielding a macro scheme implies that only a logarithmic blow-up in
space is needed to reconstruct the string from a string attractor. Indeed, we show that this property
2

can be turned into a very efficient data structure—we call it A-DAG (Attractor Directed Acyclic
Graph)—for text extraction. Thanks to the universality of string attractors, this technique can be
used verbatim to extract text from any compressed representation within a space bounded by a
(small) function of its associated repetitiveness measure. Let γ be the size of a string attractor of
a length-n string T over an alphabet [1 . . . , σ]. For any τ > 0, the A-DAG takes O(γτ logτ (n/γ))
words of space and supports the extraction of any length-ℓ substring of T in O(logτ (n/γ)+ℓ log σ/w)
time. On one side, we obtain the first data structure supporting efficient random access on general
macro schemes. In general, the A-DAG is faster than existing text-extraction data structures for
all known repetitiveness measures (by our reductions, it is sufficient to replace γ with z, b, g, grl ,
r, or e in the above bounds). Moreover, a recent lower bound [12] implies that our query times
for τ = logǫ (n/γ) (for any small ǫ > 0) are very close to the optimum within the resulting space.
Another interesting tradeoff is achieved choosing τ = (n/γ)ǫ for any constant ǫ > 0: in this case, we
obtain optimal O(ℓ log(σ)/w) extraction time in the packed setting within O(γ 1−ǫ nǫ ) space. This
space is a weighted geometric average between the compressed and plain string sizes, is always at
most O(n), and is o(n) if γ = o(n), i.e. if the string is asymptotically compressible.
In our last section we propose a generalization of string attractors to labeled directed graphs
capturing all distinct paths (interpreted as strings) in the graph. We show that the decisional version
of the path attractor problem is NP-complete on labeled trees, and provide a polynomial-time
logarithmic approximation based on a reduction to the set-cover problem. We conclude the paper
by proposing several exciting open problems that naturally follow from our work, and discussing
new research directions that could lead to a better understanding of the notion of repetitiveness.
Proof omitted within the first 12 pages are reported in Appendix A due to space limitations.

2

Preliminaries

−
When s is a string, the notation ←
s denote s reversed. For space reasons, we assume the reader
to be familiar with the notions of Lempel-Ziv factorization [23], Burrows-Wheeler transform [11],
run-length encoding, Compact Directed Acyclic Word Graph [9,15] (CDAWG), and grammar compression [19]. In this paper we consider the version of the Lempel-Ziv factorization [23] (LZ77 for
short) without self-references and without trailing characters.
A macro scheme [33] is a set of b directives of two possible types:
– T [i..j] ← T [i′ ..j ′ ] (i.e. copy T [i′ ..j ′ ] in T [i..j]), or
– T [i] ← c, with c ∈ Σ (i.e. assign character c to T [i]).
such that the text can be unambiguously reconstructed from the directives.
A bidirectional parse is a macro scheme where the left-hand sides of the directives induce a text
factorization, i.e. they cover the whole T and they do not overlap. Note that LZ77 is a particular
case of bidirectional parse (in particular, it is the optimal unidirectional one), and therefore is also
a particular macro scheme.
The height of a macro scheme is defined as follows. Let i be a string position. If i is an explicitly
stored character, we define the character height hi of i to be equal to 1. Otherwise, let j be the
position from where T [i] is copied according to the macro scheme. Then, we define the character
height hi of i to be hi = hj + 1. The macro scheme height h is defined as the maximum character
height h = max1≤i≤n hi .
3

3

String attractors

A string S[1..n] is considered to be repetitive when the cardinality of the set SU BS = {S[i..j] | 1 ≤
i ≤ j ≤ |S|} of its distinct substrings is much smaller than the maximum number of distinct
substrings on a text of the same length on the same alphabet. In the domain of data compression, a more relevant quantification γ of the string’s repetitiveness should, however, also provide
a meaningful way of representing SU BS within a space proportional to γ so that S itself can be
reconstructed from this representation. In this respect, SU BS itself provides the “ideal” quantification of repetitiveness, but it is useless in practice as its size could be quadratic in S. As a
result of these requirements, typical definitions of repetitiveness tend to be circular in the sense
that rely on particular compressors such as the Lempel-Ziv factorization, straight-line programs, or
the run-length Burrows-Wheeler transform. In other words, a string S is usually considered to be
repetitive when the size of its compressed representation is small when compared to the worst-case
entropy of the set of all length-n strings on the same alphabet (n log σ bits). In this section, we
tackle the problem from the opposite direction: we first give a more “principled” definition of string
repetitiveness that naturally follows from the definition of SU BS , and show that it directly relates
with the number of distinct substrings. We then show that all known dictionary compressors are
a particular case of our notion of repetitiveness, and show how our perspective of the problem
can be exploited to uncover new properties of dictionary compressors and solve more efficiently
data-structure problems related to them. Our idea is the following: we fix a set of γ positions on S
so that every element of SU BS has an occurrence crossing one of these positions, and claim that
the size γ ∗ of the smallest such set is a meaningful notion of string repetitiveness. We call the set
of such positions string attractor :
Definition 1. A string attractor of a string T ∈ Σ n is a set of γ positions Γ = {j1 , ..., jγ } such
that every substring T [i..j] has an occurrence T [i′ ..j ′ ] = T [i..j] with jk ∈ [i′ , j ′ ], for some jk ∈ Γ .
Example 1. Note that {1, 2, .., n} is always a string attractor (the biggest one) for any string. Note
also that this is the only possible string attractor for a string composed of n distinct characters.
Example 2. Consider the following string S, where we underlined the positions of a smallest string
attractor Γ ∗ = {4, 7, 11, 12} of S.
CDABCCDABCCA
To see that Γ ∗ is a valid attractor, note that every substring between attractor’s positions has
an occurrence crossing an attractor position (these substrings are A,B,C,D,CD,DA,AB,CC). The remaining substrings cross an attractor position by definition. To see that Γ ∗ is the smallest attractor
for S, note that the alphabet size is σ = 4 = |Γ ∗ |, and any attractor Γ must satisfy |Γ | ≥ σ.
Clearly, the set Γ alone is not sufficient to reconstruct the original string as we do not even
store characters associated with those positions. However, in Theorem 6 we will show that only a
logarithmic blow-up in space is needed to achieve this task. For now, we stress out that the size
γ ∗ of the smallest string attractor and the string’s repetitiveness are two closely-related concepts.
First, we show an upper-bound to the number of distinct k-mers.
Lemma 1. Let Γ be a string attractor of size γ for S. Then, S contains at most γk distinct k-mers,
for every 1 ≤ k ≤ |S|.
4

Proof. By the attractor’s definition, every distinct k-mer appearing in the string has an occurrence
crossing some attractor’s position. It follows that, in order to count the number of distinct k-mers,
we can restrict our attention to the regions of size 2k − 1 overlapping the attractor’s positions. The
upper-bound γk easily follows.
⊔
⊓
From the above lemma, we directly obtain:
P
Theorem 1. |SU BS | ≤ nk=1 min{σ k , n − k + 1, γ ∗ k}
The linguistic complexity LC(S)
a string S ∈ [1, σ]n , as defined in [35], is the rate between
Pof
n
|SU BS | and the maximum number k=1 min{σ k , n−k +1} of distinct substrings that could appear
in a string from [1, σ]n . LC(S) is often used as an index of string repetitiveness. Theorem 1 yields
an upper- bound for LC(S) as a function of γ ∗ .
Example 3. For the string S in example 2, we have n = 12, σ = 4, γ ∗ = 4, and |SU BS | = 57. Then,
LC(S) ≈ 0.814 and Theorem 1 gives the bound LC(S) ≤ 0.9572.
The length ℓmax of the longest repeated substring is also indicative of the string’s repetitiveness. In the following lemma we show that a smaller minimum attractor implies a larger ℓmax .
Equivalently, we give a lower-bound on the size of the minimum attractor as a function of ℓmax .
Lemma 2. Let S ∈ [1, σ]n be a string with minimum attractor’s size γ ∗ and longest repeated
∗
n−ℓmax
∗
substring’s length equal to ℓmax . Then, it holds ℓmax ≥ n−γ
γ ∗ +1 and, equivalently, γ ≥ ℓmax +1 .
Proof. Consider the maximum distance j −i between any two positions i, j in the smallest attractor
for S. Then, by Definition 1, the substring S[i + 1..j − 1] of length j − i − 1 between these two
positions is not covered by any attractor’s element. This means that S[i + 1..j − 1] must have
another occurrence crossing some other attractor element, which implies that it is repeated. The
smallest maximum distance between the γ ∗ attractor’s elements is obtained when they are equally
spaced. The claim easily follows after observing that the repeated substring should not cross any
attractor’s element (n − γ ∗ positions are therefore left), and the γ ∗ elements break the text in γ ∗ + 1
factors.
⊔
⊓
3.1

Reductions from compressors

In the next theorems we show reductions from all known compressors for repetitive strings to string
attractors. We start with a well-known lemma that will be used later:
Lemma 3. Let G = {Xi → Ai Bi , i = 1, ..., g′ } ∪ {Yi → Ziℓi , ℓi ≥ 2, i = 1, ..., g′′ } be a run-length
grammar generating T ∈ Σ n . For any substring T [i..j] one of the following is true:
1. there exists a rule Xk → Ak Bk such that T [i..j] is composed of a non-empty suffix of the
expansion of Ak followed by a non-empty prefix of the expansion of Bk , or
2. there exists a rule Yk → Zkℓk such that T [i..j] is composed of a non-empty suffix of the expansion
of Zk followed by a non-empty prefix of the expansion of Zkℓk −1
Note that if the grammar does not allow run-length rules, then (1) must always be true for any
substring.
5

Theorem 2. Let G = {Xi → Ai Bi , i = 1, ..., g ′ } ∪ {Yi → Ziℓi , ℓi ≥ 2, i = 1, ..., g ′′ } be a run-length
grammar of size g = g ′ + g′′ generating T . G induces a family of string attractors, all of size g.
Proof. Start with an empty string attractor ΓG = ∅, and repeat the following for k = 1, ..., g′ .
Choose any of the expansions T [i..j] of Xk . By the production Xk → Ak Bk , T [i..j] can be factored
as T [i..j] = T [i..i′ ]T [i′ +1..j], where T [i..i′ ] and T [i′ +1..j] are expansions of Ak and Bk , respectively.
Insert position i′ in ΓG .
Now, repeat the following for k = 1, ..., g ′′ . Choose any of the expansions T [i..j] of Yk . By the
production Yk → Zkℓk , T [i..j] can be factored as T [i..j] = T [i..i′ ]T [i′ + 1..j], where T [i..i′ ] and
T [i′ + 1..j] are expansions of Zk and Zkℓk −1 , respectively. Insert position i′ in ΓG .
To see that ΓG is a valid string attractor of size g, consider any substring T [i..j]. By Lemma
3, T [i..j] has an occurrence T [i′ ..j ′ ] spanning the expansion of some Ak |Bk or of some Zk |Zkℓk −1 ,
where we highlighted with a vertical bar the crossing point. By the way we constructed ΓG , this
prefix/suffix decomposition of T [i′ ..j ′ ] crosses (with the same split) one of the elements in ΓG (i.e.
⊔
⊓
the one associated with production Xk → Ak Bk or Yk → Zkℓk ).
Clearly, Theorem 2 applies also to grammars not allowing run-length rules: in this case, g ′′ = 0
and g = g′ . Note that the theorem captures also LZ78, Lempel-Ziv Welch (LZW), and run-length
encoding (since they are just particular grammars). We now show that also macro schemes are
particular string attractors.
Theorem 3. Let MS be a macro scheme of size b of T . MS induces a string attractor ΓM S of size
at most 2b.
Proof. Let T [ik1 ..jk1 ] ← T [i′k1 ..jk′ 1 ], T [qk2 ] ← ck2 , with 1 ≤ k1 ≤ b1 , 1 ≤ k2 ≤ b2 , and b = b1 + b2 be
the b directives of our macro scheme MS. We claim that ΓM S = {i1 , . . . , ib1 , j1 , . . . , jb1 , q1 , . . . , qb2 }
is a valid string attractor for T .
Let T [i..j] be any substring. All we need to show is that T [i..j] has a primary occurrence, i.e. an
occurrence containing one of the positions ik1 , jk1 or qk2 . Let i1 = i and j1 = j. Consider all possible
chains of copies (following the macro scheme directives) T [i1 ..j1 ] ← T [i2 ..j2 ] ← T [i3 ..j3 ] ← ... that
either end in some primary occurrence T [ik ..jk ] or are infinite (note that there could exist multiple
chains of this kind since the left-hand side terms of some macro scheme’s directives could overlap).
Our goal is to show that there must exist at least one finite such chain, i.e. that ends in a primary
occurrence. Pick any i1 ≤ p1 ≤ j1 . Since ours is a valid macro scheme, then T [p1 ] can be retrieved
from the scheme, i.e. the directives induce a finite chain of copies T [p1 ] ← ... ← T [pk′ ] ← c, for
some k′ , such that T [pk′ ] ← c is one of the macro scheme’s directives. We now show how to build a
finite chain of copies T [i1 ..j1 ] ← T [i2 ..j2 ] ← ... ← T [ik ..jk ] ending in a primary occurrence T [ik ..jk ]
of T [i1 ..j1 ], with k ≤ k′ . By definition, the assignment T [p1 ] ← T [p2 ] comes from some macro
scheme’s directive T [l1 ..r1 ] ← T [l2 ..r2 ] such that p1 ∈ [l1 , r1 ] and p1 − l1 = p2 − l2 (if there are
multiple directives of this kind, pick any of them). If either l1 ∈ [i1 , j1 ] or r1 ∈ [i1 , j1 ], then T [i1 , j1 ]
is a primary occurrence and we are done. Otherwise, we set i2 = l2 + (i − l1 ) and j2 = l2 + (j − l1 ).
By this definition, we have that T [i1 ..j1 ] = T [i2 ..j2 ] and p2 ∈ [i2 , j2 ], therefore we can extend our
chain to T [i..j] ← T [i2 ..j2 ]. It is clear that the reasoning can be repeated, yielding that either
T [i2 ..j2 ] is a primary occurrence or our chain can be extended to T [i..j] ← T [i2 ..j2 ] ← T [i3 ..j3 ] for
some substring T [i3 ..j3 ] such that p3 ∈ [i3 , j3 ]. We repeat the construction for p4 , p5 , ... until either
(i) we end up in a chain T [i..j] ← ... ← T [ik ..jk ], with k < k′ , ending in a primary occurrence
T [ik ..jk ] of T [i1 ..j1 ], or (ii) we obtain a chain T [i1 ..j1 ] ← ... ← T [ik′ ..jk′ ] such that pk′ ∈ [ik′ , jk′ ]
6

(i.e. we consume all the p1 , . . . , pk′ ). In case (ii), note that T [pk′ ] ← c is one of the macro scheme’s
⊔
⊓
directives, therefore T [ik′ ..jk′ ] is a primary occurrence of T [i1 ..j1 ].
Since LZ77 is a particular case of macro scheme, we obtain that it induces a string attractor
of size at most 2z. We can achieve a better bound by exploiting the so-called primary occurrence
property of LZ77:
Lemma 4. The Lempel-Ziv factorization of size z of a string T induces a string attractor ΓLZ77
of size at most z.
Proof. We insert in ΓLZ77 all positions at the end of a phrase. It is well known (see, e.g. [21])
that every text substring has an occurrence crossing a phrase border (these occurrences are usually
known as primary), therefore we obtain that ΓLZ77 is a valid attractor for T .
⊔
⊓
The run-length Burrows-Wheeler transform seems a completely different paradigm for compressing repetitive strings: while with grammars and macro schemes we copy substrings around in
the string, with the RLBWT we build a string permutation by concatenating characters preceding
lexicographically-sorted suffixes, and then run-length compress it. This strategy is motivated by the
fact that similar substrings (adjacent in the lexicographic order) are often preceded by the same
character, therefore the BWT contains long runs of the same letter if the string is repetitive [25].
We denote with r the number of equal-letter runs in the BWT. The following theorem holds (we
use a technique originally developed in [28, 29, 30] to get our bound):
Theorem 4. Let r be the number of equal-letter runs in the Burrows-Wheeler transform BW T (T )
of a string T . BW T (T ) induces a string attractor ΓRLBW T of size at most 2r.
Proof. We insert in ΓRLBW T all positions i such that T [i] is the first or last character in its BWT
equal-letter run. The size of ΓRLBW T is at most 2r (less if there are runs of length 1). We now show
that ΓRLBW T is a valid string attractor.
Consider any substring T [i..j]. We want to show that T [i..j] has an occurrence T [i′ ..j ′ ] = T [i..j]
crossing an element in ΓRLBW T . We prove the theorem by induction on j − i. If j − i = 0, then
T [i..j] is a single character. Since we pick the first and last position of each BWT run, each character
appears in at least one attractor position, and the thesis easily follows.
Let j − i > 0. By the inductive hypothesis, T [i + 1..j] has an occurrence T [i′ + 1..j ′ ] crossing
an attractor element i′ + 1 ≤ p ≤ j ′ . Let [sp, ep] be the BWT range of T [i + 1..j]. We distinguish
two cases.
(i) All characters in BWT [sp, ep] are equal to T [i] = T [i′ ]. Then, T [i′ ..j ′ ] is an occurrence of
T [i..j] crossing the attractor element p.
(ii) BWT [sp, ep] contains at least one character c 6= T [i]. Then, there must be a run of T [i]’s
ending or beginning in BWT [sp, ep], meaning that there is a sp ≤ q ≤ ep such that BWT [q] = T [i]
and the position p corresponding to q belongs to ΓRLBW T . Then, T [p..p + (j − i)] is an occurrence
of T [i..j] crossing the attractor element p.
⊔
⊓
To conclude, any path-compressed automaton recognizing the string’s suffixes also induces a
string attractor of the same size.
Theorem 5. Let e be the number of edges of a path-compressed automaton A recognizing all (and
only the) substrings of a string T . A induces a family of string attractors, all of size e.
7

Proof. We call root the starting state of A. Start with empty ΓA . For every edge (u, v) of A, do
the following. Let T [i..j] be any occurrence of the substring read from the root of A to the first
character in the label of (u, v). We insert j in ΓA .
To see that ΓA is a valid string attractor of size e, consider any substring T [i..j]. By definition
of A, T [i..j] defines a path from the root to some node u, plus a prefix of the label (possibly,
all the characters of the label) of an edge (u, v) exiting from u. Let T [i..k], k ≤ j, be the string
read from the root to u, plus the first character in the label of (u, v). Then, by definition of ΓA
there is an occurrence T [i′ ..k′ ] = T [i..k] such that k′ ∈ ΓA . Since the remaining (possibly empty)
suffix T [k + 1..j] of T [i..j] ends in the middle of an edge, every occurrence of T [i..k] is followed by
T [k + 1..j], i.e. T [i′ ..i′ + (j − i)] is an occurrence of T [i..j] crossing the attractor element k′ .
⊔
⊓
The Compact Directed Acyclic Word Graph, of size e∗ , is the smallest automaton recognizing
all string’s suffixes.
To conclude the section note that the above reductions, in conjunction with Theorems 1 and
2, give the first known upper-bound to the linguistic complexity LC(S) and lower bound to the
length ℓmax of the longest repeated substring of a string S as a function of the output size of any
dictionary compressor.
3.2

Reductions to compressors

In this section we derive upper bounds on the approximation rates of some compressors for repetitive
strings with respect to the smallest string attractor. We then use these bounds and the reductions
of the previous section to uncover new relations between known repetitiveness measures. The next
property follows easily from Definition 1 and will be used in the proofs of the following theorems.
Lemma 5. Any superset of a string attractor is also a string attractor.
We now show that we can derive a bidirectional parse from a string attractor.
Theorem 6. Given a string T ∈ Σ n and a string attractor Γ of size γ for T , we can build a
bidirectional parse for T of size O(γ log(n/γ)).
In the next theorem we show how to derive a SLP from a string attractor.
Theorem 7. Given a string T ∈ Σ n and a string attractor Γ of size γ for T , we can build a SLP
for T of size O(γ log2 (n/γ)).
Using the above theorems, we can derive the approximation rates of some compressors for
repetitive strings with respect to the smallest string attractor.
∗ of
Corollary 1. The following bounds hold between the size g ∗ of the smallest SLP, the size grl
the smallest run-length SLP, the size z of the Lempel-Ziv parse without self-references, the size b∗
of the smallest macro scheme, and the size γ ∗ of the smallest string attractor:

1. b∗ ∈ O(γ ∗ log(n/γ ∗ ))
∗ , z ∈ O(γ ∗ log2 (n/γ ∗ ))
2. g∗ , grl
Proof. For the first bound, build the bidirectional parse of Theorem 6 using a string attractor of
minimum size γ ∗ . For the second bound, use the same attractor to build the SLP of Theorem 7
and exploit the well-known relation z ≤ g ∗ [32]. The result follows from the definitions of smallest
macro scheme and smallest SLP.
⊔
⊓
8

Combining the reductions of Section 3.1 with the results stated in Corollary 1, we obtain approximation algorithms for the smallest string attractor. Note that only one of our approximations,
however, is computable in polynomial time (unless P=NP): the attractor induced by the LempelZiv factorization. This algorithm computes a O(log2 (n/γ ∗ ))-approximation. In Section 5 we show
how to compute a (ln n)-approximation of the smallest string attractor in O(n2 ) time.
Combining the construction of Theorem 7 with the reductions of Theorems 2 and 3 we obtain
the following new relations between repetitiveness measures:
Corollary 2. The following bounds hold between the size g ∗ of the smallest SLP, the size b∗ of the
smallest macro scheme, and the number r of equal-letter runs in the BWT:
1. g∗ ∈ O(b∗ log2 (n/b∗ ))
2. g∗ ∈ O(r log2 (n/r))
Proof. For bound 1, build the SLP of Theorem 7 on a string attractor of size b∗ induced from
the smallest macro scheme (Theorem 3). Do the same, but using the attractor induced from the
RLBWT (Theorem 4), for bound 2. The results follows from the definition of smallest SLP.
⊔
⊓
Note that, using the well-known relation z ≤ g∗ for the size z of the Lempel-Ziv parse without
self-references [32], we also obtain:
Corollary 3. The following bounds hold between the size z of the Lempel-Ziv parse without selfreferences, the size b∗ of the smallest macro scheme, and the number r of equal-letter runs in the
BWT:
1. z ∈ O(b∗ log2 (n/b∗ ))
2. z ∈ O(r log2 (n/r))
The first relation shows that the size of the smallest unidirectional parse without self-references—
which can be computed in linear time—is at most a polylogarithmic factor larger than the smallest
macro scheme—which is NP-hard to find. The second bound is the first to relate the size of LZ77
with that of the RLBWT 1 , and solves an open problem explicitly stated in [31].

4

Applications: a universal compressed data structure for text extraction

The problem of efficiently extracting substrings from compressed text representations has lately
received a lot of attention in the field of compressed computation. On one side, the following lower
bound is known to hold for grammar-compressed text [12]: Ω((log n)1−ǫ / log g) time is needed to
access one random position within O(poly(g)) space, for every constant ǫ > 0. As long as upperbounds are concerned, several data structures have been proposed in the literature for each distinct
compression scheme. In Table 1 we report the best time-space trade-offs known to date, grouped
by compression scheme (horizontal lines). Extracting text from Lempel-Ziv compressed text is a
notoriously difficult problem. No efficient solution exists within O(z) space (they all require time
proportional to the parse’s height), although efficient queries can be supported by raising the
space by a logarithmic factor [2, 7]. Grammars, on the other hand, allow for more compact and
1

We are aware that the same bounds have been derived simultaneously by Gagie et al. [17] (work not yet published)
using very different techniques based on locally-consistent parsing.

9

time-efficient extraction strategies. Bille et al. [8] have been the first to show how to efficiently
perform text extraction within O(g) space. Their time bounds were later improved by Belazzogui
et al. [3], who also showed how to slightly increase the space to O(g logǫ n log(n/g)) while almost
matching the lower bound [12] in the packed setting. Space-efficient text extraction from the runlength Burrows-Wheeler transform has been an open problem until recently. Standard solutions [24]
required to spend additional O(n/s) space on top of the RLBWT in order to support extraction
in a time proportional to s. In a recent publication, Gagie et al. [17] showed how to achieve nearoptimal extraction time in the packed setting within O(r log(n/r)) space. Belazzogui and Cunial [1]
showed how to efficiently extract text from a CDAWG-compressed text. Their most recent work [5]
shows moreover how to build a grammar of size O(e): this result implies that the same bounds for
grammar-compressed text apply to the CDAWG. To conclude, no strategy for efficiently extracting
text from general macro schemes is known to date: the only solution we are aware of requires to
explicitly navigate the macro scheme’s directives, and requires therefore time proportional to the
parse’s height.
Space
Extract time
Structure
Bille et al. [7, Lem. 5]
O(z log(n/z))
O(ℓ + log(n/z))
Gagie et al. [2, Thm. 2]
O(z log(n/z))
O((1 + ℓ/ logσ n) log(n/z))
Belazzougui et al. [3, Thm. 1]
O(g)
O(ℓ/ logσ n + log n)
Belazzougui et al. [3, Thm. 2]
O(g logǫ n log(n/g)) O(ℓ/ logσ n + log n/ log log n)
Gagie et al. [17, Thm. 2]
O(r log(n/r))
O(ℓ log(σ)/w + log(n/r))
Belazzougui and Cunial [1, Thm. 1]
O(e)
O(ℓ + log n)

Table 1: Best trade-offs in the literature for extracting text from compressed representations.

Extract time
O(ℓ
log(σ)/w)


O (γ log ǫ n log(n/γ)) O ℓ log(σ)/w + log(n/γ)
log log n



O γ log1+ǫ (n/γ)
O ℓ log(σ)/w + loglog(n/γ)
log(n/γ)
Space
O(γ 1−ǫ nǫ )

O (γ log(n/γ))

O(ℓ log(σ)/w + log(n/γ))

Table 2: Some interesting trade-offs achievable with the A-DAG of Theorem 8, in order of decreasing
space and increasing time.
In this section, we show that the powerful abstraction offered by string attractors can be used to
efficiently extract text from any dictionary-compressed representation. We describe a parametrized
data structure—the Attractor Directed Acyclic Graph, or A-DAG for short—offering a range of
different space-time trade-offs. Our main result is stated in Theorem 8. Table 2 reports some
interesting space-time trade-offs achievable with our data structure. To compare the bounds of
Tables 1 and 2, just replace γ with any of the measures z, g, r, e, b (possible by the reductions
described in Section 3.1). On one extreme of the parameter space, we achieve optimal extraction
time in the packed setting. Interestingly, this is achieved within a space—O(γ 1−ǫ nǫ ) words—that is
always O(n) (since γ ≤ n) and is o(n) if the string is asymptotically compressible (i.e. if γ = o(n)).
By the lower bound [12], Ω((log n)1−ǫ / log g) time is needed to access one random position within
O(poly(g)) space on grammar-compressed strings, for every constant ǫ > 0. Since g ∈ Ω(log n),
10

the space in lines 2 and 3 of Table 2 is O(poly(g)) on grammar-induced attractors, and extraction
time therefore almost matches the optimum. Moreover, since string attractors are more general than
grammars, these trade-offs are close to the optimum also for general string attractors. Note also that
the time in line 2 of Table 2 is strictly better than that of Line 4 in Table 1 (while the two solutions
use the same space) and is optimal in the packed setting for polynomial compression rates, i.e. n/γ ∈
polylog(n). The A-DAG is, in general, faster than all existing extraction strategies for grammars,
LZ77, Burrows-Wheeler transform, and CDAWG described in Table 1. Our solution is, moreover,
the first supporting fast extraction on general macro schemes. The A-DAG is a generalization of a
data structure proposed very recently by Gagie et al. [17] for extracting text compressed with the
RLBWT.
Theorem 8. Let T [1..n] be a string over alphabet [1..σ], and let Γ be a string attractor of size γ
for T . For any integer parameter τ ≥ 2, we can store a data structure—the A-DAG of hT, Γ i—of
O(γτ logτ (n/γ)) words supporting the extraction of any length-ℓ substring of T in O(logτ (n/γ) +
ℓ log(σ)/w) time.

5

Generalizations to labeled graphs

In this section we propose a generalization of string attractors to labeled directed graphs capturing
all distinct paths (interpreted as strings) in the graph.
In the following, G = hV, E, δi denotes an edge-labeled directed graph with nodes from V , edges
from E ⊆ V × V , and labeling function δ : E → Σ.
Definition 2. A path attractor of G is a set of edges Γ ⊆ E such that for every path v1 . . . vk
′ i) for i = 1, . . . , k − 1 and
of G there exists a path v1′ . . . vk′ such that δ(hvi , vi+1 i) = δ(hvi′ , vi+1
′
′
hvj , vj+1 i ∈ Γ for some 1 ≤ j < k.
Note that Definition 2 is equivalent to Definition 1 when G is a path graph. We now study the
complexity of determining whether a graph has a path attractor of some fixed size k.
Definition 3. Path attractor problem
– Input:
hG, ki, where G is a labeled graph and k ≥ 1 is an integer
– Question: Does G have a path attractor of size at most k?
Lemma 6. The path attractor problem is NP-hard
Proof. The idea is to show a reduction from set-cover to the path attractor problem. The reduction
is obtained by converting the t sets of the set-cover instance to t tries built using the binary
representations of the elements in the sets, and observing that a path attractor on these trees
corresponds to a cover of the universe in the set-cover instance (and vice-versa). See Appendix A
for full formal proof.
Lemma 7. The path attractor problem belongs to NP when G is a tree
Proof. The number of distinct paths in a labeled tree with n nodes is clearly polynomial in n, so
it takes polynomial time to verify that the edges of a given path attractor intersect at least one
occurrence of all distinct paths in the tree.
⊔
⊓
11

Since in Lemma 6 the graph G is a labeled tree, Lemmas 6 and 7 imply the following:
Theorem 9. The path attractor problem is NP-complete on labeled trees
In the following theorem we show how to compute a logarithmic approximation of the smallest
path attractor when the graph is a labeled tree.
Theorem 10. If G = hV, E = {e1 , . . . , en }i is a labeled tree, we can compute a (ln n)-approximation
of the smallest path attractor of G in O(n2 ) time.
When G is a string (i.e. a path graph), Theorem 10 yields a string attractor of size γ ∗ ln n
computable in O(n2 ) time. Note that we already provided a logarithmic approximation of the
smallest string attractor in the previous section by showing that b∗ ∈ O(γ ∗ log(n/γ ∗ )) (Corollary
1). However, finding the smallest macro scheme is a NP-complete [18] problem, so Theorem 10 is
our first polynomial-time algorithm computing such an approximation.

6

Conclusions

We introduced a new combinatorial object—the string attractor—that generalizes all known compressors for repetitive strings and is related with the notion of string’s repetitiveness. We proved
that the smallest attractor problem becomes NP-complete when generalized to labeled trees, and
described several approximation algorithms. In particular, the smallest path attractor on trees (and,
in particular, the smallest string attractor) can be approximated within a factor ln n in O(n2 ) time,
and the smallest string attractor of size γ ∗ can be approximated within a factor O(log2 (n/γ ∗ ))
in O(n) time. We moreover used these combinatorial objects to uncover new relations between
repetitiveness measures of string compressors and to obtain a universal compressed data structure
for text extraction.
Our paper leaves many exciting open problems. In particular: determining the computational
complexity of the smallest string attractor problem, finding better approximation algorithms for
the smallest string/path attractor, deriving new relations between repetitiveness measures using
the techniques here developed, and deriving better bounds for the linguistic complexity of a string
as a function of the size of its smallest attractor. Finally, note that path attractors capture all
sequences of labels in a graph, but do not take into account the graph topology. A possible, more
powerful, extension could be the that of considering a set Γ of graph’s edges such that every distinct
connected subgraph has an isomorphic occurrence crossing one of the elements in Γ .
Acknowledgements I would like to thank Alberto Policriti for many fruitful discussions on the
topic. Thanks also to Gonzalo Navarro, Travis Gagie, Philip Bille, Inge Li Gørtz, Mikko Berggren
Ettienne, and Anders Roy Christiansen for many constructive suggestions.

References
1. D. Belazzougui and F. Cunial. Fast label extraction in the CDAWG. In Proc. 24th International Symposium on
String Processing and Information Retrieval (SPIRE), 2017. To appear.
2. D. Belazzougui, T. Gagie, P. Gawrychowski, J. Kärkkäinen, A. Ordóñez, S. J. Puglisi, and Y. Tabei. Queries on
LZ-bounded encodings. In Proc. 25th Data Compression Conference (DCC), pages 83–92, 2015.
3. D. Belazzougui, S. J. Puglisi, and Y. Tabei. Access, rank, select in grammar-compressed strings. In Proc. 23rd
Annual European Symposium on Algorithms (ESA), LNCS 9294, pages 142–154, 2015.

12

4. Djamal Belazzougui. Linear time construction of compressed text indices in compact space. In Proceedings of
the forty-sixth annual ACM symposium on Theory of computing, pages 148–193. ACM, 2014.
5. Djamal Belazzougui and Fabio Cunial. Representing the suffix tree with the cdawg. arXiv preprint
arXiv:1705.08640, 2017.
6. Djamal Belazzougui, Fabio Cunial, Travis Gagie, Nicola Prezza, and Mathieu Raffinot. Composite repetitionaware data structures. In Proc. CPM, pages 26–39, 2015.
7. P. Bille, M. B. Ettienne, I. L. Gørtz, and H. W. Vildhøj. Time-space trade-offs for Lempel-Ziv compressed
indexing. In Proc. 28th Annual Symposium on Combinatorial Pattern Matching (CPM), LIPIcs 78, pages 16:1–
16:17, 2017.
8. P. Bille, G. M. Landau, R. Raman, K. Sadakane, S. S. Rao, and O. Weimann. Random access to grammarcompressed strings and trees. SIAM Journal on Computing, 44(3):513–539, 2015.
9. Anselm Blumer, Janet Blumer, David Haussler, Ross McConnell, and Andrzej Ehrenfeucht. Complete inverted
files for efficient text retrieval and analysis. Journal of the ACM (JACM), 34(3):578–595, 1987.
10. Dany Breslauer. The suffix tree of a tree and minimizing sequential transducers. Theoretical Computer Science,
191(1-2):131–144, 1998.
11. Michael Burrows and David J Wheeler. A block-sorting lossless data compression algorithm, 1994.
12. S. Chen, E. Verbin, and W. Yu. Data structure lower bounds on random access to grammar-compressed strings.
CoRR, abs/1203.1080, 2012.
13. Vasek Chvatal. A greedy heuristic for the set-covering problem. Mathematics of operations research, 4(3):233–235,
1979.
14. Maxime Crochemore and Lucian Ilie. Computing longest previous factor in linear time and applications. Information Processing Letters, 106(2):75–80, 2008.
15. Maxime Crochemore and Renaud Vérin. Direct construction of compact directed acyclic word graphs. In
Combinatorial Pattern Matching, pages 116–129. Springer, 1997.
16. Maxime Crochemore and Renaud Vérin. On compact directed acyclic word graphs. In Structures in Logic and
Computer Science, pages 192–211. Springer, 1997.
17. Travis Gagie, Gonzalo Navarro, and Nicola Prezza. Optimal-time text indexing in bwt-runs bounded space. arXiv
preprint arXiv:1705.10382, 2017.
18. John Kenneth Gallant. String compression algorithms. 1982.
19. Danny Hucke, Markus Lohrey, and Carl Philipp Reh. The smallest grammar problem revisited. In International
Symposium on String Processing and Information Retrieval, pages 35–49. Springer, 2016.
20. John C Kieffer, En-Hui Yang, Gregory J Nelson, and Pamela Cosman. Universal lossless compression via multilevel pattern matching. IEEE Transactions on Information Theory, 46(4):1227–1245, 2000.
21. Sebastian Kreft and Gonzalo Navarro. On compressing and indexing repetitive sequences. Theoretical Computer
Science, 483:115–133, 2013.
22. N Jesper Larsson and Alistair Moffat. Off-line dictionary-based compression. Proceedings of the IEEE,
88(11):1722–1732, 2000.
23. Abraham Lempel and Jacob Ziv. On the complexity of finite sequences. IEEE Transactions on information
theory, 22(1):75–81, 1976.
24. V. Mäkinen, G. Navarro, J. Sirén, and N. Välimäki. Storage and retrieval of highly repetitive sequence collections.
Journal of Computational Biology, 17(3):281–308, 2010.
25. Veli Mäkinen, Gonzalo Navarro, Jouni Sirén, and Niko Välimäki. Storage and retrieval of highly repetitive
sequence collections. Journal of Computational Biology, 17(3):281–308, 2010.
26. J Ian Munro, Gonzalo Navarro, and Yakov Nekrich. Space-Efficient Construction of Compressed Indexes in
Deterministic Linear Time. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete
Algorithms, pages 408–424. SIAM, 2017.
27. Ge Nong, Sen Zhang, and Wai Hong Chan. Linear suffix array construction by almost pure induced-sorting. In
Data Compression Conference, 2009. DCC’09., pages 193–202. IEEE, 2009.
28. A. Policriti and N. Prezza. Computing LZ77 in run-compressed space. In Proc. 26th Data Compression Conference
(DCC), pages 23–32, 2016.
29. A. Policriti and N. Prezza. LZ77 Computation Based on the Run-Length Encoded BWT. Algorithmica, 2017.
30. N. Prezza. Compressed Computation for Text Indexing. PhD thesis, University of Udine, 2016.
31. Nicola Prezza.
Can Lempel-Ziv and Burrows-Wheeler compression be asymptotically compared?
In
www.iwoca.org, Problems Section, 2016.
32. Wojciech Rytter. Application of Lempel–Ziv factorization to the approximation of grammar-based compression.
Theoretical Computer Science, 302(1):211–222, 2003.

13

33. James A Storer and Thomas G Szymanski. Data compression via textual substitution. Journal of the ACM
(JACM), 29(4):928–951, 1982.
34. Edward N Trifonov. Making sense of the human genome. Structure and methods: proceedings of the Sixth
Conversation in the Discipline Biomolecular Stereodynamics held at the State University of New York at Albany,
June 6-10, 1989/edited by RH Sarma & MH Sarma, 1990.
35. Olga G Troyanskaya, Ora Arbell, Yair Koren, Gad M Landau, and Alexander Bolshoy. Sequence complexity
profiles of prokaryotic genomic sequences: A fast algorithm for calculating linguistic complexity. Bioinformatics,
18(5):679–688, 2002.
36. Terry A. Welch. A technique for high-performance data compression. Computer, 6(17):8–19, 1984.
37. Jacob Ziv and Abraham Lempel. Compression of individual sequences via variable-rate coding. Information
Theory, IEEE Transactions on, 24(5):530–536, 1978.

A

Appendix

A.1

Proof of Lemma 3

Consider any substring T [i..j]. Either the start rule of G is of the form S → A1 B1 , or S → Z1ℓ ,
for some ℓ > 2. Then, either (i) T [i..j] is fully contained in the strings generated by A1 , B1 , or Z1 ,
or (ii) it spans A1 |B1 (in the first case) or Z1ℓ1 |Z1ℓ2 , with ℓ1 + ℓ2 = ℓ (in the second case), where
we highlighted with a vertical bar the crossing point. In case (i), we apply the same reasoning
recursively until falling in case (ii). In case (ii), if T [i..j] spans Ai |Bi , for some 1 ≤ i ≤ g ′ , then we
have our thesis. The remaining case to consider is the one where T [i..j] spans Ziℓ1 |Ziℓ2 , for some
1 ≤ i ≤ g′′ and ℓ1 , ℓ2 > 1. This means that T [i..j] can be written as a suffix of Zi followed by a
concatenation of k ≥ 0 copies of Zi followed by a prefix of Zi , i.e. T [i..j] = Zi [l..|Zi |]Zik Zi [1..r] for
some 1 ≤ l ≤ |Zi |, k ≥ 0, and 0 ≤ r ≤ |Zi |. Then, T [i..j] has also an occurrence overlapping the
first occurrence of Zi in the term Ziℓ1 +ℓ2 , i.e. crossing the two factors Zi and Ziℓ1 +ℓ2 −1 of Ziℓ1 +ℓ2 :
T [i..j] = Zi [l..|Zi |]Ziℓ1 +ℓ2 −1 [1..(j − i) − (|Zi | − l)].
⊔
⊓
A.2

Proof of Theorem 6

We add γ equally-spaced attractor elements following Lemma 5. We define phrases of the parse
around attractor elements in a “concentric exponential fashion”, as follows. Characters on attractor
positions are explicitly stored. Let i1 < i2 be two consecutive attractor elements. Let m = ⌊(i1 +
i2 )/2⌋ be the middle position between them. We create a phrase of length 1 in position i1 + 1,
followed by a phrase of length 2, followed by a phrase of length 4, ... until the new phrase does not
include position m. We do the same (but right-to-left) for position i2 . We finally add a phrase in
the middle, i.e. in the remaining “hole” covering position m. For the phrases’ sources, we use any
of their occurrences crossing an attractor element (possible by definition of Γ ).
Suppose we are to extract T [i], and i is inside a phrase of length ≤ 2e , for some e. Let i′ be the
position from where T [i] is copied according to our bidirectional parse. By the way we defined the
scheme, it is not hard to see that i′ is either an explicitly stored character or lies inside a phrase
of length2 ≤ 2e−1 . Since attractor elements are at distance at most n/γ from each other, both the
parse height and the number of phrases we introduce per attractor element are O(log(n/γ)).
⊔
⊓
2

To see this, note that 2e = 1 + 20 + 21 + 22 + · · · , +2e−1 : these are the lengths of phrases following (and preceding)
attractor elements (included). In the worst case, position i′ falls inside the longest such phrase, of length 2e−1

14

A.3

Proof of Theorem 7

We first build the bidirectional parse of Theorem 6, with O(γ log(n/γ)) phrases of length at most
n/γ each. We will process phrases in order of increasing length. We maintain the following invariant.
Every maximal substrings T [i..j] covered by processed phrases is collapsed into a single nonterminal
Y . Moreover, once we finish processing a phrase T [i′ ..j ′ ], the phrase will be represented by a single
nonterminal X (expanding to T [i′ ..j ′ ]). We will create O(1) new nonterminals to merge X with
the (at most) two adjacent nonterminals representing all contiguous processed phrases to keep our
invariant true. It is clear that, once all phrases have been processed, our invariant implies that the
entire string is collapsed into a single nonterminal S. We now show how to process a phrase and
analyze the number of nonterminal introduced by the process.
The overall idea is to map a phrase on its source and copy the source’s parse into nonterminals,
introducing new nonterminals at the borders if needed. By the bidirectional parse’s definition, the
source of any phrase T [i..j] overlaps only phrases shorter than j − i + 1 characters. Since we process
phrases in order of increasing length, phrases overlapping the source have already been processed
and therefore their parse into nonterminals is well-defined.
We make sure that our string is parsed in levels. At level i > 0, we parse the nonterminals (or
terminals if i = 1) of level i − 1 in groups of length 2 or 3, and replace each group with a new
nonterminal.
We start by parsing each maximal substring T [i..j] containing only phrases of length 1 into
arbitrary blocks of length 2 or 3. We create a new nonterminal per block. Note that, by the way the
parse is defined, this is always possible (since j − i + 1 ≥ 2 always holds). We repeat this process
recursively—grouping nonterminals at level k ≥ 0 to form new nonterminals at level k + 1—until
T [i..j] is collapsed into a single nonterminal. Our invariant now holds for the base case, i.e. for
phrases of length t = 1: each maximal substring containing only phrases of length ≤ t is collapsed
into a single nonterminal. We now proceed with phrases of length ≥ 2, in order of increasing
length. Let T [i..j] be a phrase to be processed, with source T [i′ ..j ′ ]. By definition of the parse,
T [i′ ..j ′ ] overlaps only phrases of length at most j − i and, by inductive hypothesis, these phrases
have already been processed. We group characters of T [i..j] in blocks of length 2 or 3 copying the
parse of T [i′ ..j ′ ] at level 0. Note that this might not be possible for the borders of length 1 or 2 of
T [i..j]: this is the case if the block containing T [i′ ] starts before position i′ (symmetric for T [j ′ ]).
In this case, we create O(1) new nonterminals as follows. If T [i′ − 1, i′ , i′ + 1] form a block, then
we group T [i, i + 1] in a block of length 2 and collapse it into a new nonterminal at level 1. If, on
the other hand, T [i′ − 1, i′ ] form a block, we consider two sub-cases. If T [i′ + 1, i′ + 2] form a block,
then we create the block to T [i, i + 1, i + 2] and collapse it into a new nonterminal at level 1. If
T [i′ + 1, i′ + 2, i′ + 3] form a block, then we create the two blocks T [i, i + 1] and T [i + 2, i + 3] and
collapse them into 2 new nonterminals at level 1. We repeat this process for the nonterminals at
level k ≥ 1 that were copied from T [i′ ..j ′ ], grouping them in blocks of length 2 or 3 according to the
source and creating O(1) new nonterminals at level k + 1 to cover the borders. After O(log(n/γ))
levels, T [i..j] is collapsed into a single nonterminal. Since we create O(1) new nonterminals per
level, we introduce overall O(log(n/γ)) new nonterminals.
At this point, let Y be the nonterminal just created that expands to T [i..j]. Since we process
phrases by increasing length, Y is either followed (Y X), preceded (XY ), or in the middle (X1 Y X2 )
of one or two nonterminals expanding to a maximal substring containing contiguous processed
phrases. We now show how to collapse these two or three nonterminals in order to maintain our
invariant true, while at the same time satisfying the property that nonterminals at level i expand
15

to two or three nonterminals at level i − 1. We show the procedure in the case Y is preceded by a
nonterminal X, i.e. we want to collapse XY into a single nonterminal. The other two cases can then
easily be derived using the same technique. Let iX and iY be the levels of X and Y , and let us assume
that iX ≤ iY (the case iX > iY is symmetric). If iX = iY , then we just create a new nonterminal
W → XY and we are done. Otherwise, let Y1 . . . Yt , with t ≥ 2, be the sequence of nonterminals
that are the expansion of Y at level iX . Our goal is to collapse the sequence XY1 . . . Yt into a single
nonterminal, while introducing at most O(log(n/γ)) new nonterminals (that are charged to the
phrase T [i..j]: overall, we will therefore introduce O(log(n/γ)) new nonterminals per phrase). The
parsing of Y1 . . . Yt into blocks is already defined (by the expansion of Y ), so we only need to copy
it while adjusting the left border in order to include X. We distinguish two cases. If Y1 and Y2 are
grouped into a single block, then we replace this block with the new block XY1 Y2 and collapse it in a
new nonterminal at level iX + 1. If, on the other hand, Y1 , Y2 , and Y3 are grouped into a single block
then we replace it with the two blocks XY1 and Y2 Y3 and collapse them in two new nonterminals
at level iX + 1. We repeat the same procedure at levels iX + 1, iX + 2, . . . , iY , until everything is
collapsed in a single nonterminal. At each level we introduce one or two new nonterminals, therefore
overall we introduce at most 2(iY − iX ) + 1 ∈ O(log(n/γ)) new nonterminals.
⊔
⊓
A.4

Proof of Theorem 8
w log (n/γ)

τ
packed characters in
We describe a data structure supporting the extraction of α =
log σ
O(logτ (n/γ)) time. To extract a substring of length ℓ we divide it into ⌈ℓ/α⌉ blocks and extract
each block with the proposed data structure. Overall, this will take O((ℓ/α + 1) logτ (n/γ)) =
O(logτ (n/γ) + ℓ log(σ)/w) time.
Our data structure is stored in O(logτ (n/γ)) levels. For simplicity, we assume that γ divides
n and that n/γ is a power of 2τ . Intuitively, we will build a DAG with nodes of out-degree 2τ ;
each node will be associated with a substring whose length is exponentially decreasing in the levels
(with base 2τ ).
The top level (level 0) is special: we divide the string into γ blocks T [1..n/γ] T [n/γ+1..2n/γ] . . . T [n−
n/γ+1..n] of size n/γ. For levels i > 0, we let si = n/(γ·τ i ) and, for every element j ∈ Γ , we consider
the 2τ non-overlapping blocks of length si : T [j−si ·k+1...j−si ·(k−1)] and T [j+si ·(k−1)+1...j+si ·k],
for k = 1, . . . , τ . Each such block is composed of two half-blocks of length si /2. In total, there are 4τ
half blocks. We moreover consider a sequence of 4τ − 1 additional consecutive and non-overlapping
half-blocks of length si /2, starting in the middle of the first half-block above defined and ending
in the middle of the last. Note that, with this choice of blocks, at level i for any substring S of
length at most si /4 (inside the considered regions of length 2τ · si around elements of Γ ) we can
always find a half-block fully containing S. This property will now be used to map “short” strings
from the first to last level of our structure without splitting them, until reaching explicitly stored
characters at some level that we define below.
From the definition of string attractor, blocks at level 0 and each half-block at level i > 0 have
an occurrence at level i + 1 crossing some position in Γ . Such an occurrence can be fully identified
by the coordinate hoff , ji, for 0 ≤ off < 2si and j ∈ Γ , indicating that the occurrence starts at
τ (n/γ)
. Then i∗ is
position j − si + off + 1. Let i∗ be the smallest number such that si∗ < 4α = 4w log
log σ
the last level of our structure. At this level, we explicitly store a packed string with the characters
of the blocks. This uses in total O(γ · τ · si∗ log(σ)/w) = O(γτ logτ (n/γ)) words of space. All the
blocks at level 0 and half-block at levels 0 < i < i∗ store instead the coordinates hoff , ji of their

16

primary occurrence in the next level. At level i∗ − 1, these coordinates point inside the strings of
explicitly stored characters.
Let S = T [i..i + α − 1] be the substring to be extracted. Note that we can assume n/γ ≥ α;
otherwise all the string can be stored in plain packed form using n log(σ)/w < αγ log(σ)/w ∈
O(γ logτ (n/γ)) words and we do not need any data structure. It follows that S either spans two
blocks at level 0, or it is contained in a single block. The former case can be solved with two queries
of the latter, so we assume, without losing generality, that S is fully contained inside a block at
level 0. To retrieve S, we map it down to the next levels (using the stored coordinates of primary
occurrences of half-blocks) as a contiguous substring as long as this is possible, that is, as long as
it fits inside a single half-block. Note that, thanks to the way half-blocks overlap, this is always
possible as long as α ≤ si /4. By definition, then, we arrive in this way precisely to level i∗ , where
characters are stored explicitly and we can return the packed substring. Note also that, since blocks
in the same level have the same length, at each level we spend only constant time to find the pointer
to the next level.
⊔
⊓
A.5

Proof of Lemma 6

We show a reduction from set-cover.SLet hU, S1 , . . . , St i be an instance of set-cover, where
U = {u1 , . . . , un } is the universe and ti=1 Si = U . Without loss of generality, we can assume
ui = i − 1, for i = 1, . . . , n, and n = 2m for some m ≥ 0: if n is not a power of two, then we add
a new set St+1 = [|U |, 2⌈log 2 |U |⌉ − 1] and replace the universe by U ′ = U ∪ St+1 (i.e. we add new
elements until reaching the next power of two). It is clear that Si1 , . . . , Siq cover U if and only if
Si1 , . . . , Siq , St+1 cover U ′ , so the problem with n being a power of two is still NP-complete.
We build a labeled tree T as follows. The alphabet is h0, 1, s1 , . . . , st i. The root r(T ) has t children c1 , . . . , ct with incoming edges labeled, respectively, s1 , . . . , st . Each ci has two children nodes,
c0i and c1i . Edges hci , c0i i and hci , c1i i are labeled 0 and 1, respectively. Let Si = {uji,1 , . . . , uji,bi }. The
subtrees rooted in c0i and c1i are identical: each is a binary trie containing the m-digits binary representations of uji,1 , . . . , uji,bi . We claim that our set-cover instance hU, S1 , . . . , St i has a solution
of size at most γ if and only if T has a path attractor of size at most t + 2γ.
(⇒) Let Si1 , . . . , Siq be a cover of U . We want to prove that T has an attractor of size at most
t + 2q. We claim that Γ = {hr(T ), ci i : i = 1, . . . , t} ∪ {hci , c0i i : i = i1 , . . . , iq } ∪ {hci , c1i i : i =
i1 , . . . , iq } is such a path attractor for T . By the way T is defined, the strings labeling paths in
this tree either start with a si , for 1 ≤ i ≤ t, or are any combination of at most m + 1 bits (i.e.
characters in {0, 1}). InS
particular, note that all combinations of at most m + 1 bits occur as paths,
m
since (i) |U | = 2 , (ii) ti=1 Si = U , and (iii) the binary representations of Si -elements are always
preceded by the labels 0 and 1 in the tree’s paths. All paths whose labels start with a si are clearly
captured by the edges {hr(T ), ci i : i = 1, . . . , t} ∈ Γ . We now focus on the binary strings labeling
the remaining paths. Since Si1 , . . . , Siq is a cover of U , the binary representations of elements in
Si1 , . . . , Siq are all possible combinations of m bits. This implies that the set of labels of paths
starting from edges in {hci , cxi i : i = i1 , . . . , iq }, with x ∈ {0, 1}, are all possible combinations of x
followed by any sequence of m bits. Since in Γ we include both hci , c0i i and hci , c1i i for i = i1 , . . . , iq ,
these edges capture all prefixes of paths labeled with any combination of m + 1 bits. Since the
closure under prefix of the set {0, 1}m+1 is exactly {0, 1}≤m+1 , we finally obtain that edges in Γ
capture all paths in T .
(⇐) Let Γ be a path attractor for T , of size q. We want to prove that our set-cover instance
has a solution of size at most (q − t)/2. First, note that {hr(T ), ci i : i = 1, . . . , t} ⊆ Γ , as otherwise
17

the t unary paths labeled s1 , . . . , st would not be represented by the attractor. Let α = q − t. The α
edges in Γ − {hr(T ), ci i : i = 1, . . . , t} intersect all possible sequences of at most m + 1 bits (by the
attractor’s definition). We create a cover of U of the desired size as follows. We first initialize two
empty sets R0 and R1 . Then, for every edge hu, vi in Γ −{hr(T ), ci i : i = 1, . . . , t}, if hu, vi = hci , cxi i
or hu, vi belongs to the subtree rooted in cxi , for some 1 ≤ i ≤ t and x ∈ {0, 1}, then we insert Si
in Rx . We claim that both R0 and R1 are a cover of U . In particular, note that |R0 | + |R1 | ≤ α:
we pick as solution of our set-cover instance the Rx of minimum size |Rx | ≤ α/2 = (q − t)/2,
that is, our claim. We now prove that R1 is a cover of U (the proof is analogous for R0 ). Note
that the following two facts hold. (i) By definition, the tree rooted in c1i is a trie containing the
binary representations of elements from Si . (ii) Edges hu, vi in Γ − {hr(T ), ci i : i = 1, . . . , t} such
that hu, vi = hci , c1i i or hu, vi belongs to the subtree rooted in some c1i capture all paths labeled
with 1{0, 1}m (from the attractor’s definition). From (i) and (ii) it is easy to derive that sets in
R1 must cover the whole U . Suppose, by contradiction, that some u ∈ U is not covered by R1 ,
and let Bu be the binary representation of u. Let moreover Si1 , . . . , Sik be all the sets containing
u. Since u ∈ U is not covered by R1 , none of the Si1 , . . . , Sik belongs to R1 . Then, by definition of
R1 , this implies that no edge of Γ is equal to hci , cxi i or belongs to the subtree rooted in cxi , for any
i ∈ {i1 , . . . , ik }. Since these are the only edges potentially intersecting path 1Bu , this means that
1Bu is not captured by Γ , which is a contradiction.
⊔
⊓
A.6

Proof of Theorem 10

We show a reduction to set-cover, and then solve the instance with the greedy algorithm [13] that at
each round picks the set covering the largest number of non-covered elements in the universe. It is
known [13] that the greedy algorithm computes a (ln n)-approximation of the optimal solution. We
make use of the suffix tree T (G) of the tree G [10]. T (G) is obtained by conceptually building the
trie containing all reversed prefixes of root-to-leaves paths in G, and then applying path compression
(as in the standard suffix tree of a string). T (G) takes O(n) space, can be built in O(n) time, and
contains a node (implicit or explicit) for each reversed path in G [10] (i.e. all G’s reversed paths
are represented from the root to some node of T (G)).
The universe of our set-cover instance is composed of all N ∈ O(n) edges of T (G): U = E ′ =
′
{e1 , e′2 , . . . , e′N }. The collection of sets is S = {s1 , . . . , sn }: one set per G’s edge. Let st(e′ ), where
e′ is a T (G)’s edge, denote the string read from the root of T (G) to the first character (included)
←−−−
in the label of e′ . Set si contains all T (G)’s edges e′j such that there is an occurrence of st(e′j ) in
←−−−
G (i.e. a path labeled st(e′j )) crossing edge ei . We claim that S = {si1 , . . . , sit } is a solution to this
instance of set-cover if and only if Γ = {ei1 , . . . , eit } is a path attractor for G. In particular, note
that the one-to-one correspondence implies that a c-approximation to the set-cover instance yields
a c-approximation of the smallest path attractor.
(⇒) Let S = {si1 , . . . , sit } be a solution to the set-cover instance. We want to show that
Γ = {ei1 , . . . , eit } ⊆ E is a path attractor for G. Now, consider the label s of any path in G. By
−
definition of T (G), ←
s is a path starting from the root and ending inside the label of some edge e′
←−−−−
− of s. Since S is a solution to
of T (G). In particular, we can write s = st(e′ )x, for some prefix ←
x
′
the set-cover instance, there exists a si ∈ S such that e ∈ si . By the way the set-cover instance is
←−−−
defined, this implies that ei ∈ Γ crosses an occurrence of st(e′ ) in G. But then, the fact that x is
←−−−
the continuation of st(e′ ) inside the label of e′ means that all paths labeled st(e′ ) in G are always
18

−−−−
−, i.e. e ∈ Γ crosses an occurrence of ←
preceded by ←
x
st(e′ )x = s in G. Since s is a generic label of a
i
path in G, we obtain that Γ is a valid path attractor.
(⇐) Let Γ = {ei1 , . . . , eit } ⊆ E be a path attractor for G. We want to show that S =
{si1 , . . . , sit } is a solution to the set-cover instance. Pick any suffix tree edge e′ ∈ U . Now, consider
←−−−
the string st(e′ ). By the definition of T (G), st(e′ ) is a path in G. Since Γ is an attractor for G, there
←−−−
exist a ei ∈ Γ intersecting an occurrence of st(e′ ). Then, by definition of the set-cover instance,
e′ ∈ si ∈ S. Since e′ is a generic element of U , we obtain that S is a cover of U .
We implement the logarithmic approximation algorithm as follows. We maintain an undirected
bipartite graph H = hE, E ′ , F ⊆ E × E ′ i, having as vertexes all elements in E (i.e. G’s edges) and
E ′ (i.e. T (G)’s edges). We add an edge he, e′ i in F whenever G’s edge e crosses an occurrence of
st(e′ ). We keep G’s edges in an array P , and associate to each of them an integer storing their
degree in H: deg(e) = |{he, e′ i ∈ F }|. The degrees can be computed in |F | ∈ O(n2 ) time at the
beginning. Our algorithm runs in O(n) steps: at each step, we pick the e ∈ P with largest deg(e).
After that, for each e′ such that he, e′ i ∈ F , we decrease by one the degree of neighbors of e′ in H,
i.e. of all ei ∈ E such that hei , e′ i ∈ F , and we remove e, all its adjacent edges, and all its neighbors
from H. We stop the procedure when H does not have anymore vertexes from E ′ .
Since each edge of H can be removed only once, re-computing the degrees takes overall O(n2 )
time. Picking the minimum from P takes O(n) time at each step. Overall, the procedure runs in
O(n2 ) time.
⊔
⊓

19

