一种后缀数组和最长公共前缀的正确性验证方法及系统

摘要

本发明涉及一种后缀数组和最长公共前缀的正确性验证方法及系统。该方法包括：从右向左扫描一遍T，按照后缀类型定义比较字符T[i]及其后继字符T[i+1]的大小，计算T的字符T[i]和后缀suf(T,i)的类型，记录于t[i]中；将SA1和LCPA1中的元素初始化为‑1。从左到右扫描一遍SA，根据数组t找出SA中所有LMS后缀及其LCP值，分别依次记录在SA1和LCPA1中；根据字符串T、数组t、SA1和LCPA1，对SA1中相邻LMS后缀及其LCP值进行正确性验证；根据字符串T、数组t、B、C、SA1和LCPA1，归纳排序T的L型后缀及其LCP值；根据字符串T、数组t、B、C、SA1和LCPA1，归纳排序T的S型后缀及其LCP值；顺序扫描SA、SA1、LCPA和LCPA1一次，比较SA与SA1和LCPA与LCPA1是否相同，如果两组比较全部相同则T的SA和LCPA正确。

说明书

技术领域

本发明涉及数组正确性验证领域，更具体地，涉及一种后缀数组和最长公共前缀的正确性验证方法及系统。

背景技术

后缀数组SA为任意给定一个字符串T，从T的任意位置开始至其结尾的所有字符组成的字符串称为T的后缀。显然，长度为n的字符串包含n个后缀，对这n个后缀按字典顺序排序，并将其地址保存在一个整型数组中，该数组则称为字符串的后缀数组。最长公共前缀是后缀数组中相邻的两个后缀之间公共前缀的字符数。长度为n的字符串对应的最长公共前缀数组LCPA长度也为n，LCPA第一个元素为0，从第二个元素开始依次保存n个后缀对应的n-1个LCP值。后缀数组SA和最长公共前缀数组LCPA二者结合起来可以实现数据的全文索引，广泛应用于字符串处理、数据压缩、模式匹配、基因重组等领域。

在SA和LCPA构造完成后，为了避免可能存在的缺陷或计算错误，对二者进行正确性验证是必需的。目前已知的SA和LCPA正确性验证方法是两个相互独立的过程，先验证SA的正确性，然后再验证LCPA的正确性。比如，现有的SA正确性验证方法是在SA构造完成以后，执行两轮整数排序来验证SA的正确性。LCPA的正确性验证通常是采用暴力的方法依次对后缀数组中相邻两个后缀的公共前缀进行比较来验证。在数据集规模较大的情况下，由于两个验证过程相互独立，时间和空间开销相对较大。

发明内容

本发明提供一种后缀数组和最长公共前缀的正确性验证方法及系统，以克服后缀数组和最长公共前缀的正确性验证不能同时进行的问题。

本发明旨在至少在一定程度上解决上述技术问题。

为了达到上述技术效果，本发明的技术方案如下：

一种后缀数组和最长公共前缀的正确性验证方法，包括：从右向左扫描一遍T，按照后缀类型定义比较字符T[i]及其后继字符T[i+1]的大小，计算T的字符T[i]和后缀suf(T,i)的类型，记录于t[i]中；将SA1和LCPA1中的元素初始化为-1。从左到右扫描一遍SA，根据数组t找出SA中所有LMS后缀及其LCP值，分别依次记录在SA1和LCPA1中；根据字符串T、数组t、SA1和LCPA1，对SA1中相邻LMS后缀及其LCP值进行正确性验证；根据字符串T、数组t、B、C、SA1和LCPA1，归纳排序T的L型后缀及其LCP值；根据字符串T、数组t、B、C、SA1和LCPA1，归纳排序T的S型后缀及其LCP值；顺序扫描SA、SA1、LCPA和LCPA1一次，比较SA与SA1和LCPA与LCPA1是否相同，如果两组比较全部相同则T的SA和LCPA正确，否则错误。

优选地，根据字符串T、数组t、SA1和LCPA1，对SA1中相邻LMS后缀及其LCP值进行正确性验证，包括：计算FP(SA1[i],SA1[i]+LCPA1[i+1]-1)的指纹值，其中i∈[0,n1-2]，并保存字符T[SA1[i]+LCPA1[i+1]]；计算FP(SA1[j],SA1[j]+LCPA1[j]-1)的指纹值，其中j∈[1,n1-1]，并保存字符T[SA1[j]+LCPA1[j]]；逐次将指纹值FP(SA1[i],SA1[i]+LCPA1[i+1]-1)与FP(SA1[j],SA1[j]+LCPA1[j]-1)和字符T[SA1[i]+LCPA1[i+1]]与T[SA1[j]+LCPA1[j]]进行比较，如果指纹值相同且字符不同，说明LMS后缀及其LCP值正确。

优选地，根据字符串T、数组t、B、C、SA1和LCPA1，归纳排序T的L型后缀及其LCP值，包括：

(1)计算SA1中各字符桶的结束位置，保存在B数组中。从右向左扫描SA1，如果当前元素SA1[i]为-1，则继续扫描下一个元素，否则将SA1[i]保存至SA1中B[T[SA1[i]]]所指向的位置，同时将LCPA1[i]保存至LCPA1中B[T[SA1[i]]]所指向的位置，然后将SA1[i]字符桶的结束位置左移一步，将B[T[SA1[i]]]更新为B[T[SA[i]]]-1，最后将SA1[i]和LCPA1[i]设置为-1。

其中，SA1和LCPA1都是整型数组，分别保存了有序的LMS后缀及其LCP值，SA1与LCPA1的元素之间存在一一对应的关系。由于LMS后缀个数小于n，SA1和LCP1数组中只有部分空间有数据，其余空间的元素为-1。在从右向左扫描过程中，如果SA1元素不为-1，则将该元素填入SA1中对应字符桶的尾部，同时将该元素置为-1，该元素对应的LCPA1中的值也执行相同的移动和修改操作。

(2)计算SA1中各字符桶的开始位置，保存在B数组中。从左向右扫描SA1，如果当前元素SA1[i]在T中的前继T[SA1[i]-1]为S型或SA1[i]为-1，继续扫描下一个，否则将SA1[i]-1保存在SA1中B[T[SA1[i]-1]]指向的位置；接着计算SA1[B[T[SA1[i]-1]]]与其左侧最近的非-1元素SA1[j](0≤j＜B[T[SA1[i]-1]])的LCP值，如果两者指向的T中的字符不同则LCPA1[B[T[SA1[i]-1]]]＝0，如果两者指向的T中的字符和字符类型都相同则LCPA1[B[T[SA1[i]-1]]]＝C[T[SA1[i]-1]]+1；最后将B[T[SA1[i]-1]]更新为B[T[SA1[i]-1]]+1，即指向T[SA1[i]-1]字符桶的后一个位置。

其中，C数组保存的是当前元素SA1[i]与其左侧非-1元素SA1[k](k∈[0,i-1])的最长公共前缀，即LCPA1在区间[k+1,i]的RMQ值，其中k满足条件是：T[SA1[k]-1]与T[SA1[i]-1]相同，且在SA1的区间[k+1,i-1]中，没有元素在T中的前缀字符与T[SA1[i]-1]相同。

优选地，其特征在于，根据字符串T、数组t、B、C、SA1和LCPA1，归纳排序T的S型后缀及其LCP值，包括：计算SA1中各字符桶的结束位置，保存在B数组。从右向左扫描SA1，如果当前元素SA1[i]在T中的前继T[SA1[i]-1]为L型后缀，继续扫描下一个元素，否则将SA1[i]-1保存在SA1中B[T[SA1[i]-1]]指向的位置；接着计算SA1[B[T[SA1[i]-1]]]与其右侧相邻元素SA1[B[T[SA1[i]-1]]+1]的LCP值，如果两者指向的T中的字符不相同则LCPA1[B[T[SA1[i]-1]]+1]＝0，如果两者指向的T中的字符和字符类型都相同则LCPA1[B[T[SA1[i]-1]]+1]＝C[T[SA1[i]-1]]]+1；最后，单独计算各字符桶中最右侧的L型和最左侧的S型元素的LCP值，同时将B[T[SA1[i]-1]]更新为B[T[SA1[i]-1]]-1，即指向T[SA1[i]-1]字符桶的前一个位置。

其中，C数组保存的是当前扫描元素SA1[i]与其右侧元素SA1[k](k∈[i+1,n-1])的最长公共前缀，即LCPA1数组中区间[i+1,k]的RMQ值，其中k的位置满足条件是：T[SA1[k]-1]与T[SA1[i]-1]相同，且在SA1的区间[i+1,k-1]中，没有元素在T中的前缀字符与T[SA1[i]-1]相同。

一种后缀数组和最长公共前缀的正确性验证系统，包括：文件读写模块、L/S后缀识别模块、LMS后缀识别模块、LMS后缀及其LCP值正确性验证模块、L型后缀排序及其LCP值计算模块、S型后缀排序及其LCP值计算模块、SA及其LCPA验证模块和判定器；所述文件读写模块，用于读写字符串、SA、SA1、LCPA和LCPA1文件；所述L/S后缀识别模块，用于识别字符串后缀类型是L型或S型；所述LMS后缀识别模块，用于识别字符串的LMS后缀；所述LMS后缀及其LCP值正确性验证模块，用于从左向右扫描SA，获取其中的LMS后缀并使用RMQ计算其LCP值，然后使用指纹函数计算相邻LMS后缀各自公共前缀的指纹值，并保存它们公共前缀右边第一个字符。如果指纹函数值相同且保存的字符不同，则SA的LMS后缀和LCP值正确，否则错误；所述L型后缀排序及其LCP值计算模块，用于用LMS后缀及其LCP值归纳排序L型后缀，同时在归纳过程中计算L型后缀的LCP值；所述S型后缀排序及其LCP值计算模块，用于用L型后缀及其LCP值归纳排序S型后缀，同时在归纳过程中计算S型后缀的LCP值；所述SA及其LCPA验证模块，用于对已知的SA和LCPA与新计算出的SA1和LCPA1分别进行比较，如果SA与SA1相同且LCPA与LCPA1相同，则SA和LCPA正确，否则错误；所述判定器，用于判断LMS后缀及其LCP值是否正确，若是则进入下一步，否则程序结束。

与现有技术相比，本发明技术方案的有益效果是：

在SA和LCPA构建的完成后，可以同时实现对SA和LCPA的正确性验证。相比现有的验证方法，进一步降低了SA和LCPA正确性验证的时空开销。

附图说明

图1为一实施例的一种后缀数组和最长公共前缀的正确性验证方法的示意性流程图；

图2为另一实施例的一种后缀数组和最长公共前缀的正确性验证系统的示意性结构图。

具体实施方式

附图仅用于示例性说明，不能理解为对本专利的限制；

为了更好说明本实施例，附图某些部件会有省略、放大或缩小，并不代表实际产品的尺寸；

对于本领域技术人员来说，附图中某些公知结构及其说明可能省略是可以理解的。

下面结合附图和实施例对本发明的技术方案做进一步的说明。

实施例1

本实施例的基本思想是：首先，在SA和LCPA构造完成后，从左向右扫描SA找出所有的LMS后缀同时计算相邻LMS后缀之间的LCP值；其次，根据LCP的定义，使用指纹函数计算相邻LMS后缀最长公共前缀的指纹值，且保存各自最长公共前缀右边第一个字符，根据指纹值相同且保存字符不同，来验证LMS后缀及其LCP值的正确性。然后，用LMS后缀及其LCP值归纳排序L型后缀及其LCP，再用L型后缀及其LCP值归纳排序S型后缀及其LCP值。最后，将已知的SA与新计算的SA1以及已知的LCPA与新计算的LCPA1进行比较，如果两组比较完全相同，说明SA和LCPA正确，否则错误。

基于以上所述，本发明实施例提供了一种后缀数组和最长公共前缀数组正确性验证方法，参见图1，该方法具体步骤如下：

数组中的元素按从左至右的顺序存储，即最左边为第一个元素，最右边为最后一个元素。

T：输入字符串；/*长度为n个字符，包含n1个LMS子串*/

t：布尔数组；/*记录T的后缀类型，长度为n*/

SA:整型数组；/*记录T的后缀数组，长度为n*/

SA1：整形数组；/*记录新计算出的T的后缀数组，长度为n*/

LCPA：整形数组；/*记录T的LCP数组，长度为n*/

LCPA1：整形数组；/*记录新计算出的T的LCP数组，长度为n*/

B：整型数组；/*记录字符桶的开始或结束位置，长度为∑(T)，即T的字符集∑中的元素个数*/

C：整型数组；/*记录LCPA1中某一段区间的RMQ值，长度为∑(T)，*/

S101：从右向左扫描一遍T，按照后缀类型定义比较字符T[i]及其后继字符T[i+1]的大小，计算T的字符T[i]和后缀suf(T,i)的类型，记录于t[i]中。

S102：将SA1和LCPA1中的元素初始化为-1。从左到右扫描一遍SA，根据数组t找出SA中所有LMS后缀及其LCP值，分别依次记录在SA1和LCPA1中。

S103：根据字符串T、数组t、SA1和LCPA1，对SA1中相邻LMS后缀及其LCP值进行正确性验证；

所述步骤S103中，对SA1中相邻LMS后缀及其LCP值进行正确性验证的具体步骤如下：

31)计算FP(SA1[i],SA1[i]+LCPA1[i+1]-1)的指纹值，其中i∈[0,n1-2]，并保存字符T[SA1[i]+LCPA1[i+1]]；

32)计算FP(SA1[j],SA1[j]+LCPA1[j]-1)的指纹值，其中j∈[1,n1-1]，并保存字符T[SA1[j]+LCPA1[j]]；

33)逐次将指纹值FP(SA1[i],SA1[i]+LCPA1[i+1]-1)与FP(SA1[j],SA1[j]+LCPA1[j]-1)和字符T[SA1[i]+LCPA1[i+1]]与T[SA1[j]+LCPA1[j]]进行比较，如果指纹值相同且字符不同，说明LMS后缀及其LCP值正确。

S104：根据字符串T、数组t、B、C、SA1和LCPA1，归纳排序T的L型后缀及其LCP值；

所述步骤S104中，归纳排序T的L型后缀及其LCP值具体步骤如下：

41)计算SA1中各字符桶的结束位置，保存在B数组中。从右向左扫描SA1，如果当前元素SA1[i]为-1，则继续扫描下一个元素，否则将SA1[i]保存至SA1中B[T[SA1[i]]]所指向的位置，同时将LCPA1[i]保存至LCPA1中B[T[SA1[i]]]所指向的位置，然后将SA1[i]字符桶的结束位置左移一步，将B[T[SA1[i]]]更新为B[T[SA[i]]]-1，最后将SA1[i]和LCPA1[i]设置为-1。

其中，SA1和LCPA1都是整型数组，分别保存了有序的LMS后缀及其LCP值，SA1与LCPA1的元素之间存在一一对应的关系。由于LMS后缀个数小于n，SA1和LCP1数组中只有部分空间有数据，其余空间的元素为-1。在从右向左扫描过程中，如果SA1元素不为-1，则将该元素填入SA1中对应字符桶的尾部，同时将该元素置为-1，该元素对应的LCPA1中的值也执行相同的移动和修改操作。

42)计算SA1中各字符桶的开始位置，保存在B数组中。从左向右扫描SA1，如果当前元素SA1[i]在T中的前继T[SA1[i]-1]为S型或SA1[i]为-1，继续扫描下一个，否则将SA1[i]-1保存在SA1中B[T[SA1[i]-1]]指向的位置；接着计算SA1[B[T[SA1[i]-1]]]与其左侧最近的非-1元素SA1[j](0≤j＜B[T[SA1[i]-1]])的LCP值，如果两者指向的T中的字符不同则LCPA1[B[T[SA1[i]-1]]]＝0，如果两者指向的T中的字符和字符类型都相同则LCPA1[B[T[SA1[i]-1]]]＝C[T[SA1[i]-1]]+1；最后将B[T[SA1[i]-1]]更新为B[T[SA1[i]-1]]+1，即指向T[SA1[i]-1]字符桶的后一个位置。

其中，C数组保存的是当前元素SA1[i]与其左侧非-1元素SA1[k](k∈[0,i-1])的最长公共前缀，即LCPA1在区间[k+1,i]的RMQ值，其中k满足条件是：T[SA1[k]-1]与T[SA1[i]-1]相同，且在SA1的区间[k+1,i-1]中，没有元素在T中的前缀字符与T[SA1[i]-1]相同。

S105：根据字符串T、数组t、B、C、SA1和LCPA1，归纳排序T的S型后缀及其LCP值；

所述步骤S105中，归纳排序T的S型后缀及其LCP具体步骤如下：

51)计算SA1中各字符桶的结束位置，保存在B数组。从右向左扫描SA1，如果当前元素SA1[i]在T中的前继T[SA1[i]-1]为L型后缀，继续扫描下一个元素，否则将SA1[i]-1保存在SA1中B[T[SA1[i]-1]]指向的位置；接着计算SA1[B[T[SA1[i]-1]]]与其右侧相邻元素SA1[B[T[SA1[i]-1]]+1]的LCP值，如果两者指向的T中的字符不相同则LCPA1[B[T[SA1[i]-1]]+1]＝0，如果两者指向的T中的字符和字符类型都相同则LCPA1[B[T[SA1[i]-1]]+1]＝C[T[SA1[i]-1]]]+1；最后，单独计算各字符桶中最右侧的L型和最左侧的S型元素的LCP值，同时将B[T[SA1[i]-1]]更新为B[T[SA1[i]-1]]-1，即指向T[SA1[i]-1]字符桶的前一个位置。

其中，C数组保存的是当前扫描元素SA1[i]与其右侧元素SA1[k](k∈[i+1,n-1])的最长公共前缀，即LCPA1数组中区间[i+1,k]的RMQ值，其中k的位置满足条件是：T[SA1[k]-1]与T[SA1[i]-1]相同，且在SA1的区间[i+1,k-1]中，没有元素在T中的前缀字符与T[SA1[i]-1]相同。

S106：顺序扫描SA、SA1、LCPA和LCPA1一次，比较SA与SA1和LCPA与LCPA1是否相同，如果两组比较全部相同则T的SA和LCPA正确，否则错误。

本方案在SA和LCPA构建的完成后，可以同时实现对SA和LCPA的正确性验证。相比现有的验证方法，进一步降低了SA和LCPA正确性验证的时空开销。

实施例2

本发明实施例还提供了一种后缀数组和最长公共前缀正确性验证系统，如图2的结构示意图，包括：

文件读写模块1，用于读写字符串、SA、SA1、LCPA和LCPA1文件；

L/S后缀识别模块2，用于识别字符串后缀类型是L型或S型；

LMS后缀识别模块3，用于识别字符串的LMS后缀；

LMS后缀及其LCP值正确性验证模块4，该模块的主要功能为：从左向右扫描SA，获取其中的LMS后缀并使用RMQ计算其LCP值，然后使用指纹函数计算相邻LMS后缀各自公共前缀的指纹值，并保存它们公共前缀右边第一个字符。如果指纹函数值相同且保存的字符不同，则SA的LMS后缀和LCP值正确，否则错误；

L型后缀排序及其LCP值计算模块6，用LMS后缀及其LCP值归纳排序L型后缀，同时在归纳过程中计算L型后缀的LCP值；

S型后缀排序及其LCP值计算模块7，用L型后缀及其LCP值归纳排序S型后缀，同时在归纳过程中计算S型后缀的LCP值；

SA及其LCPA验证模块8，对已知的SA和LCPA与新计算出的SA1和LCPA1分别进行比较，如果SA与SA1相同且LCPA与LCPA1相同，则SA和LCPA正确，否则错误；

判定器A5，判断LMS后缀及其LCP值是否正确，若是则进入下一步，否则程序结束。

本方案在SA和LCPA构建的完成后，可以同时实现对SA和LCPA的正确性验证。相比现有的验证方法，进一步降低了SA和LCPA正确性验证的时空开销。

相同或相似的标号对应相同或相似的部件；

附图中描述位置关系的用于仅用于示例性说明，不能理解为对本专利的限制；

显然，本发明的上述实施例仅仅是为清楚地说明本发明所作的举例，而并非是对本发明的实施方式的限定。对于所属领域的普通技术人员来说，在上述说明的基础上还可以做出其它不同形式的变化或变动。这里无需也无法对所有的实施方式予以穷举。凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明权利要求的保护范围之内。