Inducing Suffix and LCP Arrays in External Memory
Inducing Suffix and LCP Arrays in External Memory
复制标题
DOI：
10.1145/2975593
复制
发表时间：
2013-01
期刊：
影响因子：
--
通讯作者：
Timo Bingmann;J. Fischer;Vitaly Osipov
中科院分区：
文献类型：
--
作者：
Timo Bingmann;J. Fischer;Vitaly Osipov
我们考虑在外部存储器(EM)中构建全文索引。我们的第一个贡献是外部存储器中的后缀数组的归纳算法，该算法运行在排序复杂度上。实际测试表明，该算法在时间和I/O量上比以前最好的EM后缀排序器[Dementiev等人，JEA 2008]的性能提高了大约两倍。我们的第二个贡献是对第一个算法的增强，以也构造最长公共前缀(LCP)数组。这产生了新的内存LCP阵列构造算法和第一个用于LCP阵列的EM构造算法。与普通后缀数组构造相比，这种扩展算法在时间和I/O容量上的开销大约是2。我们的算法的规模远远超过了以前文献中考虑的问题大小(在我们的实验中，仅使用4GiB的RAM即可获得80GiB的文本大小)。
We consider full text index construction in external memory (EM). Our first contribution is an inducing algorithm for suffix arrays in external memory, which runs in sorting complexity. Practical tests show that this algorithm outperforms the previous best EM suffix sorter [Dementiev et al., JEA 2008] by a factor of about two in time and I/O volume. Our second contribution is to augment the first algorithm to also construct the array of longest common prefixes (LCPs). This yields a new internal memory LCP array construction algorithm and the first EM construction algorithm for LCP arrays. The overhead in time and I/O volume for this extended algorithm over plain suffix array construction is roughly two. Our algorithms scale far beyond problem sizes previously considered in the literature (text size of 80GiB using only 4GiB of RAM in our experiments).