LCP Array Construction Using O(sort(n)) (or Less) I/Os
LCP Array Construction Using O(sort(n)) (or Less) I/Os
复制标题
使用 O(sort(n))（或更少）I/O 构建 LCP 数组
DOI：
10.1007/978-3-319-46049-9_20
复制
发表时间：
2016
影响因子：
0.5
通讯作者：
Dominik Kempa
中科院分区：
文献类型：
--
作者：
Juha Kärkkäinen;Dominik Kempa
后缀数组是现代字符串处理中最重要的数据结构之一，在许多应用中需要使用最长公共前缀 (LCP) 数组进行扩充。它们的构造通常是一个主要瓶颈，尤其是当数据对于内存来说太大时。虽然存在外部存储器算法以最佳 I/O 复杂度 \(\mathcal {O}\!\left( {\mathrm {sort}\!\left( {n} \right) } \right) \) 同时构造后缀数组和 LCP 数组，但出于多种原因，最好首先构造后缀数组，然后在单独的阶段中根据后缀数组构造 LCP 数组。在本文中，我们描述了第一个在 LCP 数组构建阶段实现 \(\mathcal {O}\!\left( {\mathrm {sort}\!\left( {n} \right) } \right) \) I/O 复杂度的算法，并且不是后缀排序算法的扩展。作为一种变体，我们获得了一种蒙特卡罗算法，给定一个按排序顺序包含 \(m < n\) 个后缀的稀疏后缀数组，计算 \(\mathcal {O}\!\left( {\mathrm {scan}\!\left( {n} \right) +\mathrm {sort}\!\left( {m} \right) \log (n/m)} \right) \) 中相应的 LCP 数组，如果后缀位置均匀分布，并且一般在 \(\mathcal {O}\!\left( {\mathrm {scan}\!\left( {n} \right) +\mathrm {sort}\!\left( {m} \right) \log (n)} \right) \) I/O 中。
The suffix array, one of the most important data structures in modern string processing, needs to be augmented with the longest-common-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 \(\mathcal {O}\!\left( {\mathrm {sort}\!\left( {n} \right) } \right) \), 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 \(\mathcal {O}\!\left( {\mathrm {sort}\!\left( {n} \right) } \right) \) 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 \(\mathcal {O}\!\left( {\mathrm {scan}\!\left( {n} \right) +\mathrm {sort}\!\left( {m} \right) \log (n/m)} \right) \) I/Os if the suffix positions are evenly spaced, and in \(\mathcal {O}\!\left( {\mathrm {scan}\!\left( {n} \right) +\mathrm {sort}\!\left( {m} \right) \log (n)} \right) \) I/Os in general.