实验2 串匹配
1. 1、KMP串匹配算法 ............................................................................................................................................. 1
1.1 KMP串匹配及其串行算法 ......................................................................................................................... 1 1.2 KMP串匹配的并行算法 ............................................................................................................................. 5 2. 2、随机串匹配算法 .............................................................................................................................................. 9
2.1 随机串匹配及其串行算法 ......................................................................................................................... 9 2.2 随机串匹配的并行算法 ........................................................................................................................... 11 3. 3、近似串匹配算法 ............................................................................................................................................ 12
3.1 近似串匹配及其串行算法 ....................................................................................................................... 12 3.2 近似串匹配的并行算法 ........................................................................................................................... 17 4. 小结 ..................................................................................................................................................................... 20 5. 参考文献 ............................................................................................................................................................. 20 串匹配（String Matching）问题是计算机科学中的一个基本问题，也是复杂性理论中研究的最广泛的问题之一。它在文字编辑处理、图像处理、文献检索、自然语言识别、生物学等领域有着广泛的应用。而且，串匹配是这些应用中最耗时的核心问题，好的串匹配算法能显著地提高应用的效率。因此，研究并设计快速的串匹配算法具有重要的理论价值和实际意义。
串匹配问题实际上就是一种模式匹配问题，即在给定的文本串中找出与模式串匹配的子串的起始位置。最基本的串匹配问题是关键词匹配（Keyword Matching）。所谓关键词匹配，是指给定一个长为n的文本串T[1，n]和长为m的模式串P[1，m]，找出文本串T中与模式串所有精确匹配的子串的起始位置。串匹配问题包括精确串匹配（Perfect String Matching）、随机串匹配（Randomized String Matching）和近似串匹配（Approximate String Matching）。另外还有多维串匹配（Multidimensional String Matching）和硬件串匹配（Hardware String Matching）等。
本章中分别介绍改进的KMP串匹配算法，采用散列技术的随机串匹配算法，基于过滤算法的近似串匹配算法，以及它们的MPI编程实现。
1. 1、KMP串匹配算法
1.1 KMP串匹配及其串行算法
KMP算法首先是由D.E. Knuth、J.H. Morris以及V.R. Pratt分别设计出来的，所以该算法被命名为KMP算法。KMP串匹配算的基本思想是：对给出的的文本串T［1，n］与模式串P[1，m]，假设在模式匹配
1
的进程中，执行T[i]和P[j]的匹配检查。 若T[i]=P[j]，则继续检查T[i+1]和P[j+1]是否匹配。若T[i]≠P[j]，则分成两种情况：若j=1，则模式串右移一位，检查T[i+1]和P[1]是否匹配；若1 1. 修改的KMP算法 在原算法基础上很多学者作了一些改进工作，其中之一就是重新定义了KMP算法中的next函数，即求next函数时不但要求P[1，next(j) －1]=P[j－(next(j) －1)，j-1]，而且要求P[next(j)] ≠P[j]，记修改后的next函数为newnext。在模式串字符重复高的情况下修改的KMP算法比传统KMP算法更加有效。 算法 14.1 修改的KMP串匹配算法 输入：文本串T[1，n]和模式串P[1，m] 输出：是否存在匹配位置 procedure modeifed_KMP Begin (1) i=1,j=1 (2) while i≤n do (2.1) while j≠0 and P[j]≠T[i] do j=newnext[j] end while (2.2)if j=m then return true else j=j+1,i=i+1 end if end while (3) return false End 算法 14.2 next函数和newnext函数的计算算法 输入：模式串P[1，m] 输出：next[1，m+1]和newnext[1，m] procedure next Begin 2 (1) next[1]=0 (2) j=2 (3) while j≤m do (3.1)i=next[j-1] (3.2)while i≠0 and P[i]≠P[j-1] do i=next[i] end while (3.3)next[j]=i+1 (3.4)j=j+1 end while End procedure newnext Begin (1) newnext(1)=0 (2) j=2 (3) while j≤m do (3.1)i=next(j) (3.2)if i=0 or P[j]≠P[i+1] then newnext[j]=i else newnext[j]=newnext[i] end if (3.3)j=j+1 end while End 2. 改进的KMP算法 易知算法14.1的时间复杂度为O（n），算法14.2的时间复杂度为O（m）。算法14.1中所给出的KMP算法只能找到第一个匹配位置，实际应用中往往需要找出所有的匹配位置。下面给出改进后的算法14.3便解决了这一问题。 算法 14.3 改进KMP串匹配算法 输入：文本串T[1，n]和模式串P[1，m] 3 输出：匹配结果match[1，n] procedure improved_KMP Begin (1) i=1，j=1 (2) while i≤n do (2.1)while j≠0 and P[j]≠T[i] do j=newnext[j] end while (2.2)if j=m then match[i-(m-1)]=1 j=next[m+1] i=i+1 else i=i+1 j=j+1 end if end while (3) max_prefix_len=j-1 End 算法 14.4 next函数和newnext函数的计算算法输入：模式串P[1，m] 输出：next[1，m+1]和newnext[1，m] procedure NEXT Begin (1) next[1]=newnext[1]=0 (2) j=2 (3) while j≤m+1 do (3.1)i=next[j-1] (3.2)while i≠0 and W[i]≠W[j-1]) do i=next[i] end while 4 (3.3)next[j]=i+1 (3.4)if j≠m+1 then if W[j] ≠W[i+1] then newnext[j]=i+1 else newnext[j]=newnext[i+1] end if end if (3.5)j=j+1 end while End 在算法14.3中，内层while循环遇到成功比较时和找到文本串中模式串的一个匹配位置时文本串指针i均加1，所以至多做n次比较；内while循环每次不成功比较时文本串指针i保持不变，但是模式串指针j减小，所以i－j的值增加且上一次出内循环时的i－j值等于下一次进入时的值，因此不成功的比较次数不大于i－j的值的增加值，即小于n，所以总的比较次数小于2n，所以算法14.3的时间复杂度为 O（n）。算法14.4只比的算法14.2多计算了next(m+1)，至多多做m-1次比较，所以算法14.4的时间复 杂度同样为O（m）。 1.2 KMP串匹配的并行算法 1. 算法原理 在介绍了改进的KMP串行算法基础上，这一节主要介绍如何在分布存储环境中对它进行实现。设计的思路为：将长为n的文本串T均匀划分成互不重叠的p段，分布于处理器0到p-1中，且使得相邻的文本段分布在相邻的处理器中，显然每个处理器中局部文本段的长度为?n/p?（最后一个处理器可在其段尾补上其它特殊字符使其长度与其它相同）。再将长为m的模式串P和模式串的newnext函数播送到各处理器中。各处理器使用改进的KMP算法并行地对局部文本段进行匹配，找到所有段内匹配位置。 但是每个局部段（第p-1段除外）段尾m-1字符中的匹配位置必须跨段才能找到。一个简单易行的办法就是每个处理器（处理器p-1除外）将本局部段的段尾m-1个字符传送给下一处理器，下一处理器接收到前一处理器传来的字符串后，再接合本段的段首m-1个字符构成一长为2(m-1)的段间字符串，对此字符串做匹配，就能找到所有段间匹配位置。但是算法的通信量很大，采用下述两种改进通信的方法可以大大地降低通信复杂度：①降低播送模式串和newnext函数的通信复杂度。利用串的周期性质，先对模式串P 5