Suffix automaton

Non-deterministic suffix automaton for the word "suffix". Epsilon transitions are shown grey.

In computer science, a suffix automaton or directed acyclic word graph is a finite automaton that recognizes the set of suffixes of a given string. It can be thought of as a compressed form of the suffix tree, a data structure that efficiently represents the suffixes of the string. For example, a suffix automaton for the string "suffix" can be queried for other strings; it will report "true" for any of the strings "suffix", "uffix", "ffix", "fix", "ix" and "x", and "false" for any other string.^[1]

The suffix automaton of a set of strings $U$ has at most $2 Q - 2$ states, where $Q$ is the number of nodes of a prefix-tree representing the strings in $U$ .^[2]

Suffix automata have applications in approximate string matching.^[1]

References

^ ^a ^b Navarro, Gonzalo (2001), "A guided tour to approximate string matching" (PDF), ACM Computing Surveys, 33 (1): 31–88, doi:10.1145/375360.375365
^ Mohri, Mehryar; Moreno, Pedro; Weinstein, Eugene (September 2009), "General suffix automaton construction algorithm and space bounds", Theoretical Computer Science, 410 (37): 3553–3562, doi:10.1016/j.tcs.2009.03.034

Additional reading

Inenaga, S.; Hoshino, H.; Shinohara, A.; Takeda, M.; Arikawa, S. (2001), "On-line construction of symmetric compact directed acyclic word graphs", Proc. 8th Int. Symp. String Processing and Information Retrieval, 2001. SPIRE 2001, pp. 96–110, doi:10.1109/SPIRE.2001.989743, ISBN 0-7695-1192-9.
Crochemore, Maxime; Vérin, Renaud (1997), "Direct construction of compact directed acyclic word graphs", Combinatorial Pattern Matching, Lecture Notes in Computer Science, Springer-Verlag, pp. 116–129, doi:10.1007/3-540-63220-4_55.
Epifanio, Chiara; Mignosi, Filippo; Shallit, Jeffrey; Venturini, Ilaria (2004), "Sturmian graphs and a conjecture of Moser", in Calude, Cristian S.; Calude, Elena; Dineen, Michael J. (eds.), Developments in language theory. Proceedings, 8th international conference (DLT 2004), Auckland, New Zealand, December 2004, Lecture Notes in Computer Science, vol. 3340, Springer-Verlag, pp. 175–187, ISBN 3-540-24014-4, Zbl 1117.68454
Do, H.H.; Sung, W.K. (2011), "Compressed Directed Acyclic Word Graph with Application in Local Alignment", Computing and Combinatorics, Lecture Notes in Computer Science, vol. 6842, Springer-Verlag, pp. 503–518, doi:10.1007/978-3-642-22685-4_44, ISBN 978-3-642-22684-7

This computer science article is a stub. You can help Wikipedia by expanding it.

[guided-1] Navarro, Gonzalo (2001), "A guided tour to approximate string matching" (PDF), ACM Computing Surveys, 33 (1): 31–88, doi:10.1145/375360.375365

[2] Mohri, Mehryar; Moreno, Pedro; Weinstein, Eugene (September 2009), "General suffix automaton construction algorithm and space bounds", Theoretical Computer Science, 410 (37): 3553–3562, doi:10.1016/j.tcs.2009.03.034

[1]

[2]

See also

References

Additional reading