TY - GEN
T1 - LCP array construction using O(Sort(n)) (or less) I/Os
AU - Kärkkäinen, Juha
AU - Kempa, Dominik
N1 - Publisher Copyright:
© Springer International Publishing AG 2016.
PY - 2016
Y1 - 2016
N2 - The suffix array, one of the most important data structures in modern string processing, needs to be augmented with the longestcommon- prefix (LCP) array in many applications. Their construction is often a major bottleneck especially when the data is too big for internal memory. While there are external memory algorithms that construct the suffix array and the LCP array simultaneously in the optimal I/O complexity of O(sort(n)), for several reasons it would be desirable to construct the suffix array first and then the LCP array from the suffix array in a separate stage. In this paper we describe the first algorithm that achieves O(sort(n)) I/O complexity for the LCP array construction stage and is not an extension of a suffix sorting algorithm. As a variant, we obtain a Monte Carlo algorithm that, given a sparse suffix array containing m < n suffixes in sorted order, computes the corresponding LCP array in O(scan(n) + sort(m) log(n/m)) I/Os if the suffix positions are evenly spaced, and in O(scan(n) + sort(m) log(n)) I/Os in general.
AB - The suffix array, one of the most important data structures in modern string processing, needs to be augmented with the longestcommon- prefix (LCP) array in many applications. Their construction is often a major bottleneck especially when the data is too big for internal memory. While there are external memory algorithms that construct the suffix array and the LCP array simultaneously in the optimal I/O complexity of O(sort(n)), for several reasons it would be desirable to construct the suffix array first and then the LCP array from the suffix array in a separate stage. In this paper we describe the first algorithm that achieves O(sort(n)) I/O complexity for the LCP array construction stage and is not an extension of a suffix sorting algorithm. As a variant, we obtain a Monte Carlo algorithm that, given a sparse suffix array containing m < n suffixes in sorted order, computes the corresponding LCP array in O(scan(n) + sort(m) log(n/m)) I/Os if the suffix positions are evenly spaced, and in O(scan(n) + sort(m) log(n)) I/Os in general.
UR - https://www.scopus.com/pages/publications/84989837808
U2 - 10.1007/978-3-319-46049-9_20
DO - 10.1007/978-3-319-46049-9_20
M3 - Conference contribution
AN - SCOPUS:84989837808
SN - 9783319460482
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 204
EP - 217
BT - String Processing and Information Retrieval - 23rd International Symposium, SPIRE 2016, Proceedings
A2 - Inenaga, Shunsuke
A2 - Sadakane, Kunihiko
A2 - Sakai, Tetsuya
PB - Springer Verlag
T2 - 23rd International Symposium on String Processing and Information Retrieval, SPIRE 2016
Y2 - 18 October 2016 through 20 October 2016
ER -