Definition: A compact representation of a trie corresponding to the suffixes of a given string where all nodes with one child are merged with their parents.
Generalization (I am a kind of ...)
Patricia tree, trie.
Specialization (... is a kind of me.)
multi suffix tree.
See also suffix array, directed acyclic word graph.
Note: A suffix tree is a Patricia tree corresponding to the suffixes of a given string. A directed acyclic word graph (DAWG) is a more compact form.
The newer suffix array has replaced the suffix tree as the data structure of choice in many applications.
Edward M. McCreight, A space-economical suffix tree construction algorithm, Journal of the ACM, 23:262-272, 1976.
Esko Ukkonen, On-line construction of suffix trees, Algorithmica, 14(3):249-260, September 1995.
A linear time, forward construction algorithm. See Wikipedia entry for links to PDF of Ukkonen's paper.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 11 October 2011.
HTML page formatted Tue Dec 6 16:16:33 2011.
Cite this as:
Stefan Edelkamp, "suffix tree", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 11 October 2011. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/suffixtree.html