In computer science, a suffix automaton is an efficient data structure for representing the substring index of a given string which allows the storage, processing, and retrieval of compressed information about all its substrings. The suffix automaton of a string is the smallest directed acyclic graph with a dedicated initial vertex and a set of "final" vertices, such that paths from the initial vertex to final vertices represent the suffixes of the string.
In terms of automata theory, a suffix automaton is the minimal partial deterministic finite automaton that recognizes the set of suffixes of a given string . The state graph of a suffix automaton is called a directed acyclic word graph (DAWG), a term that is also sometimes used for any deterministic acyclic finite state automaton.
Suffix automata were introduced in 1983 by a group of scientists from the University of Denver and the University of Colorado Boulder. They suggested a linear time online algorithm for its construction and showed that the suffix automaton of a string having length at least two characters has at most states and at most transitions. Further works have shown a close connection between suffix automata and suffix trees, and have outlined several generalizations of suffix automata, such as compacted suffix automaton obtained by compression of nodes with a single outgoing arc.
Suffix automata provide efficient solutions to problems such as substring search and computation of the largest common substring of two and more strings.
History
The concept of suffix automaton was introduced in 1983 by a group of scientists from University of Denver and University of Colorado Boulder consisting of Anselm Blumer, Janet Blumer, Andrzej Ehrenfeucht, David Haussler and Ross McConnell, although similar concepts had earlier been studied alongside suffix trees in the works of Peter Weiner, Vaughan Pratt and Anatol Slissenko. In their initial work, Blumer et al. showed a suffix automaton built for the string of length greater than has at most states and at most transitions, and suggested a linear algorithm for automaton construction.
In 1983, Mu-Tian Chen and Joel Seiferas independently showed that Weiner's 1973 suffix-tree construction algorithm while building a suffix tree of the string constructs a suffix automaton of the reversed string as an auxiliary structure. In 1987, Blumer et al. applied the compressing technique used in suffix trees to a suffix automaton and invented the compacted suffix automaton, which is also called the compacted directed acyclic word graph (CDAWG). In 1997, Maxime Crochemore and Renaud Vérin developed a linear algorithm for direct CDAWG construction. In 2001, Shunsuke Inenaga et al. developed an algorithm for construction of CDAWG for a set of words given by a trie.
Definitions Usually when speaking about suffix automata and related concepts, some notions from formal language theory and automata theory are used, in particular:
"Alphabet" is a finite set that is used to construct words. Its elements are called "characters"; "Word" is a finite sequence of characters . "Length" of the word is denoted as ; "Formal language" is a set of words over given alphabet; "Language of all words" is denoted as (where the "*" character stands for Kleene star), "empty word" (the word of zero length) is denoted by the character ; "Concatenation of words" and is denoted as or and corresponds to the word obtained by writing to the right of , that is, ; "Concatenation of languages" and is denoted as or and corresponds to the set of pairwise concatenations ; If the word may be represented as , where , then words , and are called "prefix", "suffix" and "subword" (substring) of the word correspondingly; If and (with ) then is said to "occur" in as a subword. Here and are called left and right positions of occurrence of in correspondingly.
Automaton structure Formally, deterministic finite automaton is determined by 5-tuple , where:
is an "alphabet" that is used to construct words, is a set of automaton "states", is an "initial" state of automaton, is a set of "final" states of automaton, is a partial "transition" function of automaton, such that for and is either undefined or defines a transition from over character .
Most commonly, deterministic finite automaton is represented as a directed graph ("diagram") such that:
Set of graph vertices corresponds to the state of states , Graph has a specific marked vertex corresponding to initial state , Graph has several marked vertices corresponding to the set of final states , Set of graph arcs corresponds to the set of transitions , Specifically, every transition is represented by an arc from to marked with the character . This transition also may be denoted as .
In terms of its diagram, the automaton recognizes the word only if there is a path from the initial vertex to some final vertex such that concatenation of characters on this path forms . The set of words recognized by an automaton forms a language that is set to be recognized by the automaton. In these terms, the language recognized by a suffix automaton of is the language of its (possibly empty) suffixes.
Automaton states
"Right context" of the word with respect to language is a set that is a set of words such that their concatenation with forms a word from . Right contexts induce a natural equivalence relation on the set of all words. If language is recognized by some deterministic finite automaton, there exists unique up to isomorphism automaton that recognizes the same language and has the minimum possible number of states. Such an automaton is called a minimal automaton for the given language . Myhill–Nerode theorem allows it to define it explicitly in terms of right contexts:
In these terms, a "suffix automaton" is the minimal deterministic finite automaton recognizing the language of suffixes of the word . The right context of the word with respect to this language consists of words , such that is a suffix of . It allows to formulate the following lemma defining a bijection between the right context of the word and the set of right positions of its occurrences in :
For example, for the word and its subword , it holds and . Informally, is formed by words that follow occurrences of to the end of and is formed by right positions of those occurrences. In this example, the element corresponds with the word while the word corresponds with the element .
It implies several structure properties of suffix automaton states. Let , then:
If and have at least one common element , then and have a common element as well. It implies is a suffix of and therefore and . In aforementioned example, , so is a suffix of and thus and ; If , then , thus occurs in only as a suffix of . For example, for and it holds that and ; If and is a suffix of such that , then . In the example above and it holds for "intermediate" suffix that .
Any state of the suffix automaton recognizes some continuous chain of nested suffixes of the longest word recognized by this state.
"Left extension" of the string is the longest string that has the same right context as . Length of the longest string recognized by is denoted by . It holds:
"Suffix link" of the state is the pointer to the state that contains the largest suffix of that is not recognized by .
In this terms it can be said recognizes exactly all suffixes of that is longer than and not longer than . It also holds:
Connection with suffix trees
A "prefix tree" (or "trie") is a rooted directed tree in which arcs are marked by characters in such a way no vertex of such tree has two out-going arcs marked with the same character. Some vertices in trie are marked as final. Trie is said to recognize a set of words defined by paths from its root to final vertices. In this way prefix trees are a special kind of deterministic finite automata if you perceive its root as an initial vertex. The "suffix trie" of the word is a prefix tree recognizing a set of its suffixes. "A suffix tree" is a tree obtained from a suffix trie via the compaction procedure, during which consequent edges are merged if the degree of the vertex between them is equal to two.
By its definition, a suffix automaton can be obtained via minimization of the suffix trie. It may be shown that a compacted suffix automaton is obtained by both minimization of the suffix tree (if one assumes each string on the edge of the suffix tree is a solid character from the alphabet) and compaction of the suffix automaton. Besides this connection between the suffix tree and the suffix automaton of the same string there is as well a connection between the suffix automaton of the string and the suffix tree of the reversed string .
Similarly to right contexts one may introduce "left contexts" , "right extensions" corresponding to the longest string having same left context as and the equivalence relation . If one considers right extensions with respect to the language of "prefixes" of the string it may be obtained:
, which implies the suffix link tree of the string and the suffix tree of the string are isomorphic:
Suffix structures of words "abbcbc" and "cbcbba"
Similarly to the case of left extensions, the following lemma holds for right extensions:
Size A suffix automaton of the string of length has at most states and at most transitions. These bounds are reached on strings and correspondingly. This may be formulated in a stricter way as where and are the numbers of transitions and states in automaton correspondingly.
Maximal suffix automata
Construction Initially the automaton only consists of a single state corresponding to the empty word, then characters of the string are added one by one and the automaton is rebuilt on each step incrementally.
State updates After a new character is appended to the string, some equivalence classes are altered. Let be the right context of with respect to the language of suffixes. Then the transition from to after is appended to is defined by lemma:
After adding to the current word the right context of may change significantly only if is a suffix of . It implies equivalence relation is a refinement of . In other words, if , then . After the addition of a new character at most two equivalence classes of will be split and each of them may split in at most two new classes. First, equivalence class corresponding to empty right context is always split into two equivalence classes, one of them corresponding to itself and having as a right context. This new equivalence class contains exactly and all its suffixes that did not occur in , as the right context of such words was empty before and contains only empty word now.
Given the correspondence between states of the suffix automaton and vertices of the suffix tree, it is possible to find out the second state that may possibly split after a new character is appended. The transition from to corresponds to the transition from to in the reversed string. In terms of suffix trees it corresponds to the insertion of the new longest suffix into the suffix tree of . At most two new vertices may be formed after this insertion: one of them corresponding to , while the other one corresponds to its direct ancestor if there was a branching. Returning to suffix automata, it means the first new state recognizes and the second one (if there is a second new state) is its suffix link. It may be stated as a lemma:
It implies that if (for example, when didn't occur in at all and ), then only the equivalence class corresponding to the empty right context is split.