Directed acyclic word graph
 | It has been suggested that this article be merged into Suffix automaton. (Discuss) Proposed since October 2015. |
In computer science, a directed acyclic word graph (DAWG) is a data structure that represents the set of all substrings of a string. As its name implies, a DAWG takes the form of a directed acyclic graph; it can also be viewed as a deterministic finite automaton, and is similar in structure to suffix trees. DAWG have applications in approximate string matching.[1]
See also
References
- ^ Navarro, Gonzalo (2001). "A guided tour to approximate string matching" (PDF). ACM Computing Surveys. 33 (1): 31–88. doi:10.1145/375360.375365.
- 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 computing article is a stub. You can help Wikipedia by expanding it. |