- Suffix tree
In
computer science , a suffix tree (also called suffix trie, PAT tree or, in an earlier form, position tree) is a data structure that presents the suffixes of a given string in a way that allows for a particularly fast implementation of many important string operations.The suffix tree for a string is a tree whose edges are labeled with strings, and such that each suffix of corresponds to exactly one path from the tree's root to a leaf. It is thus a
radix tree (more specifically, aPatricia trie ) for the suffixes of .Constructing such a tree for the string takes time and space linear in the length of . Once constructed, several operations can be performed quickly, for instance locating a
substring in , locating a substring if a certain number of mistakes are allowed, locating matches for aregular expression pattern etc. Suffix trees also provided one of the first linear-time solutions for thelongest 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.History
The concept was first introduced as a "position tree" by Weiner in 1973cite conference
author=P. Weiner
title=Linear pattern matching algorithm
booktitle=14th Annual IEEE Symposium on Switching and Automata Theory
year=1973
pages=1-11] in a paper whichDonald Knuth subsequently characterized as "Algorithm of the Year 1973". The construction was greatly simplified by McCreight in 1976cite journal
author=Edward M. McCreight
title=A Space-Economical Suffix Tree Construction Algorithm
journal=Journal of the ACM
volume=23
issue=2
year=1976
pages=262--272
url=http://doi.acm.org/10.1145/321941.321946 | doi=10.1145/321941.321946 ] , and also by Ukkonen in 1995cite journal
author=E. Ukkonen
title=On-line construction of suffix trees
journal=Algorithmica
volume=14
issue=3
year=1995
pages=249--260
url=http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf | doi=10.1007/BF01206331] cite journal
author=R. Giegerich and S. Kurtz
title=From Ukkonen to McCreight and Weiner: A Unifying View of Linear-Time Suffix Tree Construction
journal=Algorithmica
volume=19
issue=3
year=1997
pages=331--353
url=http://www.zbh.uni-hamburg.de/staff/kurtz/papers/GieKur1997.pdf | doi=10.1007/PL00009177] . Ukkonen provided the first linear-time online-construction of suffix trees, now known asUkkonen's algorithm .Definition
The suffix tree for the string of length is defined as a tree such that (cite book
last = Gusfield
first = Dan
origyear = 1997
year = 1999
title = Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology
publisher = Cambridge University Press
location = USA
id = ISBN 0-521-58519-8] page 90):
* the paths from the root to the leaves have a one-to-one relationship with the suffixes of ,
* edges spell non-empty strings,
* and all internal nodes (except perhaps the root) have at least two children.Since such a tree does not exist for all strings, is padded with a terminal symbol not seen in the string (usually denoted
$
). This ensures that no suffix is a prefix of another, and that there will be leaf nodes, one for each of the suffixes of . Since all internal non-root nodes are branching, there can be at most such nodes, and nodes in total.Suffix links are a key feature for linear-time construction of the tree. In a complete suffix tree, all internal non-root nodes have a suffix link to another internal node. If the path from the root to a node spells the string , where is a single character and is a string (possibly empty), it has a suffix link to the internal node representing . See for example the suffix link from the node for
ANA
to the node forNA
in the figure above. Suffix links are also used in some algorithms running on the tree.Functionality
A suffix tree for a string of length can be built in time, if the alphabet is constant or integer cite conference
author=Martin Farach
title=Optimal suffix tree construction with large alphabets
booktitle=Foundations of Computer Science, 38th Annual Symposium on
year=1997
pages=137--143
url=ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-48.ps.gz] . Otherwise, the construction time depends on the implementation. The costs below are given under the assumption that the alphabet is constant. If it is not, the cost depends on the implementation (see below).Assume that a suffix tree has been built for the string of length , or that a
generalised suffix tree has been built for the set of strings of total length .You can:* Search for strings:
** Check if a string of length is a substring in time ( page 92).
** Find the first occurrence of the patterns of total length as substrings in time, when the suffix tree is built usingUkkonen's algorithm .
** Find all occurrences of the patterns of total length as substrings in time ( page 123).
** Search for aregular expression "P" in time expectedsublinear in (cite journal
author=Ricardo A. Baeza-Yates and Gaston H. Gonnet
title=Fast text searching for regular expressions or automaton searching on tries
journal=Journal of the ACM
volume=43
number=6
year=1996
issn=0004-5411
pages=915--936
doi=10.1145/235809.235810
publisher=ACM Press
address=New York, NY, USA] ).
** Find for each suffix of a pattern , the length of the longest match between a prefix of and a substring in in time ( page 132). This is termed the matching statistics for .
* Find properties of the strings:
** Find the longest common substrings of the string and in time ( page 125).
** Find allmaximal pair s, maximal repeats or supermaximal repeats in time ( page 144).
** Find theLempel-Ziv decomposition in time ( page 166).
** Find the longest repeated substrings in time.
** Find the most frequently occurring substrings of a minimum length in time.
** Find the shortest strings from that do not occur in , in time, if there are such strings.
** Find the shortest substrings occurring only once in time.
** Find, for each , the shortest substrings of not occurring elsewhere in in time.The suffix tree can be prepared for constant time
lowest common ancestor retrieval between nodes in time ( chapter 8). You can then also:
* Find the longest common prefix between the suffixes and in ( page 196).
* Search for a pattern of length with at most mismatches in time, where is the number of hits ( page 200).
* Find all maximalpalindrome s in ( page 198), or time if gaps of length are allowed, or if mismatches are allowed ( page 201).
* Find alltandem repeats in , and k-mismatch tandem repeats in ( page 204).
* Find the longest substrings common to at least strings in for in time ( page 205).Uses
Suffix trees are often used in
bioinformatics applications, where they are used for searching for patterns inDNA orprotein sequences, which can be viewed as long strings of characters. The ability to search efficiently with mismatches might be the suffix tree's greatest strength. It is also used indata compression , where on the one hand it is used to find repeated data and on the other hand it can be used for the sorting stage of theBurrows-Wheeler transform . Variants of theLZW compression schemes use it (LZSS ). A suffix tree is also used insuffix tree clustering , adata clustering algorithm used in some search engines (first introduced in cite conference
author=Oren Zamir and Oren Etzioni
title=Web document clustering: a feasibility demonstration
booktitle=SIGIR '98: Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval
year=1998
pages=46--54
publisher=ACM
address=New York, NY, USA] ).Implementation
If each node and edge can be represented in space, the entire tree can be represented in space. The total length of the edges in the tree is , but each edge can be stored as the position and length of a substring of "S", giving a total space usage of computer words. The worst-case space usage of a suffix tree is seen with a
fibonacci string , giving the full nodes.An important choice when making a suffix tree implementation is the parent-child relationships between nodes. The most common is using
linked list s called sibling lists. Each node has pointer to its first child, and to the next node in the child list it is a part of.Hash map s, sorted/unsortedarray s (with array doubling), and balanced search trees may also be used, giving different running time properties. We are interested in:
* The cost of finding the child on a given character.
* The cost of inserting a child.
* The cost of enlisting all children of a node (divided by the number of children in the table below).Let be the size of the alphabet. Then you have the following costs:
Note that the insertion cost is amortised, and that the costs for hashing are given perfect hashing.
The large amount of information in each edge and node makes the suffix tree very expensive, consuming about ten to twenty times the memory size of the source text in good implementations. The
suffix array reduces this requirement to a factor of four, and researchers have continued to find smaller indexing structures.ee also
*
Suffix array References
External links
* [http://www.cise.ufl.edu/~sahni/dsaaj/enrich/c16/suffix.htm Suffix Trees] by Dr. Sartaj Sahni (CISE Department Chair at University of Florida)
* [http://www.allisons.org/ll/AlgDS/Tree/Suffix/ Suffix Trees] by Lloyd Allison
* [http://datacompression.info/SuffixTrees.shtml Suffix Trees] links collection by Mark Nelson
* [http://www.nist.gov/dads/HTML/suffixtree.html NIST's Dictionary of Algorithms and Data Structures: Suffix Tree]
* [http://www.cl.cam.ac.uk/~cpk25/libstree/ libstree] , a generic suffix tree library written in C
* [http://search.cpan.org/dist/Tree-Suffix/ Tree::Suffix] , a Perl binding to libstree
* [http://www.cs.ucdavis.edu/~gusfield/strmat.html Strmat] a faster generic suffix tree library written in C (uses arrays instead of linked lists)
* [http://hkn.eecs.berkeley.edu/~dyoo/python/suffix_trees/ SuffixTree] a Python binding to Strmat
* [http://www.balkenhol.net/papers/t1043.pdf.gz Universal Data Compression Based on the Burrows-Wheeler Transformation: Theory and Practice] , application of suffix trees in the BWT
* [http://www.cs.helsinki.fi/group/suds/ Theory and Practice of Succinct Data Structures] , C++ implementation of a compressed suffix tree]
* [http://video.google.com/videoplay?docid=3849716474680225865 Google video on constructing a suffix tree]
Wikimedia Foundation. 2010.