File SuffixArray.h

↰ Parent directory (ADS/string)

The suffix array of a text T of n symbols, beyond the book: SA[ r ] is the starting place of the r-th smallest suffix of T in the lexicographic order, a suffix that is a prefix of another being the smaller.

Definition (ADS/string/SuffixArray.h)

Detailed Description

The occurrences of a pattern P of p symbols are the suffixes prefixed by P, which lie in a contiguous range of SA, found by binary search; the array takes n integers besides T, against the 10 to 20 n bytes of a suffix tree [see File SuffixTree.h]. The positions count from 0, and no terminator is stored: the chapter writes T with a final $, whose suffix would be the first of SA.

The constructions, each giving the same array:

  • suffixArraySorting(), Algorithm 10.3: the n suffixes sorted by a sort of comparisons (std::sort), each comparison as long as the common prefix, :math:` O( n log n ) ` comparisons and :math:` O( n^2 log n ) ` time in the worst case (a text of one repeated symbol), near :math:` O( n log^2 n ) ` on random texts;

  • suffixArrayDoubling(), the prefix doubling of Manber and Myers: after round k each suffix has the rank of its prefix of :math:` 2^k ` symbols, and the pair of the ranks of the suffixes at i and :math:` i + 2^k ` is the rank of the prefix of :math:` 2^{k+1} ` symbols; the pairs are sorted by the LSD radix sort of File RadixSort.h, :math:` O( n log n ) ` time in all, or :math:` O( n log L ) ` for L the longest repeated prefix;

  • suffixArrayLarssonSadakane(), the doubling of Larsson and Sadakane (qsufsort): the same ranks, but a round sorts only the groups of suffixes that are still tied, each by the rank of the suffix h places ahead, and refines the ranks at once, so that the groups already sorted are skipped by a length stored in their first place. Their bound is :math:` O( n log n ) ` with a ternary-split quicksort; with the sort of the library inside the groups it is :math:` O( n log^2 n ) ` in the worst case, and close to linear on the usual texts;

  • suffixArraySkew(), the Skew (DC3) algorithm of Karkkainen and Sanders: the suffixes at the places :math:` i bmod 3 ne 0 ` (the :math:` P_{2,0} ` of the chapter, which counts from 1) are named by the ranks of their triples of symbols, sorted by three passes of radix sort, and sorted by the recursive suffix array of the string of the names, of 2 n / 3 symbols, unless all the names differ; the suffixes at :math:` i bmod 3 = 0 ` are sorted by the pair ( T[ i ] , rank of i + 1 ); the two lists are merged by comparing a pair or a triple whose last item is a rank in the sample. :math:` T( n ) = T( 2 n / 3 ) + O( n ) = O( n ) ` on an integer alphabet of O( n ) symbols, and the reduction to sorting gives the optimal :math:` O( Sort( n ) ) ` I/Os on disk (Theorem 10.3);

  • suffixArraySais(), the induced sorting of Nong, Zhang and Chan (SA-IS): each suffix is of type S or L as it is smaller or larger than the next one, and the leftmost S-suffixes of the runs (LMS) are at most n / 2; once the LMS-suffixes are sorted, one left-to-right scan of the buckets of the first symbols places the L-suffixes and one right-to-left scan the S-suffixes. The LMS-substrings are sorted by the same induction, named, and the string of the names is solved recursively when two of them are equal. O( n ) time, the smallest working space of the linear algorithms, and in practice two to three times faster than the Skew algorithm; with divsufsort, which also induces from a sorted sample, it is the method of the libraries in use;

  • suffixArrayScan(), the scan-based algorithm of Baeza-Yates, Gonnet and Snider for the disk: T is cut into blocks of m symbols, scanned from left to right; the suffixes that start in a block are sorted by comparisons, each earlier suffix is placed among them by binary search, and the counts C[ j ] of the earlier suffixes that fall between the block suffixes j - 1 and j merge the two arrays in one scan of the older one. :math:` O( n^2 log m / m ) ` comparisons of suffixes, i.e., cubic time in the worst case, but all its passes are sequential (Theorem 10.4).

lcpArray() is the algorithm of Kasai, Lee, Arimura, Arikawa and Park: LCP[ r ] is the length of the longest common prefix of the suffixes SA[ r ] and SA[ r + 1 ], and since the suffix i + 1 shares at least h - 1 symbols with its predecessor in SA when the suffix i shares h with its own (Facts 10.1 and 10.2), the suffixes taken in the order of the text extend h without going back, 2 n comparisons of symbols in all (Algorithm 10.2).

SuffixArray keeps T, SA, its inverse, LCP and two more arrays of the lcp, Llcp and Rlcp, of the suffix in the middle of each range of the binary search with the suffixes at its two ends:

  • range() is the binary search of Algorithm 10.1, twice (for P and for P followed by a symbol larger than all), :math:` O( p log n ) ` time (Lemma 10.1);

  • rangeLcp() is the search of Manber and Myers: knowing the lcp l and r of P with the suffixes at the ends of the range, a step that compares l with Llcp[ M ] (or r with Rlcp[ M ]) either decides without reading P or compares from the place max( l , r ), which never decreases, hence :math:` O( p + log n ) ` comparisons of symbols (Lemma 10.2);

  • lce( i , j ), the longest common extension of the suffixes i and j, is the minimum of LCP between their ranks, a query of File RangeMinimum.h, O( 1 ) time after O( n ) preprocessing.

A text is a std::string_view, whose symbols are its bytes, or a vector of integers in [ 0 , K ), e.g., several strings joined by separators [see File SuffixApplications.h]. The doubling needs :math:` n < 2^{32} `, since the radix sort takes a pair of ranks as one key of 64 bits.

The contracts [see File Contract.h]: the symbols of an integer text are less than K; every construction gives a suffix array, checked in O( n ) by comparing each adjacent pair through the ranks of the following suffixes (an audit), and lcpArray() the lcp of each adjacent pair (an audit); the two searches give the same range. The functions are defined in SuffixArray.tpp.

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

  1. Manber, G. Myers, Suffix arrays: a new method for on-line string searches, SIAM Journal on Computing 22(5), 935-948, 1993, doi:10.1137/0222058

    1. Larsson, K. Sadakane, Faster suffix sorting, Theoretical Computer Science 387(3), 258-272, 2007, doi:10.1016/j.tcs.2007.07.017

  1. Karkkainen, P. Sanders, S. Burkhardt, Linear work suffix array construction, Journal of the ACM 53(6), 918-936, 2006, doi:10.1145/1217856.1217858

  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. Gonnet, R. A. Baeza-Yates, T. Snider, New indices for text: PAT trees and PAT arrays, in W. B. Frakes, R. A. Baeza-Yates (eds.), Information Retrieval: Data Structures and Algorithms, Prentice-Hall, 66-82, 1992

    1. Puglisi, W. F. Smyth, A. H. Turpin, A taxonomy of suffix array construction algorithms, ACM Computing Surveys 39(2), 4, 2007, doi:10.1145/1242471.1242472

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes

Functions

Typedefs