|
from http://blog.csdn.net/joylnwang/article/details/6878068 2011.10 之前我的《BM算法详解》一文中有一个巨大的缺憾，就是没能给出计算模式串好后缀跳转表的高效算法。Robert S.Boyer和J Strother Moore两人的论文中，不知什么原因，并没有给出这样的算法，蛮力算法O(n^3)的时间复杂度使得BM算法的实用性大打折扣。实际上线性时间内计算出模式串的好后缀跳转表的算法是存在，但是在介绍这个算法之前，我要向大家推荐一本字符串处理方面的权威著作《Algorithms on Strings，Trees and Sequences》，作者Dan Gusfield。书中几乎涵盖了当今具有实用价值的所有字符串处理技术，当然BM和KMP算法也涵盖其中，本文的内容就源于此书。不过这本书的内容可以说是非常非常的难，要想全部吃透十分不易。 在我的有关KMP，BM算法的两篇文章中，我已经提到了一个关键的问题，那就是前/后缀的自包含问题。无论是KMP算法还是BM算法的跳转表，都与自包含前/后缀有着直接的联系。这里我们需要引入一个概念Zi(S)，其中S代表模式串，对于模式串S[1...n]，Zi(S)表示子串S[i...j]的长度，其中j是所有满足S[i...j]=S[1...j-i+1]的j中的最大者。说起来挺玄乎，实际就是以i为起始的最长包含前缀。对于S=aabcaabxaaz，我们有
由上面Z5(S)=3我们知道S[5...7]=S[1...3]，且S[5...8]!=S[1...4]，这里我们把S[5...7]叫做字符串S的一个Z-block，对于Zi(S)，如果Zi(S)!=0，那么所标记的Z-block起始于i，结束于i+Zi(S)-1。显然，一个字符串可能包含若干个Z-block，而且各Z-block之间可能互相交叠。我们再定义两个值li，ri，其中li，ri是包含S[i]的所有Z-block中右端点最大的一个，如下图所示，这里包含i的Z-block有两个，只有标注a的Z-block的l值和r值，才是li和ri的实际值。实际上S[li...ri]=S[1...ri-li+1]。
现在我们就来介绍一下，在Z1(S)，……，Zi(S)，li，ri已知的情况下，如何求解Zi+1(S)，这里我们令li=l, ri=r, i+1=k, i-li+2=k'。 1. 如果k，Zk'(S)与l，r的所决定的Z-block关系如下图所示，因为S[l...r]=S[1...r-l+1]，所以我们可以把S[l...r]区间内的问题，放到S[1...r-l+1]区间内来考虑，此时k在1，r-l+1区间内的对应点就是k'。我们需要关注Zk'(S)这个已知量，在下图所示的这种情况中，Zk'(S)所决定Z-block完全包含在1，r-l+1区间内。也就是k'+Zk'(S)-1<r-l+1，此时Zk(S)实际上就等于Zk'(S)。
2. 如果k，Zk'(S)与l，r的所决定的Z-block关系如下图所示。此时，我们也同样将S[l...r]区间内的问题，放到S[1...r-l+1]区间内来分析。此时Zk'(S)所决定的Z-block的右端要超过r-l+1，也就是说对于Zk(S)，我们已经知道其前r-k+1个元素与S[1...r-k+1]相同，但是对于S[r]以后的元素是否还可以与前面的r-k+1个元素连起来形成更长的包含前缀我们还只有进行比较后才能知道。由于之前我们的已经有S[k...r]=S[k'...r-l+1]=S[1...r-k+1]（注意图中几个标注beta的区域），所以我们可以省去对这两个区间的比较，直接从S[r-k+2]开始与S[r-k+2]进行比较，直到匹配失败为止，此时我们就得到新的右端点ri+1，同时将li+1更新为i+1。
3. 如果r<=k。那么之前计算出的Z-block对我们没有任何帮助，我们从r开始，找到最小的k，使得S[r...k]!=S[1...r-k+1]。此时我们同时还要更新对应的li+1=i+1，ri+1=k-1。 分别处理上述三种情况，我们就可以在线性时间内，递推填写S[1...n]的所有Zi(S)值。假设模式串S="aabaabcaxaabaabcy"，其对应的Zi(S)值如下表。
当我们要计算Z12(S)时，Z1(S)到Z11(S)都已经计算得到，此时的l=10，r=15，也就是说S[10...15]所形成的Z-block是当前的最右Z-block且包含S[12]。此时我们要计算Z12(S)，由于S[10...15]=S[1...6]，所以Z12(S)与Z3(S)密切相关，我们发现Z3(S)=0，3+Z3(S)=3<6，这个符合前面的第一种情况，所以Z12(S)=Z3(S)=0. 对于Z10(S)，当计算Z10(S)时，已知的最右Z-block是S[8]，l=8，r=8，因为10>8，所以符合上述第三种情况，我们直接从S[10]开始向后寻找S的包含前缀，找到S[10...15]是一个长度为6的S的包含前缀，所以Z10(S)=6，同时更新l=10，r=15. 在Zi(S)值计算中，第二种情况的场景比较少见，但是第二种情况也是Zi(S)计算中最容易出问题的部分。 下面给出我自己写的计算Z数组的算法
因为普通的字符串是从索引0开始，所以算法中对此作了调整。
Z-block算法从理论上彻底解决了前缀自包含的计算问题，从易理解的角度上讲，Z-block算法也要明显优于KMP算法中三人对next表构造过程的描述。拥有了模式串的Z值数组后，相应的KMP算法的next跳转表，BM算法的好后缀表的计算都将变得高效，直观。 KMP算法中next[i]与Zi(S)的对应关系我在《KMP算法详解》一文中已经介绍了next[i]的含义，对于S[i]，next[i]的意义是，如果存在k使得S[1...i-k]=S[k...i-1]且S[i-k+1]!=S[i]，那么next[i]=i-k+1。实际上对于满足条件的k，其Z值Zk(S)就满足k+Zk(S)=i，next[i]=Zk(S)+1，所以我们可以用如下方法根据模式串S的Zi(S)表填写对应的next[i]表。 规则一，从头到尾遍历Zi(S)，当遍历到元素k时，如果Zk(S)!=0，那么next[k+Zk(S)]=Zk(S)+1，如果还存在k'使得k+Zk(S)=k'+Zk'(S)那么next[k+Zk(S)]等于Zk(S)+1与Zk'(S)+1的较大者。 规则二，对于遍历Zi(S)列表之后，尚未填写的元素的next值，我们按照如下原则填充，对于元素S[i]，如果S[i]=S[1]，则其next值next[i]=0，否则next[i]=1。 根据上面的原则，我们对于《KMP算法详解》中的老例子通过Zi(S)构建next[i]的表格如下。这里对于S[8]，由于4+Z4(S)=8，7+Z7(S)=8，所以我们选择其中的较大者Z4(S)=4，令next[8]=Z4(S)+1=5。对于S[9]，由于9+Z9(S)超出了pattern数组的范围，所以我们不使用该Z值计算next跳转表。实际对于下表，除了next[8]之外，其余均是由规则二填写。相较于KMP三人给出的next表填写算法，利用Z值表填写next表固然增加了一个转换层，降低了算法效率，但是从易理解的角度讲，由Z值到next值的转换是十分有意义的。
BM算法goodsuffix[i]与Zi(S)的对应关系用Z值表填写goodsuffix表的过程，要比填写next表复杂得多。首先，BM算法使用的是后缀自包含而Z值计算的是前缀，另一方面我们还需要找到最长的与后缀相匹配的前缀的长度，来修正跳转值。这里我们分别来处理这两个问题。 对于BM算法中的模式串S，我们可以计算其逆串Sr的Z值，Zi(Sr)。例如，对于S="abcxxxabc"，Sr="cbaxxxcba"，我们可以得到Sr的Z值表如下图所示
我们可以用如下方法计算出模式串S的最大包含后缀表rpr(i)。遍历Sr的所有Z值，对于满足n-i-Zi(Sr)+1>0的i，令rpr(n-i-Zi(Sr)+1)=Zi(Sr)，对遍历之后未被填充rpr(i)值的元素，赋值0（如果S从索引0开始，则公式要改动为n-i-Zi(Sr)）。如下图，这里要注意，对于i=7，Z7(Sr)=3，但是9-7-3+1<=0，所以我们放弃这个值。
之后，我们可以计算出未修正的好后缀跳转表。对于rpr(i)=0的元素，goodsuffix'[i]=patlen+n-i，对于rpr(i)!=0的元素，goodsuffix'[i]=n-rpr(i)，其中n是模式串最末元素的索引值。如果模式串的首字符从0开始的话，n!=patlen这里要特别注意。
另外，我们还需要找到与后缀匹配的最长前缀p，用于修正goodsuffix'的跳转步数。p值在构建Zi(Sr)的时候可以得到，对于Sr中的元素Sr[i]，如果有i+Zi(Sr)-1=n，那么p=Zi(Sr)，如果有多个i满足该条件，则p等于其中的最大者。上例中对于Sr="cbaxxxcba"，我们有7+Z7(Sr)-1=9，所以p=Z7(Sr)=3。在修正goodsuffix'的跳转步数时，我们对于n-i>=p的元素goodsuffix'值统一减去p即可得到最终的goodsuffix值。如下图
上面虽然列出了4个步骤，但是在实际计算BM的好后缀跳转表的过程中，除了Zi(Sr)需要单独计算之外，其余三个步骤，可以一次完成。 在使用Z值表计算KMP算法或者是BM算法的跳转表的过程中，模式串起始索引要特别注意，如果S[0...n]从0开始，则要对一些地方做修正。因为如果模式串从索引0的位置开始，其最末元素n!=patlen，所以在计算过程中，哪里用的是模式串的长度，哪里用的是模式串最末元素的索引，要格外留心。 |
|
|
