大数据

当前位置:首页 > 大数据

《算法导论》第三十二章

第三十二章  字符串匹配

在编辑文本程序过程中,我们经常需要在文本中找到某个模式的所有出现位置。典型情况是,一段正在被编辑的文本构成一个文件,而所要搜寻的模式是用户正在输入的特定的关键字。

有效地解决这个问题的算法叫做字符串匹配算法,该算法能够极大提高编辑文本程序时的响应效率。在其他很多应用中,字符串匹配算法用于在DNA序列中搜寻特定的序列。在网络搜索引擎中也需要用这种方法来找到所要查询的网页地址。

字符串匹配问题的形式化定义如下:假设文本是一个长度为n的数组T[1..n],而模式是一个长度为m的数组P[1..m],其中m≤n,进一步假设P和T的元素都是来自一个有限字母集QQ截图20220628110743.jpg的字符。例如,QQ截图20220628110743.jpg={0, 1}或者QQ截图20220628110743.jpg={a,b,..., z}。字符数组P和T通常称为字符串。

如图32-1所示,如果0≤s≤n-m,并且T[s+1..s+m]= P[1..m](即如果T[s+j]=P[j],其中1≤j≤m),那么称模式P在文本T中出现,且偏移为s(或者等价地,模式P在文本T中出现的位置是以s+1开始的)。如果P在T中以偏移s出现,那么称s是有效偏移;否则,称它为无效偏移。字符串匹配问题就是找到所有的有效偏移,使得在该有效偏移下,所给的模式P出现在给定的文本T中。

QQ截图20220628111002.jpg

图32-1 字符串匹配问题的一个例子,在该例子中,我们试图找到模式P= abaa在文本T=abcabaabcabac中所有出现的位置。模式只在这个文本中出现一次,在偏移s=3处,因此我们称s为有效偏移。用竖线连接了每一个模式中的字符和与其对应的文本中的字符,所有匹配的字符都被涂上了阴影

除了在32.1节将要复习的朴素算法外,本章中的每个字符串匹配算法都基于模式进行了预处理,然后找到所有有效偏移;我们称第二步为“匹配”。图32-2给出了本章中每个算法的预处理时间和匹配时间。每个算法的总运行时间是预处理时间和匹配时间的和。32.2节描述了一种由Robin和Karp发现的一种有趣的字符串匹配算法。尽管这种算法在最坏情况下的运行时间Θ((n- m+1)m)并不比朴素算法好,但就平均情况和实际情况来说,该算法效果要好得多。这种算法也可以很好地推广,用以解决其他的模式匹配问题。32.3节描述一种字符串匹配算法,该算法通过构造一个有限自动机,专门用来搜寻所给的模式P在文本中出现的位置。这种算法需要O(m|QQ截图20220628110743.jpg|)的预处理时间,但是仅仅需要Θ(n)的匹配时间。32.4节介绍与其类似但是更加巧妙的Knuth-Morris Pratt(或KMP)算法;该算法的匹配时间同样为Θ(n),但是它缩短了预处理时间,仅需Θ(m)。

QQ截图20220628111351.jpg

图32-2 本章的字符串匹配算法及其预处理时间和匹配时间


符号和术语

我们用QQ截图20220628110743.jpg*来表示包含所有有限长度的字符串的集合,该字符串是由字母表2中的字符组成。在本章中,我们只考虑有限长度的字符串。长度为零的空字符串用e表示,也属于QQ截图20220628110743.jpg*。一个字符串x的长度用|x|来表示。两个字符串x和y的连结(concatenation)用xy表示,长度为|x|+|y|,由x的字符后接y的字符构成。

如果对某个字符串y∈QQ截图20220628110743.jpg*有x=wy,则称字符串w是字符串x的前缀,记作wQQ截图20220628111705.jpgx。注意到如果wQQ截图20220628111705.jpgx,则|w|≤|x|。类似地,如果对某个字符串y有x=yw,则称字符串w是字符串x的后缀,记作wQQ截图20220628111823.jpgx。和前缀类似,如果wQQ截图20220628111823.jpgx,则|w|≤|x|。例如,我们有abQQ截图20220628111705.jpgabcca和ccaQQ截图20220628111823.jpgabcca。空字符串ε同时是任何一个字符串的前缀和后缀。对于任意字符串x和y以及任意

字符a,当且仅当xaQQ截图20220628111823.jpgya时,我们有xQQ截图20220628111823.jpgy。请注意,C和都是传递关系。下面的引理在稍后将会用到。

引理32. 1(后缀重叠引理)假设x, y和z是满足xQQ截图20220628111823.jpgz和yQQ截图20220628111823.jpgz的字符串。如果|x|≤|y|,那么xQQ截图20220628111823.jpgy;如果|x|≥|y|,那么yQQ截图20220628111823.jpgx;如果|x|=|y|,那么x=y。

证明  见图32-3中的图示证明。

QQ截图20220628112322.jpg

图32-3引理32.1的图形证明。假定xQQ截图20220628111823.jpgz和yQQ截图20220628111823.jpgz。图的三个部分分别说明引理的三种情况。竖线连接字符串的匹配区域(用阴影表示)。(a)如果| xI≤|y|,则xQQ截图20220628111823.jpgy。(b)如果|x|≥|y|,则yQQ截图20220628111823.jpgx。(c)如果|x| = |y|,则x=y

为了使符号简洁,我们把模式P[1..m]的由k个字符组成的前缀P[1..k]记作Pk。因此P0=ε,Pm=P=P[1..m]。 与此类似,我们把文本T中由k个字符组成的前缀记为Tk。采用这种记号,我们能够把字符串匹配问题表述为:找到所有偏移s(0≤s≤n-m),使得PQQ截图20220628111823.jpgTs+m

在我们的伪代码中,把比较两个等长字符串是否相等的操作当做操作原语。如果字符串比较是从左到右进行的,并且当遇到一个字符不匹配时,比较操作终止,则可以假设在这样的一个检测中所花费的时间是关于已匹配成功字符数目的线性函数。更准确地说,假设检测“x==y”需要时间Θ(t+1),其中t是满足zQQ截图20220628111705.jpgx和zQQ截图20220628111705.jpgy的最长字符串z的长度。(我们用Θ(t+ 1)而不是Θ(t),是为了更好地处理t=0的情况;尽管第一个字符比较时就不匹配,但是在运行这个比较操作时仍然花费了一定的时间。)


32.1 朴素字符串匹配算法

朴素字符串匹配算法是通过一个循环找到所有有效偏移,该循环对n- m+1个可能的s值进行检测,看是否满足条件P[1..m]= T[s+1..s+m]。

QQ截图20220628112941.jpg

图32-4描绘的朴素字符串匹配过程可以形象地看成一个包含模式的“模板”沿文本滑动,同时对每个偏移都要检测模板上的字符是否与文本中对应的字符相等。第3~5行的for循环考察每一个可能的偏移。第4行的测试代码确定当前的偏移是否有效;该测试隐含着一个循环,该循环用于逐个检测对应位置上的字符,直到所有位置都能成功匹配或者有一个位置不能匹配为止。第5行用于打印输出每一个有效偏移s。

QQ截图20220628113048.jpg

图32-4 朴素字符串匹配对模式P=aab和文本T=acaabc的操作。可以把P想象成一个沿着正文滑动的“模板”。(a)~(d) 为4个连续的朴素字符串匹配。图中竖线连接相应匹配区域(阴影部分),折线连接先错误匹配的字符,如果是的话。在位移s=2时,找到匹配的模式,见图(c)

在最坏情况下,朴素字符串匹配算法运行时间为O((n- m+1)m)。例如,在考察文本字符串an(一串由n个a组成的字符串)和模式am时,对偏移s的n-m+1个可能值中的每一个,在第4行中比较相应字符的隐式循环必须执行m次来确定偏移的有效性。因此,最坏情况下的运行时间是Θ((n-m+1)m),如果m=[n/2],则运行时间是Θ(n2)。由于不需要预处理,朴素字符串匹配算法运行时间即为其匹配时间。

我们将会看到,NAIVE-STRING MATCHER并不是解决字符串匹配问题的最好过程。事实上,在本章中,我们将会发现Knuth-Morris-Pratt算法在最坏情况下比朴素算法好得多。这种朴素字符串匹配算法效率不高,是因为当其他无效的s值存在时,它也只关心一个有效的s值,而完全忽略了检测无效s值时获得的文本的信息。然而这样的信息可能非常有用。例如,如果P= aab并且我们发现s=0是有效的,由于T[4]=b,那么偏移1、2或3都不是有效的。在后续章节中,我们将考察能够充分利用这部分信息的几种方法。


练习

32.1-1  试说明当模式 P=0001,文本T=000010001010001时,朴素字符串匹配所执行的比较。

32.1-2  假设在模式 P中所有字符都不相同。试说明如何对一段n个字符的文本T加速过程NAIVE-STRING-MATCHER的执行速度,使其运行时间达到O(n)。

32.1-3  假设模式P和文本T是长度分别为m和n的随机选取的字符串,其字符分别来自含有d个元素的字母表QQ截图20220628110743.jpgd={0,1,...,d-1},其中d≥2。证明朴素算法第4行中隐含的循环所执行的字符比较的预计次数为:

QQ截图20220628113626.jpg

直到这次循环结束。(假设对于一个给定的偏移,当有一个字符不匹配或者整个模式已被匹配时,朴素算法将终止字符比较。)因此,对任意随机选取的字符串,朴素算法都是有效的。

32.1-4  假设允许模式 P中包含一个间隔符◇,它可以和任意字符串匹配(甚至可以和长度为0的字符串匹配)。例如,模式ab◇ba◇c在文本cabcbacbacab中的出现为

QQ截图20220628113807.jpg

QQ截图20220628113815.jpg

注意,间隔符可以在模式中出现任意次,但是不能在文本中出现。给出一个多项式时间算法,以确定这样的模式P是否在给定的文本T中出现,并分析算法的运行时间。


32.2 Rabin-Karp算法

在实际应用中,Rabin 和Karp所提出的字符串匹配算法能够较好地运行,并且还可以从中归纳出相关问题的其他算法,比如二维模式匹配。Rabin Karp算法的预处理时间是Θ(m),并且在最坏情况下,它的运行时间为Θ((n-m+1)m)。基于一些假设,在平均情况下,它的运行时间还是比较好的。

该算法运用了初等数论概念,比如两个数相对于第三个数模等价。如果想要了解相关的定义,请参照31.1节的内容。

为了便于说明,假设QQ截图20220628110743.jpg={0,1,2,...,9},这样每个字符都是十进制数字。(在通常情况下,可以假定每个字符都是以d为基数表示的数字,其中d= |QQ截图20220628110743.jpg|)我们可以用长度为k的十进制数来表示由k个连续的字符组成的字符串。因此,字符串31 415对应着十进制数31 415。假如输入的字符既可以看做是图形符号,也可以看做是数字,那么在本节中我们会发现,运用我们的标准文本字体,把它们表示为数字会更加方便。

给定一个模式P[1.. m],假设p表示其相应的十进制值。类似地,给定文本T[1..n],假设ts表示长度为m的子字符串T[s+1..s+ m]所对应的十进制值,其中s=0,1,...,n-m。当然,只有在T[s+1..s+m]=P[1..m]时,ts=p。如果能在时间Θ(m)内计算出p值,并在总时间Θ(n- m+ 1)内计算出所有的ts值,那么通过比较p和每一个ts值,就能在Θ(m) +Θ(n-

m+ 1)=Θ(n)时间内找到所有的有效偏移s。(目前,暂不考虑p和t。值可能很大的问题。)我们可以运用霍纳法则(参见30. 1节)在时间Θ(m)内计算出p:

QQ截图20220628114612.jpg

类似地,也可以在Θ(m)时间内根据T[1. . m]计算出t0的值。

为了在时间Θ(n- m) 内计算出剩余的值t1,t2,...,tn-m,我们需要在常数时间内根据ts计算出ts+1,因为

QQ截图20220628114845.jpg

减去10m-1T[s+1]就从t,中去掉了高位数字,再把结果乘以10就使得数字向左移动一个数位, 然后加上T[s+m+1],则加入一个适当的低位数字。例如,如果m=5并且t,=31415,那么我们希望能够去掉高位数字T[s+1]=3,并且加入新的低位数字(假设是T[s+5+1]=2),从而获得:

QQ截图20220628140118.jpg

如果能够预先计算出常数10m-1(用31.6节中介绍的技术,就可以在O(lgm)的时间内完成这一计算过程,但对于这个应用,一种简便的运行时间为O(m)的算法就足够完成任务),则每次执行式(32.1)的计算时,需要执行的算术运算的次数为常数。因此,可以在时间Θ(m)内计算出p,在时间Θ(n- m+ 1)内计算出所有t0,t1, t2, ..,tn-m的值。因而可以用Θ(m)的预处理时间和Θ(n-m+ 1)的匹配时间找到所有模式P[1.. m]在文本T[1.. n]中出现的位置。

到目前为止,我们有意回避的一个问题是:p和ts的值可能太大,导致不能方便地对其进行操作。如果P包含m个字符,那么关于在p(m数位长)上的每次算术运算需要“常数”时间这一假设就不合理了。幸运的是,我们可以很容易地解决这个问题,如图32-5所示:选取一个合适的模q来计算p和ts的模。我们可以在Θ(m)的时间内计算出模q的p值,并且可以在Θ(n-m+ 1)时间内计算出模q的所有ts值。如果选模q为一个素数,使得10q恰好满足一个计算机字长,那么可以用单精度算术运算执行所有必需的运算。在一般情况下, 采用d进制的字母表{0,1, ..., d-1}时,选取一个q值,使得dq在一个计算机字长内,然后调整递归式(32. 1),使其能够对模q有效,式子变为:

QQ截图20220628140851.jpg

其中h=dm-1 (mod q)是一个具有m数位的文本窗口的高位数位上的数字“1”的值。

QQ截图20220628141017.jpg


图32-5 Rabin-Karp 算法。每一个字符都是一个十进制数, 并且对模13取余。(a)一个文本字符串。长度为5的窗口被标上了阴影,标记阴影数字的数值对模13取余的结果为7。(b)一个相同的文本字符串,对长度为5的窗口的每一个可能位置,计算出它对13取余的数值。假定模式P=31415,由于31415=7(mod13),所以寻找所有对模13取余为7的窗口。该算法找到两个与之对应的窗口,在图中用阴影表示出来。第一个是在文本的位置7处开始的,最后验证确实为模式的出现。而第二个是在文本的位置13处开始的,但最终验证为伪命中。(c) 已知前一个窗 口的值,如何在常数时间内计算出某个窗口的值。第一个窗口的值为31415。去除高位数字3,往左移(乘以10),然后加入低位数字2得到新的值14152。因为所有的计算都是模13取余,所以第一个窗口的值是7,从而新窗口的值是8

但是基于模q得到的结果并不完美:ts= p(mod q)并不能说明ts=p。但是另一方面,如果ts≠p(mod q),那么可以断定ts≠p,从而确定偏移s是无效的。因此可以把测试ts= p(mod q)是否成立作为一种快速的启发式测试方法用于检测无效偏移s。任何满足ts=p(mod q)的偏移s都需要被进一步检测,看s是真的有效还是仅仅是一个伪命中点。这项额外的测试可以通过检测条件P[1..m]= T[s+1..s+m]来完成,如果q足够大,那么这个伪命中点可以尽量少出现,从而使额外测试的代价降低。

下面的过程准确描述了上述思想。过程的输人是文本T,模式P,使用基数d(其典型取值为|QQ截图20220628141542.jpg|)和素数q。

QQ截图20220628141607.jpg

RABIN-KARP-MATCHER执行过程如下。所有的字符都假设是d进制的数字。仅为了说明的清楚,给t添加了下标,去除所有下标不会影响程序运行。第3行初始化m位窗口中高位上的值h。第4~8行计算出P[1..m]mod q的值p,计算出T[1..m]mod q的值t0。第9~14行的for循环迭代便利了所有可能的偏移s,保持如下的不变量:

第10行无论何时执行,都有ts=T[s+1..s+m] mod q。

如果在第10行中有p=ts(一个“命中点”),那么在第11行检测是否P[1..m]= T[s+1..s+m],用以排除它是伪命中点的可能性。第12行打印出所有找到的有效偏移。如果s<n- m(在第13行中检测),则至少再执行一次for 循环,这时首先执行第14行以保证再次执行到第10行时循环不变式依然成立。第14行直接利用等式(32.2),就可以在常数时间内由ts mod q的值计算出ts+1 mod q的值。

RABIN-KARP-MATCHER的预处理时间为Θ(m),在最坏情况下,它的匹配时间是Θ((n-m+1)m),因为Rabin-Karp算法和朴素字符串匹配算法一样,对每个有效偏移进行显式验证。如果P=am并且T=an,由于在n- m+1个可能的偏移中每一个都是有效的,则验证所需的时间为Θ((n- m+ 1)m)。

在许多实际应用中,我们希望有效偏移的个数少一些(如只有常数c个)。在这样的应用中,加上处理伪命中点所需时间,算法的期望匹配时间为O((n- m+1) + cm)=O(n+m)。减少模q的值就如同从QQ截图20220628141542.jpg*到Zq上的一个随机映射,基于这个假设,可以对算法进行启发式分析。(参见11.3.1节中对散列除法的讨论,要正规证明这个假设是比较困难的,但是有一种可行的方法,就是假设q是从适当大的整数中随机得出的,我们在此将不继续纠缠形式化的问题。)然后我们能够预计伪命中的次数为O(n/q),因为可以估计出任意的ts模q的余数等价于p的概率为1/q。因为第10行中的测试会在O(n)个位置上失败,且每次命中的时间代价是O(m),因此,Rabin-Karp算法的期望运行时间为:

QQ截图20220628142320.jpg

其中v是有效偏移量。如果v=O(1)并且q≥m,则这个算法的运行时间是O(n)。也就是说,如果期望的有效偏移量很少(O(1)),而选取的素数q大于模式的长度,则可以估计Rabin-Karp算法的匹配时间为O(n+m),由于m≤n,这个算法的期望匹配时间是O(n)。


练习

32.2-1  如果模q=11,那么当Rabin-Karp匹配算法在文本T=3 141 592 653 589 793中搜寻模式P=26时,会遇到多少个伪命中点?

32.2-2  如何扩展Rabin-Karp算法,使其能解决如下问题:如何在文本字符串中搜寻出给定的k个模式中的任何一个出现?起初假设所有k个模式都是等长的,然后扩展你的算法以适用于不同长度的模式。

32.2-3  试说明如何扩展Rabin-Karp算法用于处理以下问题:在一个n×n的二维字符数组中搜索一个给定的m×m的模式。(该模式可以在水平方向和垂直方向移动,但是不可以旋转。)

32.2-4  Alice有一份很长的 n位文件复印件A=<an-1,an-2,...,a0>,Bob 也有一份类似的文件B=<bn-1,bn-2,..., b0)。Alice 和Bob都希望知道他们的文件是否一样。为了避免传送整个文件A或B,他们运用下列快速的概率检查方法。他们共同选择一个素数q>1000n,并从{0,1,...,q-1}中随机选取一个整数x。然后,Alice 求出

QQ截图20220628142912.jpg

的值,Bob也用类似方法计算出B(x)。证明:如果A≠B,则A(x)=B(x)的概率至多为1/1000;如果两个文件相同,则A(x)的值必定等于B(x)的值。(提示:参见练习31.4-4。)

相关内容

文章评论

表情

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