directed acyclic word graph

(data structure)

Definition: (1) A directed acyclic graph representing the suffixes of a given string in which each edge is labeled with a character. The characters along a path from the root to a node are the substring which the node represents. (2) A finite state machine that recognizes a set of words.

Also known as DAWG.

Note: A variant, the compact DAWG, labels the edges with strings, not just single characters. In the compact DAWG, any node which is an only child is merged with its parent and the edge labels are concatenated. Another variant is the morphic DAWG, where some substrings are coded with new characters, like a simplified Huffman coding.

Author: PEB

Implementation

JohnPaul Adamovsky's Directed Acyclic Word Graph or DAWG page with introduction, explanation, C implementation, and notes on optimization.

More information

(1) Andrew W. Appel and Guy J. Jacobson, The World's Fastest Scrabble Program, CACM, 31(5):572-578, May 1988. Good description and comparison with a trie.

M. Crochemore and R. Verin, Direct Construction of Compact Directed Acyclic Word Graphs, 8th Annual Symposium, CPM 97, Aarhus, Denmark, 116-129, 1997.

(2) J. Aoe, K. Morimoto, M. Shishibori and K-H. Park, A Trie Compaction Algorithm for a Large Set of Keys, IEEE Trans. Knowledge and Data Engineering, 8(3):476-491, 1996.

D. Perrin, Finite Automata, in: J. van Leeuwen, ed., Handbook of Theoretical Computer Science, Elsevier, Amsterdam, Vol. A, 3-57, 1990.

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 30 December 2011.
HTML page formatted Mon Feb 2 13:10:39 2015.

Cite this as:
Paul E. Black, "directed acyclic word graph", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 30 December 2011. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/directedAcyclicWordGraph.html