大数据

当前位置:首页 > 大数据

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

32.3 利用有限自动机进行字符串匹配

很多字符串匹配算法都要建立一个有限自动机,它是一个处理信息的简单机器,通过对文本字符串T进行扫描,找出模式P的所有出现位置。本节将介绍一种建立这样自动机的方法。

这些字符串匹配的自动机都非常有效:它们只对每个文本字符检查一次,并且检查每个文本字符时所用的时间为常数。因此,在模式预处理完成并建立好自动机后进行匹配所需要的时间为Θ(n)。但是,如果习很大,建立自动机所需的时间也可能很多。32.4节将描述解决这个问题的一种巧妙方法。

本节首先定义有限自动机。然后,我们要考察一种特殊的字符串匹配自动机,并展示如何利用它找出一个模式在文本中的出现位置。最后,我们将说明对一个给定的输入模式,如何构造相应的字符串匹配自动机。

有限自动机

如图32-6所示,一个有限自动机M是一个5元组(Q,q0,A,QQ截图20220628141542.jpg,δ),其中:

  • Q是状态的有限集合。

  • q0∈Q是初始状态。

  • AQQ截图20220628143409.jpgQ是一个特殊的接受状态集合。

  • QQ截图20220628141542.jpg是有限输入字母表。

  • δ是一个从Q×QQ截图20220628141542.jpg到Q的函数,称为M的转移函数。

有限自动机开始于状态q0,每次读入输入字符串的一个字符。如果有限自动机在状态q时读入了字符a,则它从状态q变为状态δ(q, a)(进行了一次转移)。每当其当前状态q属于A时,就说自动机M接受了迄今为止所读入的字符串。没有被接受的输入称为被拒绝的输入。

QQ截图20220628143630.jpg

图32-6 一个拥有状态集Q={0, 1}的简单两状态自动机,开始状态q0=0,并且输入字母表QQ截图20220628141542.jpg={a, b}。(a)用表格表示的转移函数δ。(b)一个等价的状态转换图。状态1(被涂黑了)是唯一的接受状态。有向边代表着转换。例如,从状态1到状态0的标有b的边表示δ(1,b)=0。这个自动机接受那些以奇数个a结尾的字符串。更确切地说,一个字符串x被接受,当且仅当x=yz,其中y=ε或者y以一个b结尾,并且z=ak,这里k是奇数。例如,对于输入abaaa,包括初始状态,这个自动机输入状态序列为<0,1,0,1,0,1>,因而它接受这个输入。如果输入是abbaa, 自动机输入状态序列为<0,1,0,0,1,0>,因而它拒绝这个输入

有限自动机M引入一个函数Φ,称为终态函数,它是从QQ截图20220628141542.jpg*到Q的函数,满足Φ(w)是M在扫描字符串w后终止时的状态。因此,当且仅当Φ(w)∈A时,M接受字符串w。我们可以用转移函数递归定义Φ

QQ截图20220628144305.jpg

字符串匹配自动机

对于一个给定的模式P,我们可以在预处理阶段构造出一个字符串匹配自动机,根据模式构造出相应的自动机后,再利用它来搜寻文本字符串。图32-7说明了用于匹配模式P= ababaca的有限自动机的构造过程。从现在开始,假定P是一个已知的固定模式。为了使说明简洁,在下面的符号中将不指出对P的依赖关系。

为了详细说明与给定模式P[1.. m]对应的字符串匹配自动机,首先定义一个辅助函数σ,称为对应P的后缀函数。函数σ是一个从习到{0,1,..., m}上的映射,满足σ(x)是x的后缀P的最长前缀的长度:

QQ截图20220628171452.jpg

因为空字符串P0=ε是每一个字符串的后缀,所以后缀函数σ是良定义的。例如,对模式P= ab,有σ(ε)=0,σ(caca)=1,o(ccab)=2。 对于一个长度为m的模式P,σ(x)=m当且仅当PQQ截图20220628172020.jpgx。根据后缀函数的定义:如果xQQ截图20220628172020.jpgy,则σ(x)≤a(y)。

给定模式P[1..m],其相应的字符串匹配自动机定义如下:

  • 状态集合Q为{0,1,...,m}。开始状态q0是0状态,并且只有状态m是唯一被接受的状态。

  • 对任意的状态q和字符a,转移函数δ定义如下:

QQ截图20220628172330.jpg

我们定义δ(q,a)=σ(Pqa), 目的是记录已得到的与模式P匹配的文本字符串T的最长前缀。考虑最近一次扫描T的字符。为了使T的一个子串(以T[i]结尾的子串)能够和P的某些前缀Pj匹配,前缀Pj必须是Ti的一个后缀。假设q=Φ(Ti),那么在读完Ti之后,自动机处在状态q。设计转移函数δ,使用状态数q表示P的前缀和Ti后缀的最长匹配长度。也就是说,在处于状态q时,PqQQ截图20220628172020.jpgTi并且q=σ(Ti)。(每当q=m时,所有P的m个字符都和Ti的一个后缀匹配,从而得到一个匹配。)因此,由于Φ(Ti)和σ(Ti)都和q相等,我们将会看到(在后续的定理32.4中)自动机保持下列等式成立:

QQ截图20220629084355.jpg

如果自动机处在状态q并且读人下一个字符T[i+1]=a,那么我们希望这个转换能够指向Tia的后缀状态,它对应着P的最长前缀,并且这个状态是σ(Tia)。由于Pq是P的最长前缀,也就是Ti的一个后缀,那么P的最长前缀也就是Tia的一个后缀,不仅表示为σ(Tia),也可表示为σ(Pqa)。(引理32.3证明了σ(Tia)=σ(Pqa)。)因此,当自动机处在状态q时,我们希望这个在字

符a上的转移函数能使自动机转移到状态σ(Pqa)。

QQ截图20220629084740.jpg

QQ截图20220629084801.jpg

图32-7 (a)一个字符 串匹配自动机的状态转换图,它可以接受所有以字符串ababaca结尾的字符串。状态0是初始状态,状态7(被涂黑)是仅有的接受状态。从状态i到状态j,标有a的有向边表示δ(i,a)=j。形成自动机“脊”的右向边,在图中加重了颜色,对应着模式和输入字符串之间的成功匹配。除了从状态7到状态1和2的边外,向左指的边对应着失败的匹配。一些表示匹配失败的边并没有标记出来;通常,如果状态i对某个a∈QQ截图20220629085103.jpg没有对应a的出边,则δ(i, a)=0。(b)对应的转移函数δ和模式字符串P = ababaca。模式和输入之间的成功匹配被标上了阴影。(c) 自动机在文本T= abababacaba上的操作。在处理了前缀Ti之后,在每个文本字符T[i]下面,给出了它在自动机内的状态Φ(Ti)。自动机找到该模式的一个出现,以位置9结尾

考虑以下两种情况。第一种情况是,a=P[q+1],使得字符a继续匹配模式。在这种情况下,由于δ(q, a)=q+1,转换沿着自动机的“主线”(图32-7中的粗边)继续进行。第二种情况,a≠P[q+1],使得字符a不能继续匹配模式。这时我们必须找到一个更小的子串,它是P的前缀同时也是Ti的后缀。因为当创建字符串匹配自动机时,预处理匹配模式和自己,转移函数很快就得出最长的这样的较小P前缀。

让我们看一个例子。图32-7的字符串匹配自动机有δ(5,c)=6,说明其是第一种情况,匹配继续进行。为了说明第二种情况,观察图32-7中的自动机,有δ(5, b)=4。我们选择这个转换的原因是如果自动机在q=5状态时读到一个b,那么Pqb= ababab,并且P的最长前缀也是ababab的后缀P4= abab。

为了清楚说明字符串匹配自动机的操作过程,我们给出一个简单而有效的程序,用来模拟这样一个自动机(用它的转移函数δ来表示),在输入文本T[1..n]中,寻找长度为m的模式P的出现位置。如同对于m长模式的任意字符串匹配自动机,状态集Q为{0,1,...,m},初始状态为0,唯一的接受状态是m。

QQ截图20220629085832.jpg

从FINITE AUTOMATON-MATCHER的简单循环结构可以看出,对于一个长度为n的文本字符串,它的匹配时间为Θ(n)。但是,这一匹配时间没有包括计算转移函数δ所需要的预处理时间。我们将在证明FINITE-AUTOMATON-MATCHER的正确性以后,再来讨论这一问题。

考察自动机在输入文本T[1..n]上进行的操作。下面将证明自动机扫过字符T[i]后,其状态为σ(Ti)。因为当且仅当PQQ截图20220628172020.jpgTi,o(Ti)=m。所以当且仅当模式P被扫描过之后自动机处于接受状态m。为了证明这个结论,要用到下面两条关于后缀函数σ的引理。

引理32. 2(后缀函数不等式)对任意字符串 x 和字符a,σ(xa)≤σ(x)+1。

证明  参照图 32-8,设r=σ(xa)。如果r=0,则根据σ(x)非负,σ(xa)=r≤σ(x)+1显然成立。于是现在假定r>0,根据σ的定义。有PrQQ截图20220628172020.jpgxa。所以,把a从Pr与xa的末尾去掉后,得到Pr-1QQ截图20220628172020.jpgx。因此,r-1≤σ(x), 因为σ(x)是满足PkQQ截图20220628172020.jpgx的最大的k值,所以σ(xa)=r≤σ(x)+1。

QQ截图20220629090706.jpg

图32-8描述了 引理32. 2的证明。图中显示≤σ(x)+1,其中r=σ(xa)

引理32. 3(后缀函数递归引理)对任意 x和字符a,若q=σ(x),则σ(xa)=a(P, a)。

证明  根据σ的定义, 有PqQQ截图20220628172020.jpgx。如图32-9所示,有PqaQQ截图20220628172020.jpgxa。若设r=σ(xa),则PrQQ截图20220628172020.jpgxa,并由引理32.2知,r≤q+1。因此可得|Pr| =r≤q+1=|Pqa|。因为PqaQQ截图20220628172020.jpgxa和PrQQ截图20220628172020.jpgxa并且|Pr|≤|Pqa|,所以由引理32.1可知PrQQ截图20220628172020.jpgPqa。因此可得r≤σ(Pqa),即σ(xa)≤σ(Pqa)。但由于PqaQQ截图20220628172020.jpgxa,所以有σ(Pqa)≤σ(xa),从而证明σ(Pqa)=σ(xa)。

现在我们就可以来证明用于描述字符串匹配自动机在给定输入文本上操作过程的主要定理了。 如上所述, 这个定理说明了自动机在每一步中仅仅记录所读入字符串后缀的最长前缀。 换句话说,自动机保持着不变式(32.5)。

QQ截图20220629092004.jpg

图32-9 描述了引理32.3的证明。图中显示r=σ(Pqa),其中q=σ(x)和r=a(xa)

定理32.4  如果Φ是字符串匹配自动机关于给定模式P的终态函数,T[1..n]是自动机的输入文本,则对i=0,1, ..., n, Φ(Ti)=σ(Ti)。

证明  对i进行归纳。对i=0,因为T0=ε,定理显然成立。因此Φ(T0)=0=σ(T0)。

现在假设Φ(Ti)=σ(Ti),并证明Φ(Ti+1)=σ(Ti+1)。设q表示Φ(Ti),a表示T[i+1],那么,

QQ截图20220629092758.jpg

根据定理32.4,如果自动机在第4行进入状态q,则q是满足PqQQ截图20220628172020.jpgTi的最大值。因此,在第5行有q=m,当且仅当自动机刚刚扫描了模式P在文本中的一次出现位置。于是可以得出结论,FINITE-AUTOMATON-MATCHER可以正确地运行。

计算转移函数

下面的过程根据一个给定模式P[1. . m ]来计算转移函数δ。

QQ截图20220629093031.jpg

这个过程根据在式(32.4)中的定义直接计算δ(q, a),在从第2行和第3行开始的嵌套循环中,要考察所有的状态q和字符a。第4~8行把δ(q, a)置为满足PkQQ截图20220628172020.jpgPqa的最大的k。代码从k的最大可能值min(m, q+1)开始。随着过程的执行,k逐渐递减,直至PkQQ截图20220628172020.jpgPqa,这种情况必然会发生,因为P0=ε是每个字符串的一个后缀。

COMPUTE- TRANSITION-FUNCTION的运行时间为O(m3|QQ截图20220629085103.jpg|),因为外循环提供了一个因子m|QQ截图20220629085103.jpg|,内层的repeat循环至多执行m+l次,而第7行的测试PkQQ截图20220628172020.jpgPqa需要比较m个字符。还存在速度更快的程序。如果能够利用精心计算出的模式P的有关信息(见练习32. 4-8),则根据P计算出δ所需要的时间可以改进为O(m|QQ截图20220629085103.jpg|)。如果用改进后的过程来计算δ,则对字

母表QQ截图20220629085103.jpg,我们能够找出长度为m的模式在长度为n的文本中的所有出现位置,这需要O(m|QQ截图20220629085103.jpg|)的预处理时间和Θ(n)的匹配时间。


练习

32.3-1  对模式|P= aabab构造出相应的字符串匹配自动机,并说明它在文本字符串T=aababaabaababaab上的操作过程。

32.3-2  对字母表QQ截图20220629085103.jpg={a, b},画出与模式ababbabbababbababbabb对应的字符串匹配自动机的状态转换图。

32.3-3  如果由 PkQQ截图20220628172020.jpgPq导出k=0或k=q,则称模式P是不可重叠的。试描述与不可重叠模式相应的字符串匹配自动机的状态转换图。

*32.3-4  已知两个模式P 和P',试描述如何构造一个有限自动机,使之能确定其中任意一个模式的所有出现位置。尽量使自动机的状态数最小。

32.3-5  给定一个包括间隔字符(参见练习32. 1-4)的模式P,说明如何构造一个有限自动机,使其在O(n)的时间内找出P在文本T中的一次出现位置,其中n=|T|。


相关内容

文章评论

表情

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