Definition: A directed acyclic word graph (DAWG) representing the suffixes of a given string in which each edge is labeled with the longest possible string. The strings along a path from the root to a node are the substring which the node represents.
See also directed acyclic word graph, Patricia tree.
Note: This is a variant of a directed acyclic word graph, or DAWG, in which a node with one child is merged with its parent and the edge labels are concatenated. A Patricia tree merges single-child nodes also, but does not combine common subtrees.
Andrew W. Appel and Guy J. Jacobson, The World's Fastest Scrabble Program, CACM, 31(5):572-578, May 1988. Good description of the basic DAWG.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 17 December 2004.
HTML page formatted Fri Mar 25 16:20:34 2011.
Cite this as:
Paul E. Black, "compact DAWG", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2004. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/compactDAWG.html