Directed acyclic word graph

From Wikipedia, the free encyclopedia
Jump to: navigation, search
"DAWG" redirects here. For other uses of this letter group, see Dawg.
For the US Department of Defense review panel, see Deputy's Advisory Working Group.
For the dictionary data structure that is sometimes called a DAWG, see Deterministic acyclic finite state automaton.

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[edit]


  1. ^ Navarro, Gonzalo (2001). "A guided tour to approximate string matching". ACM Computing Surveys 33 (1): 31–88. doi:10.1145/375360.375365.  edit