(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 Black.
Entry modified 17 December 2004.
HTML page formatted Wed Mar 13 12:42:45 2019.
Cite this as:
Paul E. Black, "compact DAWG", in
Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 17 December 2004. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/compactDAWG.html