STR Strings and text Data structure
Suffix automaton
Also known as: suffix automaton · DAWG · directed acyclic word graph · endpos · suffix links · CDAWG
A graph in which, from the root, you can walk exactly along the substrings of a text. A state is a class of substrings with the same set of end positions; there are fewer than 2n of them and fewer than 3n transitions, and the whole thing is built online, letter by letter, in linear time.
«Все счастливые семьи похожи друг на друга» (“All happy families are alike”) is the first sentence of Anna Karenina. In the Russian original it can be cut and pasted out of pieces of Eugene Onegin: take «все с» from the sixth stanza of the third chapter, «частливые » from the seventeenth stanza of the fourth, and «друг на друга» (“each other”) turns up whole in the twelfth stanza of the sixth. The whole phrase takes fifteen pieces, and no fewer will do. To cut like this you need a structure that, for each next letter, answers in one step whether the poem has such a continuation. That is the suffix automaton, a graph in which from the root you can walk exactly along the substrings of a text. Type your own phrase: it is assembled from Onegin in the fewest pieces, and for each piece you can see where it comes from and how many times it occurs.
Pushkin’s «Я помню чудное мгновенье» (“I remember a wondrous moment”) is assembled from sixteen pieces of his own novel in verse: «я помню » (“I remember ”) comes from the thirty-third stanza of the first chapter, the one beginning «Я помню море пред грозою» (“I remember the sea before a storm”), and «мгновенье» and «виденье, » from Tatyana’s letter. Everything is searched without regard to case, the letter ё, or the kind of dash and quotes.
The idea
Put all the suffixes of a text into a trie: from the root you can walk exactly along the substrings. But a trie node is a separate substring, and Onegin has 9,648,463,959 of them. Let us merge nodes with the same future. For a substring x denote by endpos(x) the set of positions where its occurrences end. In the word «колокол» (kolokol, “bell”), «л», «ол» and «кол» have the same ends, the third and seventh letters, while «окол», «локол», «олокол» and «колокол» end only at the seventh. Strings with common ends continue alike: whatever is appended on the right, the occurrences end in the same places. So they can be stored as one state.
If non-empty strings u and w, |u| ≤ |w|, have the same ends, then u is a suffix of w, and any string longer than u, shorter than w and also a suffix of w has the same ends.
At any common end both u and w end, so the short one is a suffix of the long one. Let x lie between them: u is a suffix of x, x a suffix of w. Each occurrence of w carries an occurrence of x with the same end, each occurrence of x an occurrence of u: endpos(w) ⊆ endpos(x) ⊆ endpos(u) = endpos(w).
So a state of the automaton is the longest string of a class and its consecutive suffixes, down to some length. Denote the length of the longest by len. The next, shorter suffix occurs more often and lies in a different class; that class is pointed to by the suffix link link. The links form a tree rooted at the class of the empty string: a parent’s ends include its children’s ends, and different children have disjoint ends. So the number of occurrences of any substring is the number of ends of its class, and all of them are counted in one bottom-up pass over the tree.
A state is a class of substrings with the same set of ends. A transition by letter c leads from the class of strings x to the class of strings xc; the suffix link leads to the class of the longest suffix with more ends. Such a graph is built online, letter by letter, and has fewer than 2n states and 3n transitions.
Construction letter by letter
Let the automaton of text T be ready, with last the state of the whole of T. We append a letter c.
- A new state cur for the string Tc: len(cur) = len(last) + 1.
- Walk from last along suffix links. While state p has no transition by c, add a transition to cur: the suffixes of T that c never followed before are now continued only by the end of the text.
- If we reached the root and went past it, the link of cur is the root. Otherwise let the transition by c from p lead to q. If len(q) = len(p) + 1, the strings of q are suffixes of Tc, and the link of cur is q.
- If len(q) is larger, the class q splits: its strings up to length len(p) + 1 have gained a new end, while the long ones have not. Create a copy of q with len(p) + 1, the same transitions and the same link; redirect the transitions by c from p, and further along the links while they lead to q, to the copy. The links of q and cur become the copy.
Watch how this happens on a short word. Dashed lines are suffix links; below the graph are the classes of the current automaton: strings and their ends. In «колокол» a copy appears at the fourth letter: the class {«о», «ко»} splits because «о» has occurred a second time and «ко» has not. You can enter your own word.
Why there are few states and transitions
The automaton of a string of length n ≥ 2 has at most 2n − 1 states.
We start with a single root, and each letter adds cur and possibly a copy. On the first letter there is no copy: the root has no transitions yet. On the second neither: only the root and the state of the first letter with len = 1 exist, a transition by c can lead only to it from the root, and len(root) + 1 = 1. In total at most 1 + 1 + 1 + 2(n − 2) = 2n − 1.
The automaton of a string of length n ≥ 2 has at most 3n − 3 transitions.
First note: a prefix of the longest string of a class is itself the longest string of its class. Otherwise some longer yp has the same ends as the prefix p; then every occurrence of p is preceded by y, and the string y·longest(v) would have the same ends as longest(v) while being longer.
Mark, for every state other than the root, one incoming transition: the one by the last letter of its longest string. The marked transitions form a tree, and the path along it from the root to v reads longest(v); there are at most 2n − 2 of them. Take an unmarked transition a → b by letter c. The string longest(a)·c can be extended to the right up to the end of the text, giving a suffix of the text. The path of this suffix from the root goes along marked transitions to a and then along our transition: it is the first unmarked transition on the path. So different unmarked transitions give different suffixes. The whole text is not among them: its path is the path to last along marked transitions. There are n − 1 non-empty suffixes other than the text itself, and in all there are at most 2n − 2 + n − 1 transitions.
The exact bounds are slightly lower: 3n − 4 transitions for n ≥ 3. Both are attained: 2n − 1 states by a string of the form abb…b, 3n − 4 transitions by abb…bc. Onegin, at 138,918 characters, has 201,422 states and 306,788 transitions: 1.45n and 2.21n.
Construction over the whole string takes O(n) steps if a transition by a letter is found and added in O(1).
The first loop adds a transition at each step, and so does copying; transitions never disappear, and there are fewer than 3n of them. That leaves the redirection loop. Let d(v) be the depth of v in the link tree.
If there is a transition a → b by c, then d(b) ≤ d(a) + 1. Take a string x from a: the chain of links from b is the classes of the non-empty suffixes of xc (the longer suffixes of the strings of b lie in b itself). These are strings yc, where y is a suffix of x, including the empty one. If y₁ and y₂ are in one class, then so are y₁c and y₂c: their ends are the ends of y followed by c. There are at most d(a) + 1 classes among the y.
Let the first loop at a step pass k₁ links from last to p, and the second another k₂, to p′. If the link of cur is q, then d(cur) = d(q) + 1 ≤ d(p) + 2 = d(last) − k₁ + 2. If it is a copy, then the copy’s link is the old link of q, and a transition from p′ leads into it: the string of this link of length len(link q) is zc, where z is a suffix of the strings of p; the states of the chain whose strings are longer than z lead by c to q, and the first one where z lies is p′. Then d(cur) = d(link q) + 2 ≤ d(p′) + 3 = d(last) − k₁ − k₂ + 3. The depth of the new last grows per step by at most 3 − k₁ − k₂ and is never negative, so the sum of all k₁ + k₂ over n steps is at most 3n.
The collage
The collage in the scene is one pass of the phrase over the automaton: follow transitions while you can, and that is the longest piece the poem contains; cut and start again from the root. The length of each piece is chosen greedily, and this loses nothing.
If each time you take the longest piece present in the text, you get no more pieces than in any other collage of the same phrase.
Let the greedy collage cut the phrase at positions g₁ < g₂ < …, and another at o₁ < o₂ < …. We prove that oi ≤ gi. For i = 0 both cuts are the start of the phrase. Let oi ≤ gi. If oi+1 ≤ gi, all is clear. Otherwise the piece from oi to oi+1 is in the text, and with it its tail from gi: part of a substring is also a substring. The greedy piece from gi is the longest possible, so gi+1 ≥ oi+1. Since the greedy cuts never fall behind, the greedy collage reaches the end of the phrase no later.
The same pass, if instead of starting again from the root it falls back along the suffix link on a failure, gives for each position of a second text the length of the longest piece that ends there and occurs in the first. The maximum of these lengths is the longest common substring of the two texts, in O(n + m).
Code
A state is an index into parallel lists: length, link, transition dictionary, end of first occurrence and a “copy” mark. The online step is the function add, exactly as in the list above. The numbers of occurrences are counted bottom-up over the link tree: each state that is not a copy is one end, and states are visited from long to short. The collage gives for each piece the place of its first occurrence (chapter and stanza) and how many times the piece occurs in the poem.
What it costs
| Structure | Size | Construction | Letter by letter |
|---|---|---|---|
| Trie of all suffixes | O(n²) nodes, 9.6 billion for Onegin | O(n²) | yes |
| Suffix tree | fewer than 2n nodes, edges are stretches of the text | O(n), Ukkonen’s algorithm | yes |
| Suffix array and LCP | n numbers plus another n | O(n log n) or O(n) | no |
| Suffix automaton | fewer than 2n states and 3n transitions | O(n) | yes |
The array is more compact: two numbers per character. But the automaton grows with the text and answers “is there such a continuation” in one step, without knowing the length of the piece in advance. A naive collage extends a piece letter by letter and searches for it in the text each time; substring search is built into the language in C and is fast, but it goes through the whole text on every failure. Below, the first 3000 characters of Onegin are cut out of pieces of the beginning of War and Peace of length n: the automaton grows online, with a measurement after each doubling.
Walking the automaton does not depend on the length of the text: about 2 ms in Python and tenths of a millisecond in Go at any n. Search grows linearly, and at 131 thousand characters it is 70 times slower in Python and almost two hundred times slower in Go.
Where it is easy to go wrong
- No copy. If in step 4 you simply make q the link of cur, the automaton starts accepting too much. The shortest example on two letters is “abba”: such an automaton accepts “aba”, which is not in the word.
- A shared dictionary in the copy. The copy needs its own instance of the transitions. In Python
nxt.append(nxt[q])instead ofdict(nxt[q])leaves one dictionary for two, and redirection spoils both: «колокол» starts accepting «кок» and «кокол». - The end of the first occurrence in a copy is the same as in q, not in cur: the copy is older, its strings occurred earlier.
- Counting occurrences by recursion. The link tree of the string “aaa…a” is a chain of length n. It is better traversed in decreasing order of len: each link has a smaller len.
- Memory. A dictionary per state is hundreds of bytes. For Onegin that is fine; for a text of hundreds of megabytes the transitions go into shared arrays, as in the scene, or you switch to a suffix array.
Where it works
Right-to-left pattern search: the Backward DAWG Matching algorithm reads a window of the text from the end over the automaton of the reversed pattern and, as soon as the piece of the window stops being a substring of the pattern, shifts the window right past it; its bit-parallel version, BNDM, was proposed by Gonzalo Navarro and Mathieu Raffinot in 1998. The longest common substring of two texts and the lengths of matches at each position: a pass, as in the collage. Counts over a growing text: how many distinct substrings after each letter, which piece repeats, for online splitting in compression. In olympiads the automaton is a universal substring index: the number of occurrences, the k-th substring in alphabetical order, the shortest string absent from the text.
History
Anselm Blumer, Janet Blumer, Andrzej Ehrenfeucht, David Haussler and Ross McConnell described this structure in 1983 and called it the directed acyclic word graph, DAWG. They also built it online in linear time and proved the bounds of 2n − 1 states and 3n − 4 transitions. A detailed paper, together with Mu-Tian Chen and Joel Seiferas, came out in 1985 under the title “The smallest automaton recognizing the subwords of a text”. Chen and Seiferas noticed that Peter Weiner’s 1973 suffix tree construction builds the automaton of the reversed string along the way. In 1987 the Blumers and co-authors compressed the automaton the same way a suffix tree is compressed, which gave the compact word graph, CDAWG.
Problems
The collage: for each phrase, the smallest number of pieces of the text. And the echo: for each letter, the length of the longest piece that ends at it and has occurred before; in the automaton that is the length behind the suffix link after each step.
A collage EchoesData: Eugene Onegin: Wikisource, after the 1977 collected works, modern spelling; public domain