File SuffixSorting.h

↰ Parent directory (ADS/string)

The engineered construction of the suffix array and of its LCP array, beyond the book: the ones that the benchmark of the suffix arrays compares with libsais and libdivsufsort, while the constructions of File SuffixArray.h stay those of the textbook, on integers of the size of a pointer.

Definition (ADS/string/SuffixSorting.h)

Detailed Description

suffixArray() is the induced sorting of Nong, Zhang and Chan (SA-IS) [see File SuffixArray.h] on integers of 32 bits (or of 64, for the texts of :math:` 2^{31} ` symbols or more). The suffix i of T (n symbols in [ 0 , K )) is of type :math:`[
t_i = left{ begin{array}{ll}
L & i = n - 1 mbox{ or } T[ i ] > T[ i + 1 ] mbox{ or }

( T[ i ] = T[ i + 1 ] mbox{ and } t_{i+1} = L ) \

S & mbox{otherwise,}

end{array} right.

` S if it is smaller than the suffix i + 1, and i is an LMS place if :math:` t_i = S ` and :math:` t_{i-1} = L ; two LMS places are never adjacent, so that there are :math: m le lfloor n / 2 rfloor ` of them. Once the LMS-suffixes are sorted and put at the ends of the buckets of their first symbols, one scan from left to right puts each L-suffix i - 1 at the head of its bucket after the suffix i, and one from right to left each S-suffix i - 1 at the tail of its bucket, which sorts all of them; the same two scans from the LMS places in any order sort the LMS-substrings (from an LMS place to the next one), whose names give a string of m symbols whose suffix array orders the LMS-suffixes, so that :math:`[

T( n ) le T( lfloor n / 2 rfloor ) + O( n ) = O( n ) .

` Besides T and the n words of SA, a level takes 8 K words for the counts and the parts of the buckets and n / 32 words for two bit vectors, and the levels together :math:` O( n ) ` words. As engineered here:

  • the types, 64 places a word: with :math:` G ` the bits of the places where :math:` T[ i ] < T[ i + 1 ] ` and :math:` E ` of those where they are equal, both from vector comparisons (AVX2) and read from the higher places to the lower ones, the bits of type S are the carries of the one addition :math:` G + ( G vee E ) , since :math: t_i = S ` if and only if :math:` G_i vee ( E_i wedge t_{i+1} = S ) `, the carry rule of a sum; a word costs a few operations, and only the carry passes from word to word. The suffixes i >= 1 fall into the four kinds of the types of i and i - 1 (LL, LS, LMS and SS), counted per first symbol with no branch in two histograms, one for the even places and one for the odd, so that equal symbols in a row do not wait for each other, the counters 4 T[ i ] + kind of 64 places built by vector operations from the bits of the types;

  • on a text of bytes the LMS-suffixes are first sorted directly, as strings, and the induction only follows (the two stages of Itoh and Tanaka and of DivSufSort, on the LMS-suffixes of SA-IS): the :math:` sigma ` bytes that occur are ranked, and when :math:` sigma le 64 ` the text is packed in codes of :math:` b = lceil log_2 sigma rceil ` bits (the bytes themselves otherwise, b = 8), so that the window of 64 bits at the bit b p of the packed text holds the first :math:` 64 / b ` symbols of the suffix p and two suffixes compare as their windows, then as the windows 64 bits on. The items ( top bits of the window , p ), one word on 32 bits, are sorted by a radix sort on the top :math:` N = lceil log_2 ( m + 1 ) rceil + 6 ` bits of their windows (into the 256 buckets of the top 8 bits first when :math:` m ge 2^{16} , then each bucket in the cache by passes of at most 11 bits), so that on a text with no long repeats about :math: m^2 / 2^{N+1} le m / 128 ` pairs stay equal, settled by insertion; the suffixes of equal windows go on to the next windows, a suffix that ends inside a window before those that go on. The whole of it reads the text in order, against the 2 random reads a suffix of the partial induction, and needs no names and no recursion. It is tried when a sample of 1024 keys of 32 bits has at most one equal pair in 256 (on a text whose windows repeat, as in English or in long repeats, the induction does better), and given up for the partial induction once the ties read more than m windows;

  • the partial induction, which sorts the LMS-substrings, splits the bucket of each symbol c into parts by the type of the suffix before: an area A, with the LL part and the LMS part (the seeds) of each symbol, holds the entries that the scan from left to right moves, and an area C, with the LS part and the SS part, those that the scan from right to left moves, so that no scan visits an entry with nothing to do. An entry is marked when it starts a new name: a moved suffix is marked unless the last one moved into the same part came from a suffix of the same name, the name being the count d of the marks the scan has met; the scans keep the arrays in functions that declare them not to overlap, two entries a step, the text 64 entries ahead prefetched and, beyond 65536 symbols, the parts and the places they point to;

  • the names are written only when some are tied, and two LMS-suffixes of equal names (equal LMS-substrings, of the same length l) compare as the text that follows them: on the bytes, when the groups of equal names have at most 16 suffixes on average, each group is sorted by keys of 8 bytes of the text read at p + l, p + l + 8, …, round after round on the parts still tied (at most 8 rounds and 2 m keys, and none if a first round on a sample of the groups leaves half of them tied, as on long repeats), small groups by insertion and large ones by a radix sort on the bits that their keys do not share, gathered by pext; the names are then those of the groups left (finer than the LMS-substrings: equal names still mean equal LMS-substrings, and a smaller name a smaller suffix), and the groups left are sorted by the names that follow, within a budget of m names, and only then by the doubling of Larsson and Sadakane on the groups of equal names (when few, or small) or by the recursion on the string of the names, in SA[ m .. 2 m ): in the round h = 1, 2, 4, … of the doubling the suffixes of a group, equal on their first h names, are sorted by :math:` V[ i + h ] , the rank of the suffix h places ahead, a group of g suffixes costing :math: O( g log g ) `;

  • the sorted LMS-suffixes go to the ends of their buckets a group of symbol at a time, by memmove(), and the final induction stores a suffix with its top bit set when the suffix before it is of the other type, by a shift and no branch, the text it prefetches at a place chosen by a select;

  • a text whose suffixes are all of type L never rises, so that each suffix is larger than the next one and SA is :math:` n - 1 , ldots , 0 `.

lcpArrayPhi() is the algorithm of Karkkainen, Manzini and Puglisi: with :math:` Phi[ SA[ r ] ] = SA[ r - 1 ] `, the permuted LCP :math:`[

mathit{PLCP}[ i ] = mathrm{lcp}( T[ i .. ] , T[ Phi[ i ] .. ] ) , qquad mathit{PLCP}[ i + 1 ] ge mathit{PLCP}[ i ] - 1

` (Lemma of Kasai et al.), is computed in the order of the text from the value at i - 1 less one, :math:` 2 n ` comparisons of symbols in all, one symbol at a time (the lcp grows by n + 1 at most in all, so that loads of 8 bytes would save little); the text at :math:` Phi[ i + 64 ] ` is prefetched, and :math:` mathit{LCP}[ r ] = mathit{PLCP}[ SA[ r + 1 ] ] ` costs one random read per entry, prefetched too: from :math:` 2^{18} ` bytes on, where n integers leave the cache, PLCP is also kept as n bytes, :math:` min( mathit{PLCP}[ i ] , 255 ) , and the read falls in them, the integer read only for 255 (the bytes are dropped when more than n / 64 values reach 255, as on long repeats). LCP[ r ] is the lcp of the suffixes SA[ r ] and SA[ r + 1 ], n - 1 entries, as in lcpArray(); :math: Phi ` and PLCP share one array of n integers, and the three passes keep their arrays in functions that declare them not to overlap.

The arrays built, SA, PLCP and LCP, ask for transparent huge pages (madvise(), on Linux) before they are first written, so that their page faults are 512 times fewer and the random writes of the induction and of :math:` Phi ` miss the TLB less.

The contracts [see File Contract.h]: the symbols of an integer text are less than K and n fits the integers; the arrays built are a suffix array and its LCP array (audits, O( n ) and :math:` O( n + sum_r mathit{LCP}[ r ] ) ` time). The functions are defined in SuffixSorting.tpp.

  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

  2. Itoh, H. Tanaka, An efficient method for in memory construction of suffix arrays, Proceedings of the 6th Symposium on String Processing and Information Retrieval (SPIRE), 81-88, 1999, doi:10.1109/SPIRE.1999.796581

  1. Fischer, F. Kurpicz, Dismantling DivSufSort, Proceedings of the Prague Stringology Conference (PSC), 62-76, 2017, https://arxiv.org/abs/1710.01896

    1. Knuth, The Art of Computer Programming, vol. 3, 2nd ed., Addison-Wesley, 1998, section 5.2.5 (radix sorting)

  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, G. Manzini, S. J. Puglisi, Permuted longest-common- prefix array, Proceedings of the 20th Symposium on Combinatorial Pattern Matching (CPM), LNCS 5577, 181-192, 2009, doi:10.1007/978-3-642-02441-2_17

  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

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

  • ADS/Contract.h (File Contract.h)

  • ADS/string/impl/SuffixSorting.tpp

  • concepts

  • cstddef

  • cstdint

  • string_view

  • vector

Included By

Namespaces

Functions