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 2Q − 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]
See also
References
- 1 2 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., Developments in language theory. Proceedings, 8th international conference (DLT 2004), Auckland, New Zealand, December 2004, Lecture Notes in Computer Science, 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, 6842, Springer-Verlag, pp. 503–518, doi:10.1007/978-3-642-22685-4_44, ISBN 978-3-642-22684-7
This article is issued from Wikipedia - version of the 2/21/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.