Suffix Tree Structure
A Suffix Tree Structure is a tree data structure that contains all the suffixes of the given token string as their keys and positions in the text as their values.
- AKA: PAT Tree.
- Context:
- It can, for string [math]\displaystyle{ S }[/math], have edges labeled with strings, such that each suffix of [math]\displaystyle{ S }[/math] corresponds to exactly one path from the tree's root to a leaf. It is thus a radix tree (a Patricia tree) for the suffixes of [math]\displaystyle{ S }[/math].
- Example(s):
- The expanded suffix tree of the string x = abcabcaba.
.
- The expanded suffix tree of the string x = abcabcaba.
- See: Longest Common Substring Problem, Suffix Tree Clustering Algorithm, Trie, Compressed Tree, Suffix (Computer Science), Substring, Regular Expression.
References
2016
- (Wikipedia, 2016) ⇒ http://wikipedia.org/wiki/suffix_tree Retrieved:2016-3-28.
- In computer science, a suffix tree (also called PAT tree or, in an earlier form, position tree) is a compressed trie containing all the suffixes of the given text as their keys and positions in the text as their values. Suffix trees allow particularly fast implementations of many important string operations.
The construction of such a tree for the string [math]\displaystyle{ S }[/math] takes time and space linear in the length of [math]\displaystyle{ S }[/math] . Once constructed, several operations can be performed quickly, for instance locating a substring in [math]\displaystyle{ S }[/math] , locating a substring if a certain number of mistakes are allowed, locating matches for a regular expression pattern etc. Suffix trees also provide one of the first linear-time solutions for the longest common substring problem. These speedups come at a cost: storing a string's suffix tree typically requires significantly more space than storing the string itself.
- In computer science, a suffix tree (also called PAT tree or, in an earlier form, position tree) is a compressed trie containing all the suffixes of the given text as their keys and positions in the text as their values. Suffix trees allow particularly fast implementations of many important string operations.
- (Apostolico et al., 2016) ⇒ Alberto Apostolico, Maxime Crochemore, Martin Farach-Colton, Zvi Galil, and S. Muthukrishnan. (2016). “40 Years of Suffix Trees.” In: Communications of the ACM Journal, 59(4). doi:10.1145/2810036
- QUOTE: Tracing the first four decades in the life of suffix trees, their many incarnations, and their applications.
1976
- (McCreight, 1976) ⇒ Edward M. McCreight. (1976). “A Space-economical Suffix Tree Construction Algorithm." Journal of the ACM (JACM) 23, no. 2
- ABSTRACT: A new algorithm is presented for constructing auxiliary digital search trees to aid in exact-match substring searching. This algorithm has the same asymptotic running time bound as previously published algorithms, but is more economical in space. Some implementation considerations are discussed, and new work on the modification of these search trees in response to incremental changes in the strings they index (the update problem) is presented.
1973
- (Weiner, 1973) ⇒ P. Weiner (1973). “Linear pattern matching algorithm.” In: Proceedings of the 14th Annual IEEE Symposium on Switching and Automata Theory. doi:10.1109/SWAT.1973.13.