arXiv:1707.08197v2 [] 26 Sep 2017

Fast Label Extraction in the CDAWG
Djamal Belazzougui1 and Fabio Cunial2
1

2

DTISI, CERIST Research Center, Algiers, Algeria.
Max Planck Institute of Molecular Cell Biology and Genetics,
Dresden, Germany.
September 27, 2017
Abstract
The compact directed acyclic word graph (CDAWG) of a string T of
length n takes space proportional just to the number e of right extensions of the maximal repeats of T , and it is thus an appealing index
for highly repetitive datasets, like collections of genomes from similar
species, in which e grows significantly more slowly than n. We reduce
from O(m log log n) to O(m) the time needed to count the number of occurrences of a pattern of length m, using an existing data structure that
takes an amount of space proportional to the size of the CDAWG. This
implies a reduction from O(m log log n + occ) to O(m + occ) in the time
needed to locate all the occ occurrences of the pattern. We also reduce
from O(k log log n) to O(k) the time needed to read the k characters of the
label of an edge of the suffix tree of T , and we reduce from O(m log log n)
to O(m) the time needed to compute the matching statistics between a
query of length m and T , using an existing representation of the suffix
tree based on the CDAWG. All such improvements derive from extracting
the label of a vertex or of an arc of the CDAWG using a straight-line
program induced by the reversed CDAWG.

1

Introduction

Large, highly repetitive datasets of strings are the hallmark of the post-genomic
era, and locating and counting all the exact occurrences of a pattern in such
collections has become a fundamental primitive. Given a string T of length
n, the compressed suffix tree [15, 18] and the compressed suffix array can be
used for such purpose, and they achieve an amount of space bounded by the
k-th order empirical entropy of T . However, such measure of redundancy is
known not to be meaningful when T is very repetitive [10]. The space taken
by such compressed data structures also includes an o(n) term which can be
a practical bottleneck when T is very repetitive. Conversely, the size of the

1

compact directed acyclic word graph (CDAWG) of T is proportional just to the
number of maximal repeats of T and of their right extensions (defined in Section
2.2): this is a natural measure of redundancy for very repetitive strings, which
grows sublinearly with n in practice [2].
In previous work we described a data structure that takes an amount of space
proportional to the size eT of the CDAWG of T , and that counts all the occ
occurrences in T of a pattern of length m in O(m log log n) time, and reports
all such occurrences in O(m log log n + occ) time [2]. We also described a representation of the suffix tree of T that takes space proportional to the CDAWG
of T , and that supports, among other operations, reading the k characters of
the label of an edge of the suffix tree in O(k log log n) time, and computing the
matching statistics between a pattern of length m and T in O(m log log n) time.
In this paper we remove the dependency of such key operations on the length
n of the uncompressed, highly repetitive string, without increasing the space
taken by the corresponding data structures asymptotically. We achieve this by
dropping the run-length-encoded representation of the Burrows-Wheeler transform of T , used in [2], and by exploiting the fact that the reversed CDAWG
induces a context-free grammar that produces T and only T , as described in
[1]. A related grammar, already implicit in [6], has been concurrently exploited
in [21] to achieve similar bounds to ours. Note that in some strings, for example in the family Ti for i ≥ 0, where T0 = 0 and Ti = Ti−1 iTi−1 , the length
of the string grows exponentially in the size of the CDAWG, thus shaving an
O(log log n) term is identical to shaving an O(log eT ) term.
This work can be seen as a continuation of the research program, started in
[1, 2], of building a fully functional, repetition-aware representation of the suffix
tree based on the CDAWG.

2

Preliminaries

We work in the RAM model with word length at least log n bits, where n is the
length of a string that is implicit from the context. We index strings and arrays
starting from one. We call working space the maximum amount of memory that
an algorithm uses in addition to its input and its output.

2.1

Graphs

We assume the reader to be familiar with the notions of tree and of directed
acyclic graph (DAG). In this paper we only deal with ordered trees and DAGs,
in which there is a total order among the out-neighbors of every node. The
i-th leaf of a tree is its i-th leaf in depth-first order, and to every node v of a
tree we assign the compact integer interval [sp(v)..ep(v)], in depth-first order,
of all leaves that belong to the subtree rooted at v. In this paper we use the
expression DAG also for directed acyclic multigraphs, allowing distinct arcs to
have the same source and destination nodes. In what follows we consider just
DAGs with exactly one source and one sink. We denote by T (G) the tree

2

generated by DAG G with the following recursive procedure: the tree generated
by the sink of G consists of a single node; the tree generated by a node v of
G that is not the sink, consists of a node whose children are the roots of the
subtrees generated by the out-neighbors of v in G, taken in order. Note that:
(1) every node of T (G) is generated by exactly one node of G; (2) a node of G
different from the sink generates one or more internal nodes of T (G), and the
subtrees of T (G) rooted at all such nodes are isomorphic; (3) the sink of G can
generate one or more leaves of T (G); (4) there is a bijection, between the set of
root-to-leaf paths in T (G) and the set of source-to-sink paths in G, such that
every path v1 , . . . , vk in T (G) is mapped to a path v1′ , . . . , vk′ in G.

2.2

Strings

Let Σ = [1..σ] be an integer alphabet, let # = 0 ∈
/ Σ be a separator, and let
T = [1..σ]n−1 # be a string. Given a string W ∈ [1..σ]k , we call the reverse
of W the string W obtained by reading W from right to left. For a string
W ∈ [1..σ]k # we abuse notation, denoting by W the string W [1..k]#. Given
a substring W of T , let PT (W ) be the set of all starting positions of W in T .
A repeat W is a string that satisfies |PT (W )| > 1. We conventionally assume
that the empty string occurs n + 1 times in T , before the first character of T
and after every character of T , thus it is a repeat. We denote by ΣℓT (W ) the set
of left extensions of W , i.e. the set of characters {a ∈ [0..σ] : |PT (aW )| > 0}.
Symmetrically, we denote by ΣrT (W ) the set of right extensions of W , i.e. the
set of characters {b ∈ [0..σ] : |PT (W b)| > 0}. A repeat W is right-maximal
(respectively, left-maximal ) iff |ΣrT (W )| > 1 (respectively, iff |ΣℓT (W )| > 1). It
is well known that T can have at most n − 1 right-maximal repeats and at most
n − 1 left-maximal repeats. A maximal repeat of T is a repeat that is both
left- and right-maximal. Note that the empty string is a maximal repeat. A
near-supermaximal repeat is a maximal repeat with at least one occurrence that
is not contained in an occurrence of another maximal repeat (see e.g. [13]). A
minimal absent word of T is a string W that does not occur in T , but such that
any substring of W occurs in T . It is well known that a minimal absent word
W can be written as aV b, where a and b are characters and V is a maximal
repeat of T [8]. It is also well known that a maximal repeat W = [1..σ]m of T
is the equivalence class of all the right-maximal strings {W [1..m], . . . , W [k..m]}
such that W [k + 1..m] is left-maximal, and W [i..m] is not left-maximal for all
i ∈ [2..k] (see e.g. [2]). By matching statistics of a string S with respect to T ,
we denote the array MSS,T [1..|S|] such that MSS,T [i] is the length of the longest
prefix of S[i..|S|] that occurs in T .
For reasons of space we assume the reader to be familiar with the notion of
suffix trie of T , as well as with the related notion of suffix tree STT = (V, E) of
T , which we do not define here. We denote by ℓ(γ), or equivalently by ℓ(u, v),
the label of edge γ = (u, v) ∈ E, and we denote by ℓ(v) the string label of node
v ∈ V . It is well known that a substring W of T is right-maximal iff W = ℓ(v)
for some internal node v of the suffix tree. Note that the label of an edge of STT
is itself a right-maximal substring of T , thus it is also the label of a node of STT .
3

We assume the reader to be familiar with the notion of suffix link connecting a
node v with ℓ(v) = aW for some a ∈ [0..σ] to a node w with ℓ(w) = W . Here
we just recall that inverting the direction of all suffix links yields the so-called
explicit Weiner links. Given an internal node v and a symbol a ∈ [0..σ], it might
happen that string aℓ(v) does occur in T , but that it is not right-maximal, i.e.
it is not the label of any internal node: all such left extensions of internal nodes
that end in the middle of an edge or at a leaf are called implicit Weiner links.
The suffix-link tree is the graph whose edges are the union of all explicit and
implicit Weiner links, and whose nodes are all the internal nodes of STT , as well
as additional nodes corresponding to the destinations of implicit Weiner links.
We call compact suffix-link tree the subgraph of the suffix-link tree induced by
maximal repeats.
We assume the reader to be familiar with the notion and uses of the BurrowsWheeler transform of T . In this paper we use BWTT to denote the BWT
of T , and we use range(W ) = [sp(W )..ep(W )] to denote the lexicographic
interval of a string W in a BWT that is implicit from the context. For a
node v (respectively, for an edge e) of STT , we use the shortcut range(v) =
[sp(v)..ep(v)] (respectively, range(e) = [sp(e)..ep(e)]) to denote range(ℓ(v))
(respectively, range(ℓ(e))). We denote by rT the number of runs in BWTT , and
we call run-length encoded BWT (denoted by RLBWTT ) any representation of
BWTT that takes O(rT ) words of space, and that supports rank and select
operations (see e.g. [16, 17, 20]).
Finally, in this paper we consider only context-free grammars in which the
right-hand side of every production rule consists either of a single terminal, or
of at least two nonterminals. We denote by π(F ) the sequence of characters
produced by a nonterminal F of a context-free grammar. Every node in the
parse tree of F corresponds to an interval in π(F ). Given a nonterminal F and
an integer interval [i..j] ⊆ [1..|π(F )|], let a node of the parse tree from F be
marked iff its interval is contained in [i..j]. By blanket of [i..j] in F we denote
the set of all marked nodes in the parse tree of F . Clearly the blanket of [i..j]
in F contains O(j − i) nodes and edges.

2.3

CDAWG

The compact directed acyclic word graph of a string T (denoted by CDAWGT in
what follows) is the minimal compact automaton that recognizes all suffixes of
T [5, 9]. We denote by eT the number of arcs in CDAWGT , and by hT the length
of a longest path in CDAWGT . We remove subscripts when string T is implicit
from the context. The CDAWG of T can be seen as the minimization of STT ,
in which all leaves are merged to the same node (the sink) that represents T
itself, and in which all nodes except the sink are in one-to-one correspondence
with the maximal repeats of T [19]. Every arc of CDAWGT is labeled by a
substring of T , and the out-neighbors w1 , . . . , wk of every node v of CDAWGT
are sorted according to the lexicographic order of the distinct labels of arcs
(v, w1 ), . . . , (v, wk ). We denote again with ℓ(v) (respectively, with ℓ(γ)) the
label of a node v (respectively, of an arc γ) of CDAWGT .
4

Since there is a bijection between the nodes of CDAWGT and the maximal
repeats of T , and since every maximal repeat of T is the equivalence class of a
set of roots of isomorphic subtrees of STT , it follows that the node v of CDAWGT
with ℓ(v) = W is the equivalence class of the nodes {v1 , . . . , vk } of STT such
that ℓ(vi ) = W [i..m] for all i ∈ [1..k], and such that vk , vk−1 , . . . , v1 is a maximal
unary path in the suffix-link tree. The subtrees of STT rooted at all such nodes
are isomorphic, and T (CDAWGT ) = STT . It follows that a right-maximal string
can be identified by the maximal repeat W it belongs to, and by the length of
the corresponding suffix of W . Similarly, a suffix of T can be identified by a
length relative to the sink of CDAWGT .
The equivalence class of a maximal repeat is related to the equivalence classes
of its in-neighbors in the CDAWG in a specific way:
Property 1 ([2]). Let w be a node in the CDAWG with ℓ(w) = W ∈ [1..σ]m ,
and let Sw = {W [1..m], . . . , W [k..m]} be the right-maximal strings that belong
to the equivalence class of node w. Let {v 1 , . . . , v t } be the in-neighbors of w in
CDAWGT , and let {V 1 , . . . , V t } be their labels. Then, Sw is partitioned into t
1
t
i
disjoint sets Sw
, . . . , Sw
such that Sw
= {W [xi + 1..m], W [xi + 2..m], . . . , W [xi +
|Svi |..m]}, and the right-maximal string V i [p..|V i |] labels the parent of the locus
of the right-maximal string W [xi + p..m] in the suffix tree, for all p ∈ [1..|Svi |].
Property 1 partitions every maximal repeat of T into left-maximal factors,
and applied to the sink w of CDAWGT , it partitions T into t left-maximal factors,
where t is the number of in-neighbors of w, or equivalently the number of nearsupermaximal repeats of T . Moreover, by Property 1, it is natural to say that
in-neighbor v i of node w is smaller than in-neighbor v j of node w iff xi < xj ,
j
i
. We call
are longer than the strings in Sw
or equivalently if the strings in Sw
CDAWGT the ordered DAG obtained by applying this order to the reversed
CDAWGT , i.e. to the DAG obtained by inverting the direction of all arcs of
CDAWGT , and by labeling every arc (v, w), where w is the source of CDAWGT ,
with the first character of the string label of arc (w, v) in CDAWGT . Note
that some nodes of CDAWGT can have just one out-neighbor: for brevity we
denote by CDAWGT the graph obtained by collapsing every such node v, i.e. by
redirecting to the out-neighbor of v all the arcs directed to v, propagating to
such arcs the label of the out-neighbor of v, if any.
The source of CDAWGT is the sink of CDAWGT , which is the equivalence
class of all suffixes of T in string order. There is a bijection between the distinct
paths of CDAWGT and the suffixes of T ; thus, the i-th leaf of T (CDAWGT ) in
depth-first order corresponds to the i-th suffix of T in string order. Moreover,
the last arc in the source-to-sink path of CDAWGT that corresponds to suffix
T [i..|T |] is labeled by character T [i]. It follows that:
Property 2 ([1]). CDAWGT is a context-free grammar that generates T and
only T , and T (CDAWGT ) is its parse tree. Let v be a node of CDAWGT with t
in-neighbors, and let ℓ(v) = V W , where W is the longest proper suffix of ℓ(v)
that is a maximal repeat (if any). Then, v corresponds to a nonterminal F of the
grammar such that π(F ) = V = π(F1 ) · · · π(Ft ), and Fi are the nonterminals
that correspond to the in-neighbors of v, for all i ∈ [1..t].
5

Note that the nonterminals of this grammar correspond to unary paths in
the suffix-link tree of T , i.e. to edges in the suffix tree of T . This parallels the
grammar implicit in [6] and explicit in [21], whose nonterminals correspond to
unary paths in the suffix trie of T , i.e. to edges in the suffix tree of T .

2.4

Counting and Locating with the CDAWG

CDAWGT can be combined with RLBWTT to build a data structure that takes
O(eT ) words of space, and that counts all the occ occurrences of a pattern
P of length m in O(m log log n) time, and reports all such occurrences in
O(m log log n + occ) time [2].
Specifically, for every node v of the CDAWG, we store |ℓ(v)| in a variable
v.length. Recall that an arc (v, w) in the CDAWG means that maximal repeat
ℓ(w) can be obtained by extending maximal repeat ℓ(v) to the right and to the
left. Thus, for every arc γ = (v, w) of the CDAWG, we store the first character of
ℓ(γ) in a variable γ.char, and we store the length of the right extension implied
by γ in a variable γ.right. The length γ.left of the left extension implied by
γ can be computed by w.length − v.length − γ.right. For every arc of the
CDAWG that connects a maximal repeat W to the sink, we store just γ.char
and the starting position γ.pos of string W · γ.char in T . The total space used
by the CDAWG is O(eT ) words, and the number of runs in BWTT can be shown
to be O(eT ) as well [2].
We use the RLBWT to count the number of occurrences of P in T , in
O(m log log n) time: if this number is not zero, we use the CDAWG to report
all the occ occurrences of P in O(occ) time, using a technique already sketched
in [7]. Specifically, since we know that P occurs in T , we perform a blind search
for P in the CDAWG, as follows. We keep a variable i, initialized to zero, that
stores the length of the prefix of P that we have matched so far, and we keep
a variable j, initialized to one, that stores the starting position of P inside the
last maximal repeat encountered during the search. For every node v in the
CDAWG, we choose the arc γ such that γ.char = P [i + 1] in constant time
using hashing, we increment i by γ.right, and we increment j by γ.left. If
the search leads to the sink by an arc γ, we report γ.pos + j − 1 and we stop.
If the search ends at a node v that is associated with a maximal repeat W , we
determine all the occurrences of W in T by performing a depth-first traversal
of all nodes reachable from v in the CDAWG, updating variables i and j as
described above, and reporting γ.pos + j − 1 for every arc γ that leads to the
sink. Clearly the total number of nodes and arcs reachable from v is O(occ).
Note that performing the blind search for a pattern in the CDAWG is analogous to a descending walk on the suffix tree, thus we can compute the BWT
interval of every node of STT that we meet during the search, by storing in
every arc of the CDAWG a suitable offset between BWT intervals, as described
in the following property:
Property 3 ([2]). Let {W [1..m], . . . , W [k..m]} be the right-maximal strings that
belong to the equivalence class of maximal repeat W ∈ [1..σ]m of string T , and

6

Algorithm 1: Reading the first k characters of the string produced by
a nonterminal F of a straight-line program represented as a DAG G. F
corresponds to node u′ of G. Notation follows Lemma 1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

22
23
24

S ← empty stack;
S.push((u′ , 0, 0));
extracted ← 0;
repeat
t ← S.top;
if t.lastChild < |t.node.outNeighbors| then
t.lastChild ← t.lastChild + 1 ;
v ′ ← t.node.outNeighbors[t.lastChild];
if v ′ = G.sink then
print(label(t.node, v ′ ));
extracted ← extracted + 1;
else if t.lastChild = 1 then
t.depth ← 1;
S.push((levelAncestor(t.node, t.depth), 0, t.depth));
else S.push((v ′ , 0, 0)) ;
else
S.pop;
if S = ∅ then return extracted ;
t ← S.top;
if t.depth < t.node.depth then t.depth ← t.depth + 1 ;
if t.depth < t.node.depth then
S.push((levelAncestor(t.node, t.depth), 1, t.depth)) ;
end
until extracted = k;
return k;

let range(W [i..m]) = [pi ..qi ] for i ∈ [1..k]. Then |qi − pi + 1| = |qj − pj + 1|
for all i and j in [1..k]. Let c ∈ [0..σ], and let range(W [i..m]c) = [xi ..yi ] for
i ∈ [1..k]. Then, xi = pi + x1 − p1 and yi = pi + y1 − p1 .
Properties 1 and 3, among others, can be used to implement a number of
suffix tree operations in O(1) or O(log log n) time, using data structures that
take just O(eT ) or O(eT + eT ) words of space [1, 2]. Among other information,
such data structures store a pointer, from each node v of the CDAWG, to the
longest proper suffix of ℓ(v) (if any) that is a maximal repeat. Note that such
suffix pointers can be charged to suffix links in STT , thus they take overall
O(eT ) words of space.

7

3

Faster Count and Locate Queries in the CDAWG

In this paper we focus on deciding whether a pattern P occurs in T , a key step
in the blind search of Section 2.4. Rather than using the RLBWT for such
decision, we exploit Property 2 and use the grammar induced by CDAWGT .
Our methods will require a data structure, of size linear in the grammar,
that extracts in O(k) time the first k characters of the string produced by a
nonterminal. Previous research described an algorithm that extracts the whole
string produced by a nonterminal in linear time, using just constant working
space, by manipulating pointers in the grammar [12]. This solution does not
guarantee linear time when just a prefix of the string is extracted. A linearsize data structure with the stronger guarantee of constant-time extraction per
character has also been described [11], and this solution can be used as a black
box in our methods. However, since we just need amortized linear time, we
describe a significantly simpler alternative that needs just a level ancestor data
structure (an idea already implicit in [14]) and that will be useful in what follows:
Lemma 1. Let G = (V, E) be the DAG representation of a straight-line program. There is a data structure that: (1) given an integer k and a nonterminal F , allows one to read the first k characters of π(F ) in O(k) time and
O(min{k, h}) words of working space, where h is the height of the parse tree of
F ; (2) given a string S and a nonterminal F , allows one to compute the length
k of the longest prefix of S that matches a prefix of π(F ), in O(k) time and
O(min{k, h}) words of working space. Such data structure takes O(|V |) words
of space.
Proof. We mark the arc of G that connects each node v ′ to its first out-neighbor.
The set of all marked arcs induces a spanning tree τ of G, rooted at the sink
and arbitrarily ordered [11]. In what follows we identify the nodes of τ with
the corresponding nodes of G. We build a data structure that supports level
ancestor queries on τ : given a node v and an integer d, such data structure
returns the ancestor u of v in τ such that the path from the root of τ to u
contains exactly d edges. The level ancestor data structure described in [3, 4]
takes O(|V |) words of space and it answers queries in constant time. To read
the first k characters of string π(F ) = W , we explore the blanket of W [1..k] in
F recursively, as described in Algorithm 1. The tuples in the stack used by the
algorithm have the following fields: (node, lastChild, depth), where node is a
node of G, u′ .outNeighbors is the sorted list of out-neighbors of node u′ in G,
u′ .depth is the depth of u′ in τ , and function label(u′ , v ′ ) returns the character
that labels arc (u′ , v ′ ) in G. Algorithm 1 returns the number of characters read,
which might be smaller than k. A similar procedure can be used for computing
the length of the longest prefix of π(F ) that matches a prefix of a query string.
Every type of operation in Algorithm 1 takes constant time, it can be charged
to a distinct character in the output, and it pushes at most one element on the
stack. Thus, the stack contains O(k) tuples at every step of the algorithm. It
is also easy to see that the stack never contains more elements than the length
of the longest path from the node of G that corresponds to F to the sink.
8

If necessary, Algorithm 1 can be modified to take constant time per character:
Corollary 1. Let G = (V, E) be the DAG representation of a straight-line
program. There is a data structure that takes O(|V |) words of space and that,
given a nonterminal F , allows one to read the characters of π(F ), from left
to right, in constant time per character and in O(min{k, h}) words of working
space, where h is the height of the parse tree of F .
Proof. After having printed character i of π(F ), the time Algorithm 1 has
to wait before printing character i + 1 is always bounded by a constant, except when the procedure repeatedly pops tuples from the stack. This can be
avoided by preventively popping a tuple t for which t.lastChild has reached
|t.node.outNeighbors| after Line 7 is executed, before pushing new tuples on
the stack.
Moreover, Lemma 1 can be generalized to weighted DAGs, by storing in
each node of τ the sum of weights of all edges from the node to the root of
τ , by saving sums of weights in the tuples on the stack, and by summing and
subtracting the weights of the arcs of the DAG:
Corollary 2. Let G = (V, E) be an ordered DAG with a single sink and with
weights on the arcs, and let the weight of a path be the sum of weights of all its
arcs. There is a data structure that, given an integer k and a node v, reports
the weights of the first k paths from v to the sink in preorder, in constant time
per path and in O(min{k, h}) words of working space, where h is the length of
a longest path from v to the sink. Such data structure takes O(|V |) words of
space.
Lemma 1 is all we need to verify in linear time whether a pattern occurs in
the indexed text:
Theorem 1. Let T ∈ [1..σ]n be a string. There is a data structure that takes
O(eT ) words of space, and that counts (respectively, reports) all the occ occurrences of a pattern P ∈ [1..σ]m in O(m) time (respectively, in O(m + occ) time)
and in O(min{m, hT }) words of working space.
Proof. We assume that every node v ′ of CDAWGT stores in a variable v ′ .freq
the number of occurrences of ℓ(v ′ ) in T . Recall that, for a node v ′ of CDAWGT ,
ℓ(v ′ ) = π(F1 )π(F2 ) · · · π(Fk ) · W , where Fp for p ∈ [1..k] are nonterminals of the
grammar, and W is the maximal repeat that labels the node w′ of CDAWGT
that is reachable from v ′ by a suffix pointer. For each arc (u′ , v ′ ) of CDAWGT ,
we store a pointer to the nonterminal Fp of v ′ that corresponds to u′ . We
perform a blind search for P in CDAWGT as described in Section 2.4: either the
search is unsuccessful, or it returns a node v ′ of CDAWGT and an integer interval
[i..j] such that, if P occurs in T , then P = V [i..j] where V = ℓ(v ′ ), and the
number of occurrences of P in T is v ′ .freq. To decide whether P occurs in T ,
we reconstruct the characters in V [i..j] as follows (Figure 1a). Clearly i belongs
to a π(Fp ) for some p, and such Fp can be accessed in constant time using the
9

pointers described at the beginning of the proof. If i is the first position of π(Fp ),
we extract all characters of π(Fp ) by performing a linear-time traversal of the
parse tree of Fp . Otherwise, we extract the suffix of π(Fp ) in linear time using
Lemma 1. Note that j must belong to π(Fq ) for some q > p, since the search
reaches v ′ after right-extending a suffix of an in-neighbor u′ of v ′ that belongs to
the equivalence class of u′ (recall Property 1). We thus proceed symmetrically,
traversing the entire parse tree of Fp+1 . . . Fq−1 and finally extracting either
the entire π(Fq ) or a prefix. Finally, j could belong to W , in which case we
traverse the entire parse tree of Fp+1 . . . Fk and we recur on w′ , resetting j to
Pk
j − x=1 |π(Fx )|. If the verification is successful, we proceed to locate all the
occurrences of P in T as described in Section 2.4.
Note that the data structure in Theorem 1 takes actually O(min{eT , eT })
words of space, since one could index either T or T for counting and locating.
Lemma 1 can also be used to report the top k occurrences of a pattern P in T ,
according to the popularity of the right-extensions of P in the corpus:
Corollary 3. Let P be a pattern, let P = {p1 , p2 , . . . , pm } be the set of all its
starting positions in a text T . Let sequence Q = q1 , q2 , . . . , qm be such that qi ∈ P
for all i ∈ [1..m], qi 6= qj for all i 6= j, and i < j iff T [qi ..|T |] is lexicographically
smaller than T [qj ..|T |]. Let sequence S = s1 , s2 , . . . , sm be such that si ∈ P for
all i ∈ [1..m], si 6= sj for all i 6= j, and i < j iff the frequency of T [si ..si + x]
in T is not smaller than the frequency of T [sj ..sj + x] in T (with ties broken
lexicographically), where x is the length of the longest common prefix between
T [si ..|T |] and T [sj ..|T |]. There is a data structure that allows one to return
the first k elements of sequence Q or S in constant time per element and in
O(min{k, hT }) words of working space. Such data structure takes O(eT ) words
of space.
Proof. Recall that Theorem 1 builds the spanning tree τ of Lemma 1 on the
reversed CDAWG that represents a straight-line program of T . To print Q,
we build τ and the corresponding level-ancestor data structure on CDAWGT ,
connecting each vertex of the CDAWG to its lexicographically smallest outneighbor, and storing in each node of τ the sum of lengths of all edges from the
node to the root of τ . Given the locus v ′ of P in CDAWGT , we can print the first
k elements of Q in O(k) time and in O(min{k, h}) words of space, where h is the
length of a longest path from v ′ to the sink of CDAWGT , by using Corollary 2.
To print S we add to each node of CDAWGT an additional list of children, sorted
by nondecreasing frequency with ties broken lexicographically, and we build the
spanning tree τ by connecting each vertex of CDAWGT to its first out-neighbor
in such new list.
Finally, Theorem 1 allows one to reconstruct the label of any arc of the
CDAWG, in linear time in the length k of such label. This improves the
O(k log log n) bound described in [2], where n is the length of the uncompressed
text, and it removes the eT term from the space complexity, since RLBWTT is
not needed.
10

Figure 1: (a) The verification step of pattern search, implemented with the
CDAWG. Notation follows Theorem 1. (b) Reconstructing the label of an arc
of the CDAWG. Notation follows Theorem 2.
Theorem 2. There is a data structure that allows one to read the k characters
of the label of an arc (v ′ , w′ ) of CDAWGT , in O(k) time and in O(min{k, hT })
words of working space. Such data structure takes O(eT ) words of space.
Proof. Recall that every arc (v ′ , w′ ) that does not point to the sink of CDAWGT
is a right-maximal substring of T . If it is also a maximal repeat, then we can
already reconstruct it as described in Theorem 1, storing a pointer to such maximal repeat, starting extraction from the first nonterminal of the maximal repeat,
and recurring to the maximal repeat reachable from its suffix pointer. Otherwise, let W = ℓ(w′ ) = V U , where U is the maximal repeat that corresponds to
the node u′ reachable from the suffix pointer of w′ , and let V = π(F1 ) · · · π(Fk )
where Fp for p ∈ [1..k] are nonterminals in the grammar. The label of (v ′ , w′ )
coincides with suffix W [i..|W |], and its length is stored in the index.
If i ≤ |V |, let V [i..|V |] = X · π(Fp+1 ) · · · π(Fk ) for some p. To reconstruct
U , we traverse the whole parse tree of Fk , Fk−1 , . . . , Fp+1 , and we reconstruct
the suffix of length |X| of π(Fp ) using Lemma 1. Otherwise, if i > |V |, we
could recur to U , resetting i to i − |V | (Figure 1b). Let U = V ′ U ′ , where U ′
is the maximal repeat that corresponds to the node reachable from the suffix
pointer of u′ . Note that it could still happen that i > |V ′ |, thus we might need
to follow a sequence of suffix pointers. During the construction of the index, we
store with arc (v ′ , w′ ) a pointer to the first maximal repeat t′ , in the sequence of
suffix pointers from w′ , such that |ℓ(t′ )| ≥ |ℓ(v ′ , w′ )|, and such that the length
of the longest proper suffix of ℓ(t′ ) that is a maximal repeat is either zero or
smaller than |ℓ(v ′ , w′ )|. To reconstruct ℓ(v ′ , w′ ), we just follow such pointer and
proceed as described above.
Reading the label of an arc that is directed to the sink of CDAWGT can be
implemented in a similar way: we leave the details to the reader.
We can also read the label of an arc (v ′ , w′ ) from right to left, with the
stronger guarantee of taking constant time per character:

11

Corollary 4. There is a data structure that allows one to read the k characters
of the label of an arc (v ′ , w′ ) of CDAWGT , from right to left, in constant time per
character and in O(min{k, hT }) words of working space. Such data structure
takes O(eT ) words of space.
Proof. We proceed as in Theorem 2, but we also keep the tree τ of explicit
Weiner links from every node of CDAWGT , imposing an arbitrary order on the
children of every node t of τ , and we build a data structure that supports level
ancestor queries on τ . As in Theorem 2, we move to a maximal repeat u′ such
that |ℓ(u′ )| ≥ |ℓ(v ′ , w′ )|, and such that the length of the longest proper suffix of
ℓ(u′ ) that is a maximal repeat is either zero or smaller than |ℓ(v ′ , w′ )|. Then, we
move to node x′ = levelAncestor(u′ , 1), we reconstruct ℓ(x′ ) from right to left
using Corollary 1, and we use levelAncestor(u′ , 2) to follow an explicit Weiner
link from x′ . After a sequence of such explicit Weiner links we are back to u′ ,
and we reconstruct from right to left the prefix of ℓ(v ′ , w′ ) that does not belong
to the longest suffix of ℓ(u′ ) that is a maximal repeat, using again Corollary
1.
Since the label of arc (v ′ , w′ ) is a suffix of ℓ(w′ ), and since the label of
every node w′ of the CDAWG can be represented as π(F ) · ℓ(u′ ), where F is
a nonterminal of the grammar and u′ is the longest suffix of ℓ(w′ ) that is a
maximal repeat, we could implement Corollary 4 by adding to the grammar
the nonterminals W ′ and U ′ and a new production W ′ → F U ′ for nodes w′
and u′ , and by using Corollary 1 for extraction. This does not increase the size
of the grammar asymptotically. Note that the subgraph induced by the new
nonterminals in the modified grammar is the reverse of the compact suffix-link
tree of T .

4

Faster Matching Statistics in the CDAWG

A number of applications, including matching statistics, require reading the
label of an arc from left to right : this is not straightforward using the techniques
we described, since the label of an arc (v ′ , w′ ) can start e.g. in the middle of one
of the nonterminals of w′ rather than at the beginning of one such nonterminal
(see Figure 1b). We circumvent the need for reading the characters of the label
of an arc from left to right in matching statistics, by applying the algorithm in
Theorem 1 to prefixes of the pattern of exponentially increasing length:
Lemma 2. There is a data structure that, given a string S and an arc (v ′ , w′ )
of CDAWGT , allows one to compute the length k of the longest prefix of S that
matches a prefix of the label of (v ′ , w′ ), in O(k) time and in O(min{k, hT })
words of working space. Such data structure takes O(eT ) words of space.
Proof. Let γ = (v ′ , w′ ). If ℓ(γ) is a maximal repeat of T , we can already read
its characters from left to right by applying Theorem 1. Otherwise, we perform
a doubling search over the prefixes of S, testing iteratively whether S[1..2i ]
matches a prefix of ℓ(γ) for increasing integers i, and stopping when S[1..2i ]
12

does not match a prefix of ℓ(γ). We perform a linear amount of work in the
length of each prefix, thus a linear amount of total work in the length of the
longest prefix of S that matches a prefix of ℓ(γ).
We determine whether S[1..2i ] is a prefix of ℓ(γ) as follows. Recall that
an arc of CDAWGT (or equivalently of STT ) is a right-maximal substring of
T , therefore it is also a node of STT . We store for each arc γ of CDAWGT
the interval range(γ) of the corresponding string in BWTT . Given S[1..2i ], we
perform a blind search on the CDAWG, simulating a blind search on STT and
using Property 3 to keep the BWT intervals of the corresponding nodes of STT
that we meet. We stop at the node v of the suffix tree at which the blind search
fails, or at the first node whose interval does not contain range(γ) (in which
case we reset v to its parent), or at the last node reached by a successful blind
search in which the BWT intervals of all traversed nodes contain range(γ). In
the first two cases, we know that the longest prefix of S that matches ℓ(γ) has
length smaller than 2i . Then, we read (but don’t explicitly store) the label of
v in linear time as described in Theorem 1, finding the position of the leftmost
mismatch with S[1..2i ], if any.
Lemma 2 is all we need to implement matching statistics with the CDAWG:
Theorem 3. There is a data structure that takes O(eT ) words of space, and
that allows one to compute MSS,T in O(|S|) time and in O(min{µ, hT }) words
of working space, where µ is the largest number in MSS,T .
Proof. We fill array MSS,T from left to right, by implementing with CDAWGT the
classical matching statistics algorithm based on suffix link and child operations
on the suffix tree. Assume that we have computed MSS,T [1..i] for some i. Let
c = S[i + MSS,T [i]] and let U = S[i..i + MSS,T [i] − 1] = V X, where V is the
longest prefix of U that is right-maximal in T , and v is the node of STT with
label V . Assume that we know v and the node v ′ of CDAWGT that corresponds
to the equivalence class of v. Let w′ be the node of CDAWGT that corresponds
to the longest suffix of ℓ(v ′ ) that is a maximal repeat of T . If |ℓ(v)| > |ℓ(w′ )|+ 1,
then MSS,T [i + 1] = MSS,T [i] − 1, since no suffix of U longer than |ℓ(w′ )| + |X|
can be followed by character c. Otherwise, we move to w′ in constant time by
following the suffix pointer of v ′ , and we perform a blind search for X from
w′ . Let ℓ(w′ )X = ZX ′ , where Z = ℓ(z) is the longest prefix of ℓ(w′ )X that is
right-maximal in T , and let z ′ be the node of the CDAWG that corresponds to
the equivalence class of z. If |X ′ | > 0, or if no arc from z ′ is labeled by c, then
again MSS,T [i + 1] = MSS,T [i] − 1. Otherwise, we use Lemma 2 to compute the
length of the longest prefix of S[i + MSS,T [i]..|S|] that matches a prefix of the
arc from z ′ labeled by c. The claimed time complexity comes from Lemma 2
and from standard amortization arguments used in matching statistics.
Note that the data structure in Theorem 3 takes actually O(min{eT , eT })
words of space, since one could index either T or T for computing the matching
statistics vector (in the latter case, S is read from right to left).

13

Another consequence of Property 2 is that we can compute the minimal
absent words of T using an index of size proportional just to the number of
maximal repeats of T and of their extensions:
Lemma 3. There is a data structure that takes O(eT + eT ) words of space, and
that allows one to compute the minimal absent words of T in O(eT + eT + out)
time and in O(λT + min{µT , hT }) words of working space, where out is the size
of the output, λT is the maximum number of left extensions of a maximal repeat
of T , and µT is the length of a longest maximal repeat of T .
Proof. For every arc γ = (v ′ , w′ ) of CDAWGT , we store in a variable γ.order
the order of v ′ among the in-neighbors of w′ induced by Property 1 and used
in CDAWGT (see Section 2.3), and we store in a variable γ.previousChar the
character a, if any, such that aℓ(v ′ )b is a substring of ℓ(w′ ) and b = γ.char is
the first character of ℓ(γ).
Then, we traverse every node v ′ of CDAWGT , and we scan every arc γ =
′
(v , w′ ). If γ.order > 1, then ℓ(v ′ )b, where b = γ.char, is always preceded
by γ.previousChar in T , thus we print aℓ(v ′ )b to the output for all a that
label explicit and implicit Weiner links from v ′ and that are different from
γ.previousChar. If γ.order = 1 then ℓ(v ′ )b is a left-maximal substring of T , so
we subtract the set of all Weiner links of w′ from the set of all Weiner links of
v ′ by a linear scan of their sorted lists, and we print aℓ(v ′ )b to the output for all
characters a in the resulting list. Note that the same Weiner link of v ′ could be
read multiple times, for multiple out-neighbors w′ of v ′ . However, every such
access can be charged either to the output or to a corresponding Weiner link
from w′ , and each w′ takes part in at most one such subtraction. It follows that
the time taken by all list subtractions is O(eT + out).
We reconstruct each ℓ(v ′ ) in linear time as described in Theorem 1.

Acknowledgements
We thank the anonymous reviewers for simplifying some parts of the paper, for
improving its overall clarity, and for suggesting references [11, 12, 14] and the
current version of Lemma 3.

References
[1] Djamal Belazzougui and Fabio Cunial. Representing the suffix tree with the
CDAWG. In CPM 2017, volume 78 of Leibniz International Proceedings in
Informatics (LIPIcs), pages 7:1–7:13. Schloss Dagstuhl–Leibniz-Zentrum
fuer Informatik, 2017.
[2] Djamal Belazzougui, Fabio Cunial, Travis Gagie, Nicola Prezza, and Mathieu Raffinot. Composite repetition-aware data structures. In CPM 2015,
Lecture Notes in Computer Science, pages 26–39. Springer, 2015.

14

[3] Michael A Bender and Martın Farach-Colton. The level ancestor problem
simplified. Theoretical Computer Science, 321(1):5–12, 2004.
[4] Omer Berkman and Uzi Vishkin. Finding level-ancestors in trees. Journal
of Computer and System Sciences, 48(2):214–230, 1994.
[5] Anselm Blumer, Janet Blumer, David Haussler, Ross McConnell, and Andrzej Ehrenfeucht. Complete inverted files for efficient text retrieval and
analysis. Journal of the ACM, 34(3):578–595, 1987.
[6] Maxime Crochemore, Chiara Epifanio, Roberto Grossi, and Filippo
Mignosi. Linear-size suffix tries. Theoretical Computer Science, 638:171–
178, 2016.
[7] Maxime Crochemore and Christophe Hancart. Automata for matching
patterns. In Handbook of Formal Languages, pages 399–462. Springer, 1997.
[8] Maxime Crochemore, Filippo Mignosi, and Antonio Restivo. Automata
and forbidden words. Information Processing Letters, 67(3):111–117, 1998.
[9] Maxime Crochemore and Renaud Vérin. Direct construction of compact
directed acyclic word graphs. In CPM 1997, volume 1264 of Lecture Notes
in Computer Science, pages 116–129. Springer, 1997.
[10] Travis Gagie. Large alphabets and incompressibility. Information Processing Letters, 99(6):246–251, 2006.
[11] Leszek Gasieniec, Roman M Kolpakov, Igor Potapov, and Paul Sant. Realtime traversal in grammar-based compressed files. In DCC 2005, page 458,
2005.
[12] Leszek Gasieniec and Igor Potapov. Time/space efficient compressed pattern matching. Fundamenta Informaticae, 56(1-2):137–154, 2003.
[13] Dan Gusfield. Algorithms on strings, trees and sequences: computer science
and computational biology. Cambridge University Press, 1997.
[14] Markus Lohrey, Sebastian Maneth, and Carl Philipp Reh. Traversing
grammar-compressed trees with constant delay. In DCC 2016, pages 546–
555, 2016.
[15] Luı́s S. Russo, Gonzalo Navarro, and Arlindo L. Oliveira. Fully-compressed
suffix trees. ACM Transactions on Algorithms, 7(4):53, 2011.
[16] Veli Mäkinen and Gonzalo Navarro. Succinct suffix arrays based on runlength encoding. In CPM 2005, Lecture Notes in Computer Science, pages
45–56. Springer, 2005.
[17] 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.
15

[18] Gonzalo Navarro and Luis MS Russo. Fast fully-compressed suffix trees.
In DCC 2014, pages 283–291. IEEE, 2014.
[19] Mathieu Raffinot. On maximal repeats in strings. Information Processing
Letters, 80(3):165–169, 2001.
[20] Jouni Sirén, Niko Välimäki, Veli Mäkinen, and Gonzalo Navarro. Runlength compressed indexes are superior for highly repetitive sequence collections. In SPIRE 2008, Lecture Notes in Computer Science, pages 164–175,
2008.
[21] Takuya Takagi, Keisuke Goto, Yuta Fujishige, Shunsuke Inenaga, and Hiroki Arimura. Linear-size CDAWG: new repetition-aware indexing and
grammar compression. In String Processing and Information Retrieval 24th International Symposium, SPIRE 2017, Palermo, Italy, September
26-29, 2017, Proceedings, pages 304–316, 2017. arXiv:1705.09779.

16

