File LongestCommonExtension.h

↰ Parent directory (ADS/string)

The engineered longest common extensions of a text, beyond the book: the lce( i , j ) of the suffixes i and j of T, the length of their longest common prefix, which the benchmark of the suffix arrays compares with the lce() of File SuffixArray.h (the range minimum of Bender and Farach-Colton), with a range minimum of sdsl-lite and with the direct comparison of the two suffixes, while File SuffixArray.h stays the textbook.

Definition (ADS/string/LongestCommonExtension.h)

Detailed Description

With SA the suffix array of T, :math:` SA^{-1} ` its inverse and LCP its LCP array (LCP[ r ] the lcp of the suffixes SA[ r ] and SA[ r + 1 ]), :math:`[

mathrm{lce}( i , j ) = min_{ a le r < b } LCP[ r ] , qquad a = min( SA^{-1}[ i ] , SA^{-1}[ j ] ) , ; b = max( SA^{-1}[ i ] , SA^{-1}[ j ] ) ,

` a range minimum query; LceIndex builds SA by suffixArray() and LCP by lcpArrayPhi() [see File SuffixSorting.h], and answers in two stages:

  • the first 64 symbols of the two suffixes are compared directly, 32 at a time with AVX2 (8 else), since on most texts most extensions are short, and the direct comparison, which reads two lines of the text, is then faster than any query that reads the inverse and the LCP array at random (Ilie, Navarro and Tinta found it the fastest on the texts with few long repeats); the first chunk is inlined where lce() is called, the rest is out of line;

  • the longer ones go to the range minimum on LCP, cut into blocks of 16 entries, each one line of the cache. For the entry r of a block that starts at s a word :math:` M_r ` of 16 bits has the bit k set if :math:` LCP[ s + k ] < LCP[ s + k’ ] ` for every :math:` k < k’ le r - s , i.e., if s + k is on the stack of the suffix minima of the block up to r; the minimum of :math: LCP[ s + a .. r ] ` is then :math:` LCP[ s + a + mathrm{ctz}( M_r gg a ) ] , one shift and one count of trailing zeros (the words of Alstrup, Gavoille, Kaplan and Rauhe). The blocks form groups of 64, each with the sparse table of the minima of its blocks, :math: min_{ x le d < x + 2^L } ` for :math:` L le 6 , and the minima of the groups are in a sparse table of their own; the blocks strictly between those of a and b - 1 are covered by two overlapping ranges of one group, or by those of two partial groups and of the groups between them. Every place that a query reads is known once the two ranks are, and the lines of the two blocks are requested with their words, so that a query waits for two reads of the memory in a row: the ranks, then all the rest. Building it costs O( n ) but for the table of the groups, :math: O( ( n / 1024 ) log( n / 1024 ) ) `, and a query O( 1 ).

The space is 4 n bytes for each of :math:` SA^{-1} ` and LCP (on 32 bits), 2 n for the words, 1.75 n for the tables of the groups and a vanishing share for the table of the groups, against the 2 n + o( n ) bits of the succinct range minima of Fischer and Heun, whose practical form (Baumstark, Gog, Heuer and Labeit) pays for its space with a select on a balanced-parentheses sequence at each query.

The contracts [see File Contract.h]: a query asks for i , j <= n (n gives 0), and its answer is the lcp of the two suffixes (an audit, linear in it). The functions are defined in LongestCommonExtension.tpp.

  1. Ilie, G. Navarro, L. Tinta, The longest common extension problem revisited and applications to approximate string searching, Journal of Discrete Algorithms 8(4), 418-428, 2010, doi:10.1016/j.jda.2010.08.004

  1. Alstrup, C. Gavoille, H. Kaplan, T. Rauhe, Nearest common ancestors: a survey and a new distributed algorithm, Proceedings of the 14th ACM Symposium on Parallel Algorithms and Architectures (SPAA), 258-264, 2002, doi:10.1145/564870.564914

  1. Fischer, V. Heun, Space-efficient preprocessing schemes for range minimum queries on static arrays, SIAM Journal on Computing 40(2), 465-492, 2011, doi:10.1137/090779759

  1. Baumstark, S. Gog, T. Heuer, J. Labeit, Practical range minimum queries revisited, Proceedings of the 16th International Symposium on Experimental Algorithms (SEA), LIPIcs 75, 12:1-12:16, 2017, doi:10.4230/LIPIcs.SEA.2017.12

    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

Namespaces

Classes