Мәтіннің барлық жұрнақтарын қамтитын ағаш құрылымы

Tree containing all suffixes of a given text

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 takes time and space linear in the length of Once constructed, several operations can be performed quickly, such as locating a substring in , locating a substring if a certain number of mistakes are allowed, and locating matches for a regular expression pattern. Suffix trees also provided 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.

The concept was first introduced by Rather than the suffix , Weiner stored in his trie the prefix identifier for each position, that is, the shortest string starting at and occurring only once in His Algorithm D takes an uncompressed trie for and extends it into a trie for This way, starting from the trivial trie for , a trie for can be built by successive calls to Algorithm D; however, the overall run time is 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 nodes, e. g. for 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" according to his student Vaughan Pratt. 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 (compressed) trie of all suffixes of Although the suffix starting at 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.

Various parallel algorithms to speed up suffix tree construction have been proposed. Recently, a practical parallel algorithm for suffix tree construction with work (sequential time) 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.