大数据

当前位置:首页 > 大数据

《算法导论》第三十二章 续3

32.4 Knuth-Morris -Pratt算法

现在来介绍一种由Knuth、Morris 和Pratt 三人设计的线性时间字符串匹配算法。这个算法无需计算转移函数δ,匹配时间为Θ(n),只用到辅助函数π,它在Θ(m)时间内根据模式预先计算出来,并且存储在数组π[1..m]中。数组π使得我们可以按需要“即时”有效地计算(在摊还意义上来说)转移函数δ。粗略地说,对任意状态q=0, 1,...,m和任意字符a∈QQ截图20220629085103.jpg,π[q]的值包含了与a无关但在计算δ(q,a)时需要的信息。由于数组π只有m个元素,而δ有Θ(m|QQ截图20220629085103.jpg|)个值,所以通过预先计算π而不是δ,可以使计算时间减少一个QQ截图20220629085103.jpg因子。

关于模式的前缀函数

模式的前缀函数π包含模式与其自身的偏移进行匹配的信息。这些信息可用于在朴素的字符串匹配算法中避免对无用偏移进行检测,也可以避免在字符串匹配自动机中,对整个转移函数δ的预先计算。

考察一下朴素字符串匹配算法的操作过程。图32-10(a)展示了一个针对文本T模板的一个特定偏移s,该模板包含模式P= ababaca。在这个例子中,q=5个字符已经匹配成功,但模式的第6个字符不能与相应的文本字符匹配。q个字符已经匹配成功的信息确定了相应的文本字符。已知的这q个文本字符使我们能够立即确定某些偏移是无效的。在该图的实例中,偏移s+1必然是无效的,因为模式的第一个字符(a)将与文本字符匹配,该文本字符已知不能和模式的第一个字符匹配,但是却能与模式的第二个字符(b)匹配。在图32 -10(b)所示的偏移s'=s+2使模式前面三个字符和相应三个文本字符对齐后必定会匹配。在一般情况下,知道下列问题的答案将是很有用的:

QQ截图20220629094803.jpg

图32-10  前缀函数 π。(a)模式P= ababaca和文本T平行摆放,使得前q=5个字符匹配。匹配的字符被打上阴影且用垂直线连接。(b)根据5个匹配字符的已有信息,可以推知s+1的偏移是无效的,但是s'=s+2的偏移与我们对文本的了解一致,因而可能是有效的。(c)推导中使用的有用信息可以通过模式自身的比较来预计算。这里,我们发现P3是P的最长前缀同时也是P5的一个真后缀。这些信息被预先计算出来,并用数组π来表示,即π[5]=3。在偏移s有q个字符成功匹配,则下一个可能有效的偏移为s'=s+(q- π[q]),正如在(b)中所示

假设模式字符P[1..q]与文本字符T[s+1..s+q]匹配,s' 是最小的偏移量,s'>s,那么对某些k<q,满足

QQ截图20220629095123.jpg

的最小偏移s'>s是多少,其中s'+k= s+q?

换句话说,已知PqQQ截图20220628172020.jpgTs+q,我们希望Pq的最长真前缀Pk也是Ts+q的后缀。(由于s'+k=s+q,如果给出s和q,那么找到最小偏移s'等价于找到最长前缀的长度k。)我们把在P前缀长度范围内的差值q-k加入到偏移s中,用于找到新的偏移s',使得s'=s+(q-k)。在最好情况下,k=0,因此s'=s+q,并且立刻能得出偏移s十1,s+2,...,s十q-1。在任何情况下,对于新的偏移s',无需把P的前k个字符与T中相应的字符进行比较,因为等式(32.6)已经保证它们肯定匹配。

可以用模式与其自身进行比较来预先计算出这些必要的信息,如图32-10(c)所示。由于T[s'+1..s' +k]是文本中已经知道的部分,所以它是字符串Pq的一个后缀。可以把等式(32.6)解释为要求满足PkQQ截图20220628172020.jpgPq的最大的k<q。于是,这个新的偏移s'=s+(q- k)就是下一个可能的有效偏移。我们将会发现,对每一个q值,把已匹配字符数目k存储在新的偏移s' (而不是s'-s)中是比较方便的。

下面是预计算过程的形式化说明。已知一个模式P[1..m],模式P的前缀函数是函数π:{1,2,...,m}→{0, 1,...,m-1},满足

QQ截图20220629100957.jpg

即π[q]是Pq的真后缀P的最长前缀长度。又例如,图32-11(a)中给出了关于模式ababaca的完整前缀函数π。

QQ截图20220629101059.jpg

图32-11对模式 P=ababaca和q=5应用引理32. 5的描述。(a)给定模式的π函数。因为π[5]=3, π[3]=1和π[1]=0,通过迭代π得到π*[5]={3, 1, 0}。(b)将包含模式P的模板向右移动,并注意何时P的某前缀Pk与P5的某真后缀匹配,在k=3, 1和0时匹配。图中第一行给出了P,点垂直线就画在P5后。相继的几行显示所有P的偏移,使得P的某前缀Pk与P5的某后缀匹配。成功匹配的字符被打上了阴影。垂直线连接了并列的匹配字符。因此,{k:k<q且PkQQ截图20220629101344.jpgP5}={3,1,0}。引理32.5要求对所有q有π*[q]={k:k<q且PkQQ截图20220629101344.jpgPq}

下面给出的Knuth-Morris-Pratt匹配算法的伪代码就是KMP-MATCHER过程。我们将看到,其大部分都是在模仿FINITE-AUTOMATON-MATCHER。KMP-MATCHER调用了一个辅助程序COMPUTE-PREFIX-FUNCTION来计算π。

QQ截图20220629101528.jpg

QQ截图20220629101548.jpg

这两个程序有很多相似之处,因为它们都是一个字符串针对模式P的匹配:KMP-MATCHER是文本T针对模式P的匹配,COMPUTE-PREFIX-FUNCTION是模式P针对自己的匹配。

下面先来分析这两个过程的运行时间,对其正确性的证明要复杂一些。

运行时间分析

运用摊还分析的聚合方法(参见17.1节)进行分析,过程COMPUTE-PREFIX-FUNCTION的运行时间为Θ(m)。唯一微妙的部分 是表明第6~7行的while循环总共执行时间为O(m)。下面将说明它至多进行了m-1次迭代。我们从观察k的值开始,第一,在第4行,k初始值为0,并且增加k的唯一方法是通过第9行的递增操作,该操作在第5~10行的for循环迭代中每次最

多执行一次。因此,k总共至多增加m-1次。第二,因为进行for 循环时k<q,并且在for 循环体的每次迭代过程中,q的值都增加,所以k<q总成立。因此,第3行和第10行的赋值确保了π[q]<q对所有的q=1,2,...,m都成立,这意味着每次while循环迭代时k的值都递减。第三,k永远不可能为负值。综合考虑这些因素,我们会发现,k的递减来自于while循环,它由k在所有for循环迭代中的增长所限定,k总共下降m-1。因此,while 循环最多迭代m-1次,并且COMPUTE-PREFIX-FUNCTION的运行时间为Θ(m)。

练习32.4-4要求读者通过运用类似的聚合分析,证明KMP-MATCHER的匹配时间为Θ(n)。

与FINITE-AUTOMATON-MATCHER相比,通过运用π而不是δ,可将对模式进行预处理的时间由O(m|QQ截图20220629085103.jpg| )减为Θ(m),同时保持实际的匹配时间界为Θ(n)。

前缀函数计算的正确性

我们稍后就会看到,前缀函数π帮助我们在字符匹配自动机中模拟转移函数δ,但是首先我们需要证明COMPUTE-PREFIX-FUNCTION确实能够准确计算出前缀函数。为此,我们将需要找到所有的前缀Pk,也就是给定前缀Pq的真后缀。π[q]的值给了我们最长的前缀,正如在图32-11中所描述的,下面的引理说明通过对前缀函数π进行迭代,就能够列举出Pq的真后缀的所有前缀Pk。设

QQ截图20220629102224.jpg

其中π(i)[q]是按函数迭代的概念来定义的,满足π0[q]=q,并且对i≥1,π(i)[q]=π[π(i)[g]],当达到πt[q]=0时,π*[q]中的序列终止。

引理32. 5(前缀函数迭代引理)设P是长度为m的模式,其前缀函数为π,对q=1, 2, ... m,有π*[q]={k: k<q且PJPq}。

证明  首先证明 π*[q]QQ截图20220629103008.jpg{k:k<q且PkQQ截图20220628172020.jpgPq},或者等价地,

QQ截图20220629103111.jpg

若i∈π*[q],则对某个u>0,有i=π(u)[q]。通过对u进行归纳来证明式(32.7)成立。对u=1,有i=π[q],因为根据π的定义有i<q且Pπ(q)QQ截图20220628172020.jpgPq,所以此断言成立。利用关系π[i]<i和Pπ[i]QQ截图20220628172020.jpgPi,以及<和QQ截图20220628172020.jpg的传递性,就可以证明对所有i∈π*[q],有π*[q]QQ截图20220629103008.jpg{k:k<q且PkQQ截图20220628172020.jpgPq}。

下面用反证法来证明{k:k<q且PkQQ截图20220628172020.jpgPq}QQ截图20220629103008.jpgπ*[q],假定集合{k:k<q且PkQQ截图20220628172020.jpgPq}-π*[q]是非空的,且设j是该集合中的最大值。因为π[q]是{k:k<qPkQQ截图20220628172020.jpgPq}中的最大值且π[q]∈π*[q],所以必定有j<π[q]。因而可以设j'表示π*[q]中比j大的最小整数。(如果π° [q]中没有其他数比j大,则可以选取j'=π[q]。)我们有PjQQ截图20220628172020.jpgPq,因为j∈{k:k<q且PkQQ截图20220628172020.jpgPq},另外因为

j'∈π*[q]和式(32.7),有Pj'QQ截图20220628172020.jpgPq。因此,根据引理32.1, PjQQ截图20220628172020.jpgPj'而且根据此性质,j是小于j'的最大值。因而必定有π[j']=j,并且因为j'∈π*[q],同样必定有j∈π*[q]。这就产生了矛盾,所以引理得证。

算法COMPUTE-PREFIX-FUNCTION根据q=1,2,...,m的顺序计算π[q]的值。COMPUTE-PRFFIX-FUNCTION的第3行置π[1]=0当然是正确的,因为对所有的q,π[q]<q。下面的引理及其推论将用于证明对q>1,COMPUTE-PREFIX-FUNCTION能正确地计算出π[q]。

引理32.6  设P是长度为m的模式,π是P的前缀函数。对q=1,2,...,m,如果π[q]>0,则π[q]-1∈π*[q-1]。

证明  如果r=π[q]>0,那么r<q且PrQQ截图20220628172020.jpgPq;因此r-1<q-1且Pr-1QQ截图20220628172020.jpgPq-1(把Pr和Pq中的最后一个字符去掉,因为r>0,所以这可以做到)。因此,根据引理32.5,r-1∈π*[q-1]。因此π[q]-1=r-1∈π*[q-1]。

对q=2,3,...,m,定义子集Eq-1QQ截图20220629103008.jpgπ*[q-1]为:

QQ截图20220629105501.jpg

集合Eq-1由满足PkQQ截图20220628172020.jpgPq-1和P[k+1]= P[q]的值k<q-1组成,因为P[k+1]= P[q],所以有Pk+1QQ截图20220628172020.jpgPq。因此,Eq-1是由 k∈π*[q- 1]中的值组成,可以将Pk扩展到Pk+1并得到Pq真后缀。

推论32.7  设P是长度为m的模式,π是P的前缀函数,对q=2,3,...,m,

QQ截图20220629105900.jpg

证明  如果 Eq-1为空,则没有用于扩展Pk到Pk+1及得到Pq真后缀的k∈π*[q-1](包括k=0)。因此π[q]=0。

如果Eq-1为非空,那么对每一个k∈Eq-1,有k+1<q且Pk+1QQ截图20220628172020.jpg-Pq。因此,根据π[q]的定义,

QQ截图20220629110330.jpg

注意到π[q]>0。设r=π[q]-1,那么r+1=π[q],因此Pr+1QQ截图20220628172020.jpgPq。因为r+1>0,所以有P[r+1]=P[q]。而且根据引理32.6,有r∈π*[q-1]。因此,r∈Eq-1,所以r≤max{k∈Eq-1 }或等价地,

QQ截图20220629110555.jpg

联合等式(32.8)和式(32.9)即可完成证明。

现在来完成对COMPUTE-PREFIX-FUNCTION计算的π的正确性证明。在过程COMPUTE-PREFIX-FUNCTION中第5~10行for循环的每次迭代开始时,k=π[q-1]。当第一次进入循环时,该条件由第3行和第4行实现,并且因为第10行的执行,使得该条件在下面的每次选代中均保持成立。第6~9行调整k的值,使它变为现在的π[q]的正确值。第6~7行的while循环搜索所有k∈π*[q-1]的值,直至找到一个k值,使得P[k+1]=P[q];此时,k是集合Eq-1中的最大值,根据推论32.7,可以置π[q]为k+1。如果找不到这样的值,则在第8行k=0。如果P[1]= P[q],那么应该将k和π[q]都设置为1;否则,只需将π[q]置为0而不管k。第8~10行完成在任意条件下k和π[q]的设置。这样就完成了对COMPUTE-PREFIX-FUNCTION正确性的证明。

KMP算法的正确性

过程KMP-MATCHER可以看做是过程FINITE-AUTOMATON-MATCHER的一次重新实现,但是却用到了前缀函数π来计算状态转换。特别地,我们将证明在KMP-MATCHER和FINITE-AUTOMATON-MATCHER的for循环的第i次迭代时,当检测m的等效性时,两个过程的状态q的值相同(KMP-MATCHER在第10行,FINITE-AUTOMATON-MATCHER在第5

行)。一旦证明了KMP-MATCHER模拟了FINITE-AUTOMATON-MATCHER的操作过程,自然也就可以由FINITE-AUTOMATON-MATCHER的正确性推出KMP-MATCHER也是正确的(但是下面将看到为什么KMP-MATCHER中的第12行代码是必需的)。

在我们正式证明KMP-MATCHER模仿FINITE-AUTOMATON-MATCHER之前,让我们来理解前缀函数π如何代替转移函数δ。回顾一下,当字符串匹配自动机处在状态q时,它扫描到字符a= T[i],然后移动到一个新的状态δ(q,a)。如果a= P[q+1],那么a将持续对模式进行匹配,δ(q, a)=q+1;否则,a≠P[q+1],那么a就终止了对模式的匹配,并且0≤δ(q,a)≤q。在第一种情况下,当a持续匹配时,KMP-MATCHER移动到状态q+1而无需参考π函数:在第6行的while循环检测第一次报错,在第δ行检测结果是真,并且在第9行q增加。

当a不能持续进行模式匹配时,π函数开始起作用,因此新的状态δ(q,a)要么是q, 要么是沿着自动机移动的q的左边状态。在KMP-MATCHER中第6~7行的while循环迭代通过状态π*[q],要么停在一个q'状态,使得a和P[q'+1]匹配,要么是q'已经走完变为了0。如果a和P[q'+1]匹配,那么第9行就进入新的状态q' +1,这应该等价于准确模拟δ(q,a)的工作。换句话说,新状态δ(q, a)要么处于状态0,要么处于比某些在π*[q]中更高的状态。

让我们来考虑图32-7和图32-11中的例子,其中模式为P= ababaca。假设自动机处在q=5的状态;这些在π*[5]中的状态是以3, 1和0的顺序递减的。如果下一个扫描到的字符是c,那么很容易看到自动机移动到状态δ(5,c)=6,在KMP-MATCHER和FINITE-AUTOMATON-MATCHER中都是如此。现在假设下一个扫描到的字符是b,那么自动机会移动到δ(5,b)=4状态。在KMP-MATCHER中每次退出while 循环都运行第7行一次,并且到达状态q'=π[5]=3。由于P[q'+1]=P[4]=b,第8行检测结果是真,并且KMP-MATCHER移动到新的状态q'+1=4=δ(5,b)。最后,假设下一个扫描到的字符是a,那么自动机就自动移动到状态δ(5,a)=1。在第6行执行前三次检测,结果是真。第一次我们发现P[6]= =c≠a并且KMP-MATCHER移动到状态π[5]=3(处在π*[5]中的第一个状态),第二次我们发现P[4]= b≠a并且移动到状态π[3]=1(处在π*[5]中的第二个状态),第三次我们发现P[2]= b≠a并且移动到状态π[1]=0(处在π*[5]中的最后一个状态)。一旦到达状态q'=0,while 循环就退出。现在,在第8行发现P[q'+1]=P[1]=a,并且在第9行移动自动机到新的状态q'+1=1=δ(5,a)。

因此,我们了解到KMPMATCHER通过以递减的顺序在状态π*[q]中迭代循环,在某些状态q'停止,然后可能移动到状态q'+1。尽管似乎在模拟计算δ(q,a)时有很多工作要做,但是从渐近意义上看,KMP-MATCHER并不比FINITE-AUTOMATON-MATCHER慢。

我们现在准备正式证明Knuth-Morris-Pratt算法的正确性。根据定理32.4,在每次运行FINITE- AUTOMATON-MATCHER的第4行时得到q=σ(Ti)。因此,它足以证明for循环在KMP-MATCHER中有同样的特性。通过对循环迭代次数进行归纳来证明。首先,当它们第一次进入各自的for循环时,程序都是预设q=0。考虑在KMP-MATCHER中对i迭代的for 循环,假设q'是该循环迭代的初始状态。通过归纳假设,我们可以得到q'=σ(Ti-1)。需要证明在第10行也有q=σ(Ti)。(我们将又一次分开处理第12行。)

当考虑到字符T[i]时,P的最长前缀也是Ti的一个后缀,要么是Pq'+1(如果P[q'+1]=T[i]),要么是Pq'的某个前缀(这并不一定为真前缀,并且可能为空)。我们分别考虑以下三种情况:σ(Ti)=0,σ(Ti)=q'+1和0<σ(Ti)≤q'。

  • 如果σ(Ti)=0, 那么P0=ε是P的唯一前缀,也是Ti的一个后缀。第6~7行的while循环迭代π*[q']中的值,尽管PqQQ截图20220628172020.jpgTi-1对每个q∈π*[q']都成立,但是循环绝不会找到一个使得P[q+1]=T[i]的q。当q=0时,循环结束,并且第9行自然就不执行了。因此,在第10行q=0,使得q=σ(Ti)。

  • 如果σ(Ti)=q'+1,那么P[q'+1]=T[i],并且第一次检测第6行的while循环失败。执行第9行,q增加,使得q=q'+1=σ(Ti)。

  • 如果0<σ(Ti)≤q',那么第6~7行的while至少循环迭代一次,对于每一个值q∈π*[q],以递减顺序进行检测,直到q<q'时停止。因此,Pq是Pq'满足P[q+1]= T[i]的最长前缀,使得当while循环终止时,q+1=σ(Pq'T[i])。 由于q'=σ(Ti-1),由引理32.3可以导出σ(Ti-1T[i])=σ(Pq'T[i])。因此有

QQ截图20220629113112.jpg

当while循环终止时,在第9行的q增加之后,得到q=a(Ti)。

在KMP-MATCHER中,之所以一定要有第12行代码,是为了避免在找出P的一次出现后,第6行中可能出现P[m+1]的情形。(由练习32.4-8的提示,即对任意a∈QQ截图20220629085103.jpgδ(m, a)=δ(π[m], a),或者等价地,δ(Pa)= δ(Pπ[m]a),可以推得在下一次执行第6行代码时,q= a(Ti-1)依然保持有效。)关于Knuth-Morris-Pratt算法的正确性证明,其余的部分可以从FINITE-

AUTOMATON-MATCHER的正确性推得,因为现在可以看出KMP-MATCHER模拟了FINITE-AUTOMATON-MATCHER的操作过程。


练习

32.4-1  计算对应于模式ababbabbabbababbabb的前缀函数π。

32.4-2  给出关于q的函数π*[q]的规模的上界。举例说明所给出的上界是严格的。

32.4-3  试说明如何通过检查字符串PT(由P和T连结形成的长度为m+n的字符串)的π函数来确定模式P在文本T中的出现位置。

32.4-4  用聚合分析方法证明KMP-MATCHER的运行时间是Θ(n)。

32.4-5  用势函数证明KMP-MATCHER的运行时间是Θ(n)。

32.4-6  试说明如何通过以下方式对过程KMP-MATCHER进行改进:把第7行(不是第12行中)出现的π替换为π',其中对于q=1,2,...,m-1,π'递归定义如下:

QQ截图20220629113608.jpg

试说明修改后的算法为什么是正确的,并说明在何种意义上,这一修改是对原算法的改进。

32.4-7  写出一个线性时间的算法,以确定文本T是否是另一个字符串T'的循环旋转。例如arc和car是彼此的循环旋转。

*32.4-8  给出一个有效算法,计算出相应于某给定模式P的字符 串匹配自动机的转移函数δ。 所给出的算法的运行时间应该是O(m|QQ截图20220629085103.jpg|)。(提示:证明如果q=m或P[q+1]≠a,则δ(q,a)=δ(π[q], a)。)


思考题

32-1   (基于重复因子的字符串匹配) 设yi表示字符串y与其自身首尾相接i次所得的结果。例如(ab)3 = ababab。如果对某个字符串y∈QQ截图20220629085103.jpg*和某个r>0有x=yr,则称字符串x∈QQ截图20220629085103.jpg*具有重复因子r。设ρ(x)表示使得x具有重复因子r的最大值。

a.写出一有效算法以计算出ρ(Pi)(i=1,2,...,m),算法的输入为模式P[1..m]。算法的运行时间是多少?

b.对任何模式P[1..m],设ρ*(P)定义为QQ截图20220629114209.jpg。证明:如果从长度为m的所有二进制字符串所组成的集合中随机地选择模式P,则ρ* (P)的期望值是O(1)。

c.论证下列字符串匹配算法可以在O(ρ*(P)n+ m)的时间内正确地找出模式P在文本T[1. . n]中的所有出现位置。

QQ截图20220629114402.jpg

该算法是Galil和Seiferas提出的。通过对这些设计思想进行大量扩充,他们得到了一个线性时间的字符串匹配算法,该算法除了P和T所要求的存储空间外,仅需O(1)的存储空间。


相关内容

文章评论

表情

共 0 条评论,查看全部
  • 这篇文章还没有收到评论,赶紧来抢沙发吧~