Checking Big Suffix and LCP Arrays by Probabilistic Methods
Checking Big Suffix and LCP Arrays by Probabilistic Methods
复制标题
DOI：
10.1109/tc.2017.2702642
复制
发表时间：
2017-10
影响因子：
3.7
通讯作者：
Yi Wu;Ge Nong;W. H. Chan;L. Han
中科院分区：
文献类型：
--
作者：
Yi Wu;Ge Nong;W. H. Chan;L. Han
对于海量数据的全文索引，后缀和LCP（最长公共前缀）数组已被公认为基本的数据结构，并且在实践中至少存在两种需要来检查其正确性，即，对概率算法构造的数组进行程序调试和验证。提出了两种概率方法，使用Karp-Rabin指纹技术来检查外部存储器中常量或整数字母的后缀和LCP阵列，其中检查仅以可忽略的错误概率出错。第一种方法通过计算和比较两个后缀的LCP的指纹来检查它们的字典序和LCP值。这种方法是通用的，因为它可以验证任何顺序的任何完整或稀疏后缀/LCP数组。第二种方法占用的空间较少，它首先利用指纹识别技术验证给定后缀和LCP数组的一个子集，从中归纳出两个新的后缀和LCP数组，并与给定数组进行比较以进行验证，对于常量字母表，可以去除归纳出的后缀和LCP数组以节省空间。
For full-text indexing of massive data, the suffix and LCP (longest common prefix) arrays have been recognized as fundamental data structures, and there are at least two needs in practice for checking their correctness, i.e., program debugging and verifying the arrays constructed by probabilistic algorithms. Two probabilistic methods are proposed to check the suffix and LCP arrays of constant or integer alphabets in external memory using a Karp-Rabin fingerprinting technique, where the checking is wrong only with a negligible error probability. The first method checks the lexicographical order and the LCP-value of two suffixes by computing and comparing the fingerprints of their LCPs. This method is general in terms of that it can verify any full or sparse suffix/LCP array of any order. The second method uses less space, it first employs the fingerprinting technique to verify a subset of the given suffix and LCP arrays, from which two new suffix and LCP arrays are induced and compared with the given arrays for verification, where the induced suffix and LCP arrays can be removed for constant alphabets to save space.