Suffix tree


In computer science, a suffix 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 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 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.

Definition

The suffix tree for the string of length is defined as a tree such that:
Since such a tree does not exist for all strings, is padded with a terminal symbol not seen in the string. 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 n − 1 such nodes, and n + + 1 = 2n nodes in total.
Suffix links are a key feature for older linear-time construction algorithms, although most newer algorithms, which are based on Farach's algorithm, dispense with suffix links. 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, it has a suffix link to the internal node representing. See for example the suffix link from the node for ANA to the node for NA in the figure above. Suffix links are also used in some algorithms running on the tree.
A generalized suffix tree is a suffix tree made for a set of strings instead of a single string. It represents all suffixes from this set of strings. Each string must be terminated by a different termination symbol.

History

The concept was first introduced by.
Rather than the suffix S, Weiner stored in his trie the prefix identifier for each position, that is, the shortest string starting at i and occurring only once in S. His Algorithm D takes an uncompressed trie for S and extends it into a trie for S. This way, starting from the trivial trie for S, a trie for S can be built by n-1 successive calls to Algorithm D; however, the overall run time is O. Weiner's Algorithm B maintains several auxiliary data structures, to achieve an over all run time linear in the size of the constructed trie. The latter can still be O nodes, e.g. for S = anbnanbn$. Weiner's Algorithm C finally uses compressed tries to achieve linear overall storage size and run time.
Donald Knuth subsequently characterized the latter as "Algorithm of the Year 1973".
The text book reproduced Weiner's results in a simplified and more elegant form, introducing the term position tree.
was the first to build a trie of all suffixes of S. Although the suffix starting at i is usually longer than the prefix identifier, their path representations in a compressed trie do not differ in size. On the other hand, McCreight could dispense with most of Weiner's auxiliary data structures; only suffix links remained.
further simplified the construction. He provided the first online-construction of suffix trees, now known as Ukkonen's algorithm, with running time that matched the then fastest algorithms.
These algorithms are all linear-time for a constant-size alphabet, and have worst-case running time of in general.
gave the first suffix tree construction algorithm that is optimal for all alphabets. In particular, this is the first linear-time algorithm
for strings drawn from an alphabet of integers in a polynomial range. Farach's algorithm has become the basis for new algorithms for constructing both suffix trees and suffix arrays, for example, in external memory, compressed, succinct, etc.

Functionality

A suffix tree for a string of length can be built in time, if the letters come from an alphabet of integers in a polynomial range.
For larger alphabets, the running time is dominated by first sorting the letters to bring them into a range of size ; in general, this takes time.
The costs below are given under the assumption that the alphabet is constant.
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:
The suffix tree can be prepared for constant time lowest common ancestor retrieval between nodes in time. One can then also:
Suffix trees can be used to solve a large number of string problems that occur in text-editing, free-text search, computational biology and other application areas. Primary applications include:
Suffix trees are often used in bioinformatics applications, searching for patterns in DNA or protein sequences. The ability to search efficiently with mismatches might be considered their greatest strength. Suffix trees are also used in data compression; they can be used to find repeated data, and can be used for the sorting stage of the Burrows–Wheeler transform. Variants of the LZW compression schemes use suffix trees. A suffix tree is also used in suffix tree clustering, a data clustering algorithm used in some search engines.

Implementation

If each node and edge can be represented in space, the entire tree can be represented in space. The total length of all the strings on all of the edges in the tree is, but each edge can be stored as the position and length of a substring of, giving a total space usage of computer words. The worst-case space usage of a suffix tree is seen with a fibonacci word, 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 lists called sibling lists. Each node has a pointer to its first child, and to the next node in the child list it is a part of. Other implementations with efficient running time properties use hash maps, sorted or unsorted arrays, or balanced search trees. We are interested in:
Let be the size of the alphabet. Then you have the following costs:
The insertion cost is amortised, and that the costs for hashing are given for perfect hashing.
The large amount of information in each edge and node makes the suffix tree very expensive, consuming about 10 to 20 times the memory size of the source text in good implementations. The suffix array reduces this requirement to a factor of 8 This factor depends on the properties and may reach 2 with usage of 4-byte wide characters on 32-bit systems. Researchers have continued to find smaller indexing structures.

Parallel construction

Various parallel algorithms to speed up suffix tree construction have been proposed.
Recently, a practical parallel algorithm for suffix tree construction with work and span has been developed. The algorithm achieves good parallel scalability on shared-memory multicore machines and can index the human genome – approximately 3GB – in under 3 minutes using a 40-core machine.

External construction

Though linear, the memory usage of a suffix tree is significantly higher
than the actual size of the sequence collection. For a large text,
construction may require external memory approaches.
There are theoretical results for constructing suffix trees in external
memory.
The algorithm by
is theoretically optimal, with an I/O complexity equal to that of sorting.
However the overall intricacy of this algorithm has prevented, so far, its
practical implementation.
On the other hand, there have been practical works for constructing
disk-based suffix trees
which scale to GB/hours.
The state of the art methods are TDD,
TRELLIS,
DiGeST,
and
B2ST.
TDD and TRELLIS scale up to the entire human genome resulting in a disk-based suffix tree of a size in the tens of gigabytes. However, these methods cannot handle efficiently collections of sequences exceeding 3GB. DiGeST performs significantly better and is able to handle collections of sequences in the order of 6GB in about 6 hours.
All these methods can efficiently build suffix trees for the case when the
tree does not fit in main memory,
but the input does.
The most recent method, B2ST, scales to handle
inputs that do not fit in main memory. ERA is a recent parallel suffix tree construction method that is significantly faster. ERA can index the entire human genome in 19 minutes on an 8-core desktop computer with 16GB RAM. On a simple Linux cluster with 16 nodes, ERA can index the entire human genome in less than 9 minutes.