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 S {\displaystyle S} 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 S = s 1 s 2 … s n {\displaystyle S=s_{1}s_{2}\dots s_{n}} . 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 S {\displaystyle S} having length at least two characters has at most 2 | S | − 1 {\textstyle 2|S|-1} states and at most 3 | S | − 4 {\textstyle 3|S|-4} 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 S {\displaystyle S} of length greater than 1 {\displaystyle 1} has at most 2 | S | − 1 {\displaystyle 2|S|-1} states and at most 3 | S | − 4 {\displaystyle 3|S|-4} 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 S {\displaystyle S} constructs a suffix automaton of the reversed string S R {\textstyle S^{R}} 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 Σ {\displaystyle \Sigma } that is used to construct words. Its elements are called "characters"; "Word" is a finite sequence of characters ω = ω 1 ω 2 … ω n {\displaystyle \omega =\omega _{1}\omega _{2}\dots \omega _{n}} . "Length" of the word ω {\displaystyle \omega } is denoted as | ω | = n {\displaystyle |\omega |=n} ; "Formal language" is a set of words over given alphabet; "Language of all words" is denoted as Σ ∗ {\displaystyle \Sigma ^{}} (where the "" character stands for Kleene star), "empty word" (the word of zero length) is denoted by the character ε {\displaystyle \varepsilon } ; "Concatenation of words" α = α 1 α 2 … α n {\displaystyle \alpha =\alpha _{1}\alpha _{2}\dots \alpha _{n}} and β = β 1 β 2 … β m {\displaystyle \beta =\beta _{1}\beta _{2}\dots \beta _{m}} is denoted as α ⋅ β {\displaystyle \alpha \cdot \beta } or α β {\displaystyle \alpha \beta } and corresponds to the word obtained by writing β {\displaystyle \beta } to the right of α {\displaystyle \alpha } , that is, α β = α 1 α 2 … α n β 1 β 2 … β m {\displaystyle \alpha \beta =\alpha _{1}\alpha _{2}\dots \alpha _{n}\beta _{1}\beta _{2}\dots \beta _{m}} ; "Concatenation of languages" A {\displaystyle A} and B {\displaystyle B} is denoted as A ⋅ B {\displaystyle A\cdot B} or A B {\displaystyle AB} and corresponds to the set of pairwise concatenations A B = { α β : α ∈ A , β ∈ B } {\displaystyle AB=\{\alpha \beta :\alpha \in A,\beta \in B\}} ; If the word ω ∈ Σ ∗ {\displaystyle \omega \in \Sigma ^{}} may be represented as ω = α γ β {\displaystyle \omega =\alpha \gamma \beta } , where α , β , γ ∈ Σ ∗ {\displaystyle \alpha ,\beta ,\gamma \in \Sigma ^{}} , then words α {\displaystyle \alpha } , β {\displaystyle \beta } and γ {\displaystyle \gamma } are called "prefix", "suffix" and "subword" (substring) of the word ω {\displaystyle \omega } correspondingly; If T = T 1 … T n {\displaystyle T=T_{1}\dots T_{n}} and T l T l + 1 … T r = S {\displaystyle T_{l}T_{l+1}\dots T_{r}=S} (with 1 ≤ l ≤ r ≤ n {\displaystyle 1\leq l\leq r\leq n} ) then S {\displaystyle S} is said to "occur" in T {\displaystyle T} as a subword. Here l {\displaystyle l} and r {\displaystyle r} are called left and right positions of occurrence of S {\displaystyle S} in T {\displaystyle T} correspondingly. == Automaton structure == Formally, deterministic finite automaton is determined by 5-tuple A = ( Σ , Q , q 0 , F , δ ) {\displaystyle {\mathcal {A}}=(\Sigma ,Q,q_{0},F,\delta )} , where: Σ {\displaystyle \Sigma } is an "alphabet" that is used to construct words, Q {\displaystyle Q} is a set of automaton "states", q 0 ∈ Q {\displaystyle q_{0}\in Q} is an "initial" state of automaton, F ⊂ Q {\displaystyle F\subset Q} is a set of "final" states of automaton, δ : Q × Σ ↦ Q {\displaystyle \delta :Q\times \Sigma \mapsto Q} is a partial "transition" function of automaton, such that δ ( q , σ ) {\displaystyle \delta (q,\sigma )} for q ∈ Q {\displaystyle q\in Q} and σ ∈ Σ {\displaystyle \sigma \in \Sigma } is either undefined or defines a transition from q {\displaystyle q} over character σ {\displaystyle \sigma } . Most commonly, deterministic finite automaton is represented as a directed graph ("diagram") such that: Set of graph vertices corresponds to the state of states Q {\displaystyle Q} , Graph has a specific marked vertex corresponding to initial state q 0 {\displaystyle q_{0}} , Graph has several marked vertices corresponding to the set of final states F {\displaystyle F} , Set of graph arcs corresponds to the set of transitions δ {\displaystyle \delta } , Specifically, every transition δ ( q 1 , σ ) = q 2 {\textstyle \delta (q_{1},\sigma )=q_{2}} is represented by an arc from q 1 {\displaystyle q_{1}} to q 2 {\displaystyle q_{2}} marked with the character σ {\displaystyle \sigma } . This transition also may be denoted as q 1 σ ⟶ q 2 {\textstyle q_{1}{\begin{smallmatrix}{\sigma }\\[-5pt]{\longrightarrow }\end{smallmatrix}}q_{2}} . In terms of its diagram, the automaton recognizes the word ω = ω 1 ω 2 … ω m {\displaystyle \omega =\omega _{1}\omega _{2}\dots \omega _{m}} only if there is a path from the initial vertex q 0 {\displaystyle q_{0}} to some final vertex q ∈ F {\displaystyle q\in F} such that concatenation of characters on this path forms ω {\displaystyle \omega } . 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 S {\displaystyle S} is the language of its (possibly empty) suffixes. === Automaton states === "Right context" of the word ω {\displaystyle \omega } with respect to language L {\displaystyle L} is a set [ ω ] R = { α : ω α ∈ L } {\displaystyle [\omega ]_{R}=\{\alpha :\omega \alpha \in L\}} that is a set of words α {\displaystyle \alpha } such that their concatenation with ω {\displaystyle \omega } forms a word from L {\displaystyle L} . Right contexts induce a natural equivalence relation [ α ] R = [ β ] R {\displaystyle [\alpha ]_{R}=[\beta ]_{R}} on the set of all words. If language L {\displaystyle L} 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 L {\displaystyle L} . 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 S = s 1 s 2 … s n {\displaystyle S=s_{1}s_{2}\dots s_{n}} . The right context of the word ω {\displaystyle \omeg
Read more →
