File SuffixTree.h

↰ Parent directory (ADS/string)

The suffix tree of a text T of n symbols, beyond the book: the compact trie [see RadixTree in File Trie.h] of the n + 1 suffixes of T$, where $ is a terminator smaller than every symbol, so that no suffix is a prefix of another and each one ends in a leaf of its own.

Definition (ADS/string/SuffixTree.h)

Detailed Description

Every internal node but the root has at least two children, hence there are at most n internal nodes; the label of an edge is a substring of T, kept as the place of one occurrence and the string depths of its two ends, O( 1 ) space, and the tree takes O( n ) space (Fact 10.3), though some 10 to 20 n bytes in practice against the n integers of a suffix array [see File SuffixArray.h]. The children of a node are kept by their first symbol in a balanced search tree (std::map), so that branching costs :math:` O( log sigma ) ` for an alphabet of :math:` sigma ` symbols, and they are visited in the lexicographic order. The node u spells s[ u ], the string on the path from the root, and it is an internal node exactly when s[ u ] occurs at least twice followed by distinct symbols (Property 10.6); the lowest common ancestor of the leaves i and j spells the longest common prefix of the suffixes i and j (Property 10.9).

The constructions, each giving the same tree:

  • Build::naive inserts the suffixes from the longest one, each by a walk down from the root that compares all its symbols, :math:` Theta( n^2 ) ` time for the text :math:` a^{n-1} `;

  • Build::mcCreight is the algorithm of McCreight: the suffixes are inserted from the longest one too, but the walk of suffix i starts from the suffix link of the node of head_{i-1}, the longest prefix of the suffix i - 1 that occurs earlier, which spells head_{i-1} without its first symbol; when that link is not set yet, it is found from the link of the parent by a rescan that compares only the first symbol of each edge, whose total is O( n ) since the depth of the tree drops by at most 2 per link. :math:` O( n log sigma ) ` time (Theorem 10.10);

  • Build::suffixArray builds the suffix array by SA-IS and the LCP array by Kasai et al., then inserts the leaves in the order of SA, each one climbing from the previous leaf, along the rightmost path, to the deepest node of string depth at most LCP[ i - 1 ], and splitting the edge below it when its depth is larger; each edge climbed is left to the left for good, hence O( n ) steps (Fact 10.6).

Weiner gave the first linear construction (1973), inserting the suffixes from the shortest one; Ukkonen’s algorithm is the online form of McCreight’s, which reads T from left to right and keeps the tree of each prefix; Farach reached O( n ) on integer alphabets by merging the trees of the odd and of the even suffixes, the idea that the Skew algorithm turned into the 2/3 : 1/3 split of the suffix arrays. Since the linear suffix arrays (SA-IS, divsufsort) are smaller and faster, the construction through SA and LCP is the usual one; McCreight’s pays where the average lcp is small.

locus() finds the extended locus of a pattern P of p symbols by a walk down from the root, :math:` O( p log sigma ) ` time, and locate() the occ occurrences below it in O( occ ), since that subtree has occ leaves and fewer internal nodes (Fact 10.4). lca() answers the lowest common ancestor of two nodes in O( 1 ) time by the Euler tour of the tree and the range minima of its depths [see PlusMinusOneRangeMinimum in File RangeMinimum.h], hence lce() the longest common extension of two suffixes (Theorem 10.12). toSuffixArray() reads SA and LCP back by a visit in order, the leaves giving SA and the internal node met between two leaves their lcp (Fact 10.5).

The contracts [see File Contract.h]: the invariant of the tree (n + 1 leaves, at least two children at each internal node but the root, the first symbol of each edge equal to its key, the string depths increasing downward) after each construction; the places and the nodes of the queries exist. The functions are defined in SuffixTree.tpp.

  1. Ferragina, Pearls of Algorithm Engineering, Cambridge University Press, 2023, chapter 10

    1. McCreight, A space-economical suffix tree construction algorithm, Journal of the ACM 23(2), 262-272, 1976, doi:10.1145/321941.321946

  1. Weiner, Linear pattern matching algorithms, Proceedings of the 14th Annual Symposium on Switching and Automata Theory (SWAT), 1-11, 1973, doi:10.1109/SWAT.1973.13

  1. Ukkonen, On-line construction of suffix trees, Algorithmica 14(3), 249-260, 1995, doi:10.1007/BF01206331

  1. Farach, Optimal suffix tree construction with large alphabets, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS), 137-143, 1997, doi:10.1109/SFCS.1997.646102

  1. Gusfield, Algorithms on Strings, Trees and Sequences, Cambridge University Press, 1997, doi:10.1017/CBO9780511574931

  1. Nong, S. Zhang, W. H. Chan, Two efficient algorithms for linear time suffix array construction, IEEE Transactions on Computers 60(10), 1471-1484, 2011, doi:10.1109/TC.2010.188

  1. Kasai, G. Lee, H. Arimura, S. Arikawa, K. Park, Linear-time longest-common-prefix computation in suffix arrays and its applications, Proceedings of the 12th Symposium on Combinatorial Pattern Matching (CPM), LNCS 2089, 181-192, 2001, doi:10.1007/3-540-48194-X_17

    1. Bender, M. Farach-Colton, The LCA problem revisited, Proceedings of the 4th Latin American Symposium on Theoretical Informatics (LATIN), LNCS 1776, 88-94, 2000, doi:10.1007/10719839_9

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes