File ParallelText.h

↰ Parent directory (ADS/parallel)

The parallel LCP array, beyond the book: lcpArray( ex , T , SA ) is the array of lcpArray( T , SA ) [see File SuffixArray.h], the longest common prefixes of the suffixes adjacent in the suffix array, on the threads of an executor [see File Executor.h], by the permuted LCP of Karkkainen, Manzini and Puglisi: :math:` Phi[ SA[ r ] ] = SA[ r - 1 ] , the suffix before each one in the order of the suffix array, then the permuted array :math: PLCP[ i ] = lcp( i , Phi[ i ] ) ` in the order of the text, and last :math:` LCP[ r - 1 ] = PLCP[ SA[ r ] ] `.

Definition (ADS/parallel/ParallelText.h)

Detailed Description

The first and the last steps are parallel loops of n scattered moves. The second is the scan of Kasai et al. along the text, which reads T in its order and uses :math:` PLCP[ i ] geq PLCP[ i - 1 ] - 1 ` to resume each comparison where the previous one stopped, :math:` O( n ) ` comparisons in all; the text is cut into 4 p parts, and each part starts its scan from h = 0, which costs at most the largest lcp more per part, so that the result is the same and the work :math:` O( n + p max_i PLCP[ i ] ) ` (on a text of one repeated symbol the parts gain nothing, since then the lcp are as long as the text). The scan by the text order reads :math:` Phi[ i ] ` and :math:` T[ Phi[ i ] + h ] ` at random once per suffix, where the algorithm of Kasai reads the rank and the suffix array at random.

lcpArrayPhi( ex , T , SA ) does the same on a text of bytes and a suffix array of indices of the type I (e.g., 32 bits), the result of lcpArrayPhi( T , SA ) [see File SuffixSorting.h]: its scans compare the first 4 symbols one by one and then 8 at a time by a load of 8 bytes, the first different byte found by the trailing zeros of the exclusive or, and fetch the text at :math:` Phi[ i + 16 ] ` ahead of its use.

The contracts [see File Contract.h]: SA is the suffix array of T (an audit); the result is the LCP array (an audit). J. Karkkainen, G. Manzini, S. J. Puglisi, Permuted longest-common- prefix array, Annual 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, Annual 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

Namespaces

Functions