(data structure)
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.
Author: PEB
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 Fri Dec 17 12:03:09 2004.
HTML page formatted Wed Oct 26 09:47:21 2005.
Cite this as:
Paul E. Black, "compact DAWG", from
Dictionary of Algorithms and Data
Structures, Paul E. Black, ed.,
NIST.
http://www.nist.gov/dads/HTML/compactDAWG.html
