Maxime Crochemore

Renaud V Erin

On Compact Directed Acyclic Word Graphs

The Directed Acyclic Word Graph (DAWG) is a space-e cient data structure to treat and analyze repetitions in a text, especially in DNA genomic sequences. Here, we consider the Compact Directed Acyclic Word Graph of a word. We give the rst direct algorithm to construct it. It runs in time linear in the length of the string on a xed alphabet. Our implementation requires half the memory space used by DAWGs.

Introduction

One of the most surprising facts related to pattern matching and discovered by Ehrenfeucht et al. 2] is that the size of the minimal automaton accepting the su xes of a word is linear. The surprise is due to the maximal number of subwords that may occur in a word: it is quadratic according to the length of the word. This is obviously true if the alphabet is unbounded, but still holds if the alphabet contains at least two letters. In addition to the previous result, Ehrenfeucht et al. proved that the automaton can be built in linear time, which is indeed a consequence of the previous fact but does not come readily from it.

In the present article, we consider the compact implementation of the automaton and show that it has a direct construction that runs in linear time. Fast and space-economical methods for this construction are important because the automaton serves as an index on the underlying word, and, as such, is involved in several combinatorial algorithms on words.

Historically, the rst linear-size graph to represent the subwords of a word, called the Directed Acyclic Word Graph (DAWG), was described in 2] together with a linear-time construction. When terminal states are added to the DAWG, as shown in 8], the structure becomes the minimal automaton accepting the su xes of the word. Regarded as an automaton accepting the subwords of the word, i.e. setting all states as terminal states, the DAWG is not always a minimal automaton. Indeed, this latter automaton can be slightly smaller, but its construction satis es the same properties ( 8,3,[START_REF] Crochemore | Transducers and repetitions[END_REF]) though the algorithms become a bit more tricky. Basically, DAWGs provide an implementation of indexes on texts 4]. The index on a text T helps searching it for various patterns. For instance, it leads to an e cient solution to the string-matching problem, searching text T for a word w. The typical running time of a query is O(jwj) on a xed alphabet, and is O(jwj log j j) if the alphabet of the text is unbounded.

Many other e cient solutions to problems on words are applications of DAWGs. They include (see 12]): computing the number of subwords of a word, computing the longest repeated subword of a word, backward DAWG-matching, nding repetitions in words 6], searching for a square 7, 9], computing the longest common subword of a nite set of words and on-line subword matching 10], approximate string-matching 21].

The su x tree is an alternative representation of the subwords of a word that shares with the DAWG essentially the same applications. McCreight 18] introduced the notion and gave an e cient construction after the seminal work of Weiner 22] on a similar structure. Su x trees have been more extensively studied than DAWGs, probably because they display positions of the word in a simpler way although the branching from nodes is not uniform as it is from states of DAWGs. Apostolico 1] lists over forty references on su x trees, and Manber and Myers 17] mention several others (see also 19]). Several variants or implementations of su x trees have been developed, like su x arrays 17], PESTry 16], su x cactus 15], or su x binary search trees 14]. Ukkonen 20] designs an on-line construction of su x trees, and Farach 13] proposes a novel approach leading to a linear-time construction on integer alphabets.

In computational biology, DNA sequences are often only viewed as words over the alphabet fa; c; g; tg of nucleotides. In this form, they are objects for linguistic and statistic analysis. For this purpose, su x automata (or su x trees) are extremely useful data structures, but the bottleneck to using them is their size. The indexes has to be kept in main memory and their sizes limit their use. The size of available sequences is steadily growing, and therefore saving memory space is wanted both for the construction of the index and for its use. The Compact Directed Acyclic Word Graph (CDAWG) keeps the direct access to information while requiring less memory space. The structure has been introduced by Blumer et al. 4,5]. The implementation is obtained by deleting all states of outdegree one and their corresponding transitions (excepting terminal states).

We present an algorithm that builds directly compact DAWGs. This construction avoids constructing the DAWG rst, which makes it suitable for the presently available DNA sequences (about 1:5 million nucleotides long for the longest sequences). Experiments show that our implementation saves half of the memory space required for ordinary DAWGs and su x trees. At the same time, the reduction of the number of states (2=3 less) and of transitions (about half less) makes the applications run faster. Time and space are saved simultaneously. The memory space used by our implementation of compact DAWGs requires about 6n integers for a word of length n. This is to be compared with 7n for DAWGs, 8n for su x trees. It is just 2n for su x arrays, but this is paid by a slower access to subwords.

This article is organized as follows. In Section 2 we recall the basic notions on DAWGs. Section 3 introduces the compact DAWG, also called compact su x automaton, and contains the bounds on its size. We show in Section 3.4 how to build the compact DAWG from the DAWG in linear time with respect to the size of this latter structure. Direct construction algorithm for the compact DAWG is given in Section 4.

2 De nitions Let be a nonempty alphabet and the set of words over , with " as the empty word. If w is a word in , jwj denotes its length, w i its i th letter, and w i::j its factor (subword) w i w i+1 : : : w j . If w = xyz with x; y; z 2 , then x, y, and z are factors or subwords of w, x is a pre x of w, and z is a su x of w. S(x) denotes the set of all su xes of x and F(x) the set of its factors.

For an automaton, the tuple (p; a; q) denotes a transition of label a starting at p and ending at q. A roman letter is used for mono-letter transitions, a greek letter for multi-letter transitions. Moreover, (p; ] denotes a transition from p for which is a pre x of its label. In this notation the target state is not given.

Here, we recall the de nition of the DAWG, and a theorem about its implementation and size both proved in 3] and 9].

De nition 1. The Su x Automaton of a word x, denoted DAWG(x), is the minimal deterministic automaton (not necessarily complete) that accepts S(x), the ( nite) set of su xes of x. For example, Figure 1 shows the DAWG of the word gtagtaaac. States that are double circled are terminal states.

Theorem 2. The size of the DAWG of a word x is O(jxj) and the automaton can be computed in time O(jxj). The maximum number of states of the automaton is 2jxj 1, and the maximum number of edges is 3jxj 4.

Recall that the right context (according to S(x)) of a factor u of x is u 1 S(x). The syntactic congruence associated with S(x) is denoted by S(x) and is de ned, for x; u; v 2 , by: u S(x) v () u 1 S(x) = v 1 S(x). We call classes of factors the congruence classes of the relation S(x) . The longest word of a class of factors is called the representative of the class. States of DAWG(x) are exactly the classes of the relation S(x) . Since this automaton is not required to be complete, the class of words not occurring in x, corresponding to the empty right context, is not a state of DAWG(x).

Among the congruence classes we make a selection of classes that are called strict classes of factors of S(x) and that are de ned as follows. De nition 3. Let u be a word of C, a class of factors of S(x) . If at least two letters a and b of exist such that ua and ub are factors of x, then C is called a strict class of factors of S(x) .

We also introduce the function endpos x : F(x) ! N, de ned, for a word u, by: endpos x (u) = minfjwj j w pre x of x and u su x of wg and the function length x de ned on states of DAWG(x) by: length x (p) = juj; with u representative of p: The word u also corresponds to the concatenated labels of transitions of the longest path from the initial state to p in DAWG(x). Transitions that belong to the spanning tree of longest paths from the initial state are called solid transitions. Equivalently, for each transition (p; a; q) we have the property: (p; a; q) is solid () length x (q) = length x (p) + 1: The function length x works as well for multi-letter transitions (transitions labeled by non-empty words), just replacing 1 in the above equivalence by the length of the label of the transition from p to q. This extends the notion of solid transitions to multi-letter transitions: (p; ; q) is solid () length x (q) = length x (p) + j j: In addition, we de ne the su x link function on states of DAWG(x) by the next statement.

De nition 4. Let p be a state of DAWG(x), di erent from the initial state, and let u be a word of the equivalence class p. The su x link of p, denoted by s x (p), is the state q which representative v is the longest su x z of u such that u 6 S(x) z. Note that, consequently to this de nition, we have length x (q) < length x (p). Then, by iteration, su x links induce su x paths in DAWG(x), which is an important notion used by the construction algorithm. Indeed, as a consequence of the above inequality, the sequence (p; s x (p); s 2 x (p); :::) is nite and ends at the initial state of DAWG(x). This sequence is called the su x path of p.

De nition

Compaction of DAWGs is based on the deletion of some states and their outgoing transitions. This is possible by using multi-letter transitions and selecting strict classes of factors de ned in the previous section (De nition 3). The de nition of CDAWGs parallels the de nition of su x trees obtained from ordinary digital tries of all su xes of a word. Indeed, disregarding how the end-marker required by su x trees is managed, the CDAWG may be viewed as well as a compact version of the DAWG or as a minimized (in the sense of automata theory) version of the su x tree (see Figure 2).

The compact DAWG is de ned as follows.

De nition 5. The Compact Directed Acyclic Word Graph of a word x, denoted by CDAWG(x), is the compaction of DAWG(x) obtained by keeping only states that are either terminal states or strict classes of factors according to S(x) , and by labeling transitions accordingly. Consequently to De nition 3, strict classes of factors correspond to states that have an outdegree greater than one. So, we can delete every state having outdegree one exactly, except terminal states. Note that initial and nal states are terminal states, so they are not deleted. An example of CDAWG is displayed in Figure 3.

The construction of the DAWG of a word containing repetitions shows that many states have outdegree one only. For example, in Figure 1, the DAWG of the word gtagtaaac has 12 states, 7 of which have outdegree one; it has 18 transitions. Figure 3 displays the compacted version, obtained after deletion of the 7 states, using multi-letter transitions. The resulting automaton has only 5 states and 11 edges.

According to experiments made on biological DNA sequences, considering them as words over the alphabet = fa; c; g; tg, we got that more than 60% of states have outdegree one. So, the deletion of these states is worth, it provides an important saving. The average analysis of the number of states and edges in done in 5] in a Bernouilly model of probability.

When a state p is deleted, the deletion of its outgoing edges is realized by concatenating their label to the labels of incoming edges. For example, let r and p be states linked by a transition (r; b; p). The edges (r; b; p) and (p; a; q) are replaced by the edge (r; ba; q) if p is deleted. By recursion, this extends to every multi-letter transition (r; ; p).

In the example of Figure 3, one can note that, inside the word gtagtaaac, occurrences of g are followed by ta, and those of t and gt by a. The word gta is the representative of state 2, and there is no state corresponding to subwords g, gt, nor t. State I is directly connected to state 2 by edges (I,gta,2) and (I,ta,2). States 1 and 2 of Figure 1 no longer exist.

The su x links de ned on states of DAWGs remain valid when we reduce them to CDAWGs due to the next lemma, which proof is straightforward.

Lemma6. If p is a state of CDAWG(x), then s x (p) is a state of CDAWG(x).

Size bounds

By Theorem 2 DAWG(x) is linear in jxj. As we shall see below (Section 3.3), labels of multi-letter transitions are implemented in constant space. So, the size of CDAWG(x) is also O(jxj). Meanwhile, as we delete many states and edges, we review the exact bounds on the number of states and edges of CDAWG(x). They are respectively denoted by States(x) and Edges(x).

Lemma7. Given x 2 , if jxj = 0, then States(x) = 1; if jxj = 1, then States(x) = 2; otherwise jxj 2 and 2 States(x) jxj + 1.

The upper bound on the number of states is reached when x is in the form a jxj , for a 2 . Proof. For jxj 1, this is a mere veri cation. Assume now jxj 2. The lower bound is obvious and obtained when x is composed of pairwise di erent letters.

Consider the su x tree of x$, where $ is a marker. It has exactly jxj+1 leaves and at most jxj internal nodes. Its minimization into CDAWG(x) compacts all leaves into the nal state F, and possibly put together other nodes. Removing the marker does not change the number of states. So, we have States(x) jxj+1.

The word a jxj satis es this property since each su x a j0j , a j1j , . . . , a jxj represents exactly one class. So, we have jxj+1 classes and the same number of states. Lemma 8. Given x 2 , if jxj = 0, Edges(x) = 0; if jxj = 1, Edges(x) = 1; otherwise jxj 2 and Edges(x) 2jxj 2.

The upper bound on the number of edges is reached when x is in the form a jxj 1 c, for a and c two di erent letters of . Proof. For jxj 1, this is a mere veri cation. Assume now jxj 2.

If x is in the form a jxj , the number of edges is exactly jxj. So, we have to prove the upper bound for a word x containing at least two di erent letters. Consider the su x tree of x$. It has exactly jxj + 1 leaves. It has at most jxj 1 internal nodes in this situation (because the root has outdegree 3). The number of edges in the tree is at most 2jxj 1. After minimization into CDAWG(x) and removing the marker, all edges may remain except the edge labeled by $. This give the upper bound of 2jxj 2.

The automaton CDAWG(a jxj 1 c), for a and c two di erent letters of , has jxj states and exactly 2jxj 2 edges, distributed as jxj 1 solid edges and jxj 1 non-solid edges. Figure 6 displays a CDAWG having the maximum number of edges for a word of length 6.

Implementation and experiments

Transition matrices and adjacency lists are two classical implementations of automata. The rst one gives a direct access to transitions, but the memory space required is O(States(x) card( )). The second implementation stores only the exact number of transitions in memory, but needs O(log card( )) time to access them with standard searching techniques. When the size of the alphabet is great and the transition matrix is sparse, adjacency lists are obviously preferable. Otherwise, like for genomic sequences, transition matrix is a better choice, as shown by the experiments below. So, we only consider here transition matrices to implement CDAWGs. We now describe the exact implementation of states and edges. We do this on a four-letter alphabet, so characters take 0:25 byte. We use integers encoded with 4 bytes. For each state, to encode the target state of outgoing edges, transitions matrices need a vector of 4 integers. Adjacency lists need, for each edge, 2 integers, one for the target state and another one for the pointer to the next edge.

The basic information required to construct the DAWG is composed of a table to implement the function s x and one boolean value (0:125 byte) for each edge to know if it is solid or not. For the CDAWG, in order to implement multiletter transitions, we need one integer for the endpos x value of each state, and another integer for the label length of each edge. And that is all. Indeed, we can nd the label of a transition by cutting o the length of this transition from the endpos x value of its target state. Then, we get both the p x i x i+1 : : : x j q etat p a `; q etat q end-pos j a = x i `= j i + 1 Fig. 7. Implementation of states and arcs in CDAWGs.

position of the label in the source and its length. Figure 7 illustrates this implementation. Keeping the source in memory is negligible considering the global size of the automaton (0:25 byte by character). This is quite a convenient solution also used for su x trees. Then, respectively for transitions matrices and adjacency lists, each state requires 20:5 and 17:13 bytes for the DAWG, and 40:5 and 41:21 bytes for the CDAWG. As a reference, su x trees, as implemented by McCreight 18], need 28:25 and 20:25 bytes per state. Moreover, for CDAWG and su x trees the source has to be stored in main memory. Theoretical average numbers of states, calculated by Blumer et al. ( 5]), are 0:54n for CDAWG, 1:62n for DAWG, and 1; 62n for su x trees, when n is the length of x. This gives respective sizes in bytes per character of the source: 45:68 and 32:70 for su x trees, 33:26 and 27:80 for DAWGs, and 22:40 and 22:78 for CDAWGs.

Considering the complete data structures required for applications, the function endpos x has to be added for the DAWG and the Su x Tree. In addition, the occurrence number of each factor has to be stored in each state for all the structures. Therefore, the respective sizes in bytes per character of the source become : 58:66 and 45:68 for su x trees, 46:24 and 40:78 for DAWGs, and 24:26 and 24:72 for CDAWGs.

Table 1 compares the sizes of implementations of DAWGs and CDAWGs meant for applications to DNA sequences. Sizes for random words of di erent lengths on a four-letter alphabet are also given. DNA sequences are Saccharomyces cerevisiae yeast chromosome II (chro II), a contig of Escherichia Coli DNA sequence (coli), and contigs 1 and 115 of Bacillus Subtilis DNA sequence (bs). Number of states and edges according to the length of the source and the memory space gain are displayed. Theoretical average ratios are given, computed from 5]. First, we observe there are 2=3 less states in the CDAWG, and near of half edges. Second, the memory space saving is about 50%. Third, the num-4 Direct Construction of CDAWG In this section, we give the direct construction of CDAWGs. The running time of the algorithm is linear in the size of the input word x on a xed alphabet. The memory space is proportional to the size of the automaton, and consequently is also linear by Lemmas 7 and 8.

Algorithm

Since the CDAWG of x is a minimization of its su x tree, it is rather natural to base the direct construction on McCreight's algorithm 18]. Meanwhile, properties of the DAWG construction are also used, especially the su x link function (notion that is di erent from the su x links of McCreight's algorithm), lengths of longest paths, and positions, as explained in the previous section.

First, we introduce the notions used by the algorithm, some of them are taken from 18]. The algorithm constructs the CDAWG of the word x of length n, noted x 0::n 1 . The automaton is de ned by a set of states and transitions, where I and F denotes the initial and the nal states respectively. A partial path represents a connected sequence of edges between two states of the automaton.

A path is a partial path that begins at I. The label of a path is the concatenation of the labels of corresponding edges.

The locus, or exact locus, of a string is the end of the path labeled by the string. The contracted locus of a string is the locus of the longest pre x of whose locus is de ned. -Preliminary Algorithm Basically, the algorithm that builds CDAWG(x) inserts into the current automaton the paths corresponding to all the su xes of x, from the longest to the shortest su x. We de ne suf i as the su x x i::n 1 of x. We denote by A i the automaton constructed after the insertion of all the suf j for 0 j i. In this gure (and the following), the dashed edges represent su x links, links that are de ned on states and that are used in the next section.

At the beginning of the algorithm the automaton is initialized with the two states I and F only. At step i (i > 0), the algorithm inserts a path corresponding to suf i into A i 1 and produces A i . The main loop of the algorithm satis es the following invariant properties: P1: at the beginning of step i, all su xes suf j , 0 j < i, are paths in A i 1 . P2: at the beginning of step i, the states of A i 1 are in one-to-one correspondence with the longest common pre xes of pairs of su xes longer than suf j . We de ne head i as the longest pre x of suf i which is also a pre x of suf j for some j < i. Equivalently, head i is the longest pre x of suf i that is also label of a path in A i 1 . We de ne tail i as head 1 i suf i . Since the path labeled by abbbc ends in the middle of the edge (3,bbbcabbbcb,F), state 4 is created, splitting the edge into (3,bbbc,4) and (4,abbbcb,F). A new edge is created, (4,b,F).

At step i, the preliminary algorithm has to insert tail i from the locus of head i into A i 1 (see Figure 9). To do so, the contracted locus of head i in A i 1 is found with the help of function SlowFind that compares letter-to-letter the right path of A i 1 to suf i . An example of execution of this function is shown in Figure 10.

This part is similar to the corresponding McCreight's procedure, except on a point discussed below (redirection of edges). If there is a state at the end of the path, it is the locus of head i . Otherwise it is created at the middle of the last encountered edge by splitting it. In any case, an edge labeled by tail i is created from the locus of head i to F. The preliminary algorithm is given below.

Preliminary Algorithm 1. For all suf i (i 2 0..n-1]) Do 2.

(q; ) SlowFind(I);

If ( = ") Then 4. insert (q,taili,F); 5.

Else 6.

create v locus of headi splitting (q; ] and insert (v,taili,F); or redirect (q; ] onto v, the last created state;

7. End For all;

8. mark terminal states;

The function SlowFind returns a pair (q; ) such that q is the last encountered state on the path head i , state that is the representative of head i 1 . This keeps accessible the transition that may be split if the state q is not the exact locus of head i , i.e. if 6 = ".

If a non-solid edge is encountered during the execution of SlowFind, its target state has to be duplicated in a clone and the non-solid edge is redirected to this clone. The redirected transition becomes solid. An example of duplication is given in Figure 11.

In some situation, an edge can be redirected. This happens when a state has just been created at the previous step. The edge is redirected to this state and its label is updated accordingly. Such a situation appears in Figure 8 (case v) for the construction of CDAWG(aabbabbc) : the insertion of suf 5 =bbc induces the redirection of the edge (2,babbc,F), which becomes (2,b,3). In the above situation, the su x link of the last created state is unknown during the insertion of the current su x. And the redirections go on until the su x link is found.

Finally, when tail i = " at the end of the construction, terminal states are marked along the su x path of F.

From the above discussion, a proof of the invariance of properties P1 and P2 can be derived. Thus, at the end of the algorithm all subwords of x and only these words are labels of paths in the automaton (property P1). By property P2, states correspond to strict classes of factors (when the longest common pre x of a pair of su xes is not equal to any of them) or to terminal states (when the contrary holds). This gives a sketch of the correctness of the algorithm.

The running time of the preliminary algorithm is O(jxj 2 ) (with an implementation by transition matrix), like is the sum of lengths of all su xes of the word x.

Linear Algorithm To get a linear-time algorithm, we use together properties of DAWGs construction and of su x trees construction. The main feature is the notion of su x links. They are de ned as for DAWGs in Section 2, de nition that remains valid by Lemma 6. They are the clue for the linear running time of the algorithm.

Three elements have to be pointed out about su x links in the CDAWG.

First, we do not need to initialize su x links. Indeed, when suf 0 is inserted, x 0 is obviously a new letter because no letter of x has been scanned so far, which directly induces s x (F)=I. Note that s x (I) is never used, and so never de ned. Second, traveling along the su x path of a state p does not necessarily end at state I. Indeed, with multi-letter transitions, if s x (p)=I we have to treat the su x a 1 (a 2 ) where is the representative of p. And third, su x links induce the following invariant property satis ed at step i: P3: at the beginning of step i, the su x links are de ned for each state of A i 1 according to De nition 4, except maybe for the lastly-created state.

The next remark allows redirections without having to search with SlowFind for existing states belonging to a same class of factors.

Remark. Let have locus p and assume that q = s x (p) is the locus of . Then, p is the locus of su xes of whose lengths are greater than j j.

The algorithm has to deal with su x links each time a state is created. This happens when a state is duplicated, as illustrated by Figure 11, and when a state is created after the execution of SlowFind.

During a duplication, su x links are updated as follows. Let w be the clone of q. In regard to strict classes of factors and De nition 4, the class of w is inserted \between" the ones of q and s x (q). So, we update su x links by setting s x (w) = s x (q) and then s x (q) = w. I q v s r s x Fig. 12. Searching for sx(v) using a su x link.

After the execution of SlowFind, if state v is created, we have to compute its su x link, s x (v). Let be the label of the transition starting at q and ending at v. To compute the su x link of v, the algorithm goes through the path having label from the su x link of q, s = s x (q). The operation is repeated if necessary.

Figure 12 displays a scheme of this search. The thick dashed edges represent paths in the automaton, and the thin dashed edge represents the su x link from q to s. The search, as for the duplication, realizes the insertion of a series of su xes. To travel along the path, we use the function FastFind, similar to the one used in McCreight's algorithm 18], that goes through transitions comparing just the rst letters of their labels. This function returns the last encountered state and edge. Let r and (r; ] be the state and transition returned by FastFind. If r is the exact locus of , it is the wanted state, and we set then s x (v) = r. Else, if (r; ] is a solid edge, then a new node w is created. The edge (r; ] is split, its initial part becomes (r; ; w), and the transition (w,tail i ,F) is added. Such an example is displayed in Figure 13.

The last situation to consider is when (r; ] is non-solid. Then, the edge is replaced by (r; ; v). Such an example is displayed in Figure 14.

In the two last cases, since s x (v) is not found, we run FastFind again with s x (r) and , and this goes on until s x (v) is eventually found, that is, when = ".

FastFind is used in the same manner when a state is created by duplication during the execution of SlowFind.

The discussion shows how su x links are updated to insure that property P3 is satis ed. The operations do not in uence the correctness of the algorithm, sketched in the last section, but yield the following linear-time algorithm. Its time complexity is discussed in the next section. If ( = ") Then 5. insert (q,taili,F); 6. sx(F) q;

7.

If (q 6 = I) Then p sx(q) Else p I; suf i head i i j k q s r Fig. 15. Positions of labels when suf i is inserted. States I,q,v represent the scheme of SlowFind and states I,s,r represent the scheme of searching for sx(q), as in Figure 12.

The complexity of the algorithm essentially depends on the number of branchings made on states of the automaton. We prove that this number is linear, which implies the running times of the statement: O(jxj) with a transition matrix and O(jxj log card( )) with adjacency lists.

Branchings during the execution of the algorithm are done during calls to SlowFind and FastFind. The generic situation is displayed in Figure 15. When SlowFind operates, the current letter of x, pointed by k, is compared with a letter of the label of an edge. Doing so, k is strictly incremented, and never after decremented. During calls to FastFind, each letter comparison increases strictly the value of j, value that never decreases hereafter. This shows that the number of branchings is linear.

This ends the sketch of the proof.

Conclusion

We have considered the Compact Direct Acyclic Word Graph, which is an efcient compact data structure to represent all subwords, or factors, of a word. There are several data structures used to store this set. The present structure provides an interesting space gain compared to the standard DAWG, and also when compared with su x trees. From the theoretical point of view, the upper bounds are of jxj + 1 states and 2jxj 2 transitions. This saves jxj states and jxj transitions of the DAWG and at the same time leads to a faster use. From the practical point of view, experiments on genomic DNA sequences and on random strings display a memory space gain of 50% with respect to the DAWG. Moreover, when the size of the alphabet is small, transition matrices do not take more space than adjacency lists, keeping direct access to transitions. Thus, we can construct the data structure of twice larger strings, keeping them in main memory, which is actually important to get e cient treatments.

This work shows that the CDAWG can be constructed directly. The algorithm is linear in the length of the text (on a xed alphabet). Of course, it is simpler to compute, by reduction, the CDAWG from the DAWG. But the present algorithm saves time and space simultaneously.

Fig. 1 .

 1 Fig. 1. DAWG(gtagtaaac).

Fig. 2 .

 2 Fig.2. Consider a word that has an end-marker. Its su x tree is the compact version of the digital trie of its su xes. Its DAWG is the minimized (in the sense of automata theory) version of the trie. The compact DAWG can be obtained either by minimizing the su x tree of the word or by compacting its DAWG.

Fig. 3 .

 3 Fig. 3. CDAWG(gtagtaaac).

Fig. 4 .

 4 Fig. 4. A CDAWG with the minimum number of states, CDAWG(abcde).

Fig. 5 .

 5 Fig. 5. A CDAWG with the maximum number of states, CDAWG(aaaaa).

Figures 4 and 5 display

 5 Figures 4 and 5 display CDAWGs whose numbers of states are minimum and maximum, respectively, for words of length 5.

Fig. 6 .

 6 Fig.6. A CDAWG with the maximum number of edges, CDAWG(aaaaac).

Figure 8

 8 Figure 8 displays six steps during the construction of CDAWG(aabbabbc).

Fig. 8 .

 8 abbc c

Fig. 9 .Fig. 10 .

 910 Fig.9. Scheme of the insertion of suf i in Ai 1: there already is a path labeled by the pre x headi of suf i .

Fig. 11 .

 11 abbbcabbbcbbc

Fig. 13 .

 13 Fig.[START_REF] Farach | Optimal su x tree construction with large alphabets[END_REF]. Example of execution of FastFind ending with a solid edge during the construction of CDAWG(bbbc). The insertion of suf 1 =bbc leads to create state 1. Then FastFind works from I with path b. This leads to the middle of the edge (I,bb,1) (ii) that is solid. Since we cannot redirect this edge, state 2 is created, splitting (I,bb,1) into (I,b,2) and (2,b,1) (iii). The edge (2,c,F) is added, sx(1) is set to 2, and sx(2) is set to I.

  abbbcabbbcb

  14. Example of execution of FastFind ending with a non-solid edge during the construction of CDAWG(aabbbcabbbcb). When suf 6 =abbbcb is inserted and state 4 created, we have to look for sx(4). As sx(3)=I, we travel along edges from I to nd the end of the path labeled by bbbc with FastFind. As this path ends in the middle of the non-solid edge (1,bcabbbcb,F), this one is replaced by(1,bc,4). Then, FastFind runs again from state 2 with the word bc, in order to eventually nd sx(4).

	Linear Algorithm 1. p I; i 0; 2. While not end of x Do 3. (q; ) SlowFind(p); 4.

  The algorithm that builds the CDAWG of a word x of can be implemented in time O(jxj) and space O(jxj card( )) with a transition matrix, or in time O(jxj log card( )) and space O(jxj) with adjacency lists.Proof. As recalled in section 3.1, the size of CDAWG(x) is linear in the length of x, both in term of number of states and number of edges. Tables endpos x , length x and s x take O(States(x)) space. So, an implementation by transition matrix takes O(jxj card( )) space. By adjacency lists, it takes O(jxj) space.

	x
	tail i
	8. 9. 10. 11. 12. 13. 14. 15. End While; Else create v locus of headi splitting (q; ]; insert (v,taili,F); sx(F) v; nd r = sx(v) with FastFind; p r; update i; 16. mark terminal states; 4.2 Complexity I Theorem 9. I v

Constructing CDAWGs from DAWGs

The DAWG construction is fully exposed and demonstrated in 3], 9] and 11].

As we show in this section, the CDAWG is easily derived from the DAWG. Indeed, we just need to apply the de nition of the CDAWG. The main drawback of this construction of CDAWGs is that it requires the previous construction of DAWGs. Therefore, the overall construction takes time and memory space proportional to DAWG(x), though CDAWG(x) is signicantly smaller. So, it is better to construct the CDAWG directly.