TY - GEN
T1 - Tighter bounds for the sum of irreducible LCP values
AU - Kärkkäinen, Juha
AU - Kempa, Dominik
AU - Piąatkowski, Marcin
N1 - Publisher Copyright: © Springer International Publishing Switzerland 2015.
PY - 2015
Y1 - 2015
N2 - The suffix array is frequently augmented with the longestcommon- prefix (LCP) array that stores the lengths of the longest common prefixes between lexicographically adjacent suffixes of a text. While the sum of the values in the LCP array can be Ω(n2) for a text of length n, the sum of so-called irreducible LCP values was shown to be O(n lg n) just a few years ago. In this paper, we improve the bound to O(n lg r), where r ≤ n is the number of runs in the Burrows-Wheeler transform of the text. We also show that our bound is tight up to lower order terms (unlike the previous bound). Our results and the techniques used in proving them provide new insights into the combinatorics of text indexing and compression, and have immediate applications to LCP array construction algorithms.
AB - The suffix array is frequently augmented with the longestcommon- prefix (LCP) array that stores the lengths of the longest common prefixes between lexicographically adjacent suffixes of a text. While the sum of the values in the LCP array can be Ω(n2) for a text of length n, the sum of so-called irreducible LCP values was shown to be O(n lg n) just a few years ago. In this paper, we improve the bound to O(n lg r), where r ≤ n is the number of runs in the Burrows-Wheeler transform of the text. We also show that our bound is tight up to lower order terms (unlike the previous bound). Our results and the techniques used in proving them provide new insights into the combinatorics of text indexing and compression, and have immediate applications to LCP array construction algorithms.
UR - https://www.scopus.com/pages/publications/84949058302
U2 - 10.1007/978-3-319-19929-0_27
DO - 10.1007/978-3-319-19929-0_27
M3 - Conference contribution
SN - 9783319199283
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 316
EP - 328
BT - Combinatorial Pattern Matching - 26th Annual Symposium, CPM 2015, Proceedings
A2 - Vaccaro, Ugo
A2 - Porat, Ely
A2 - Cicalese, Ferdinando
PB - Springer Verlag
T2 - 26th Annual Symposium on Combinatorial Pattern Matching, CPM 2015
Y2 - 29 June 2015 through 1 July 2015
ER -