《并行计算》课程教学资源（讲义）串匹配

2串匹配 串匹配( String matching)问题是计算机科学中的一个基本问题,也是复杂性理论中研 究的最广泛的问题之一。它在文字编辑处理、图像处理、文献检索、自然语言识别、生物学 等领域有着广泛的应用。而且,串匹配是这些应用中最耗时的核心问题,好的串匹配算法能 显著地提高应用的效率。因此,研究并设计快速的串匹配算法具有重要的理论价值和实际意 串匹配问题实际上就是一种模式匹配问题,即在给定的文本串中找出与模式串匹配的子 串的起始位置。最基本的串匹配问题是关键词匹配( Keyword Matching)。所谓关键词匹配, 是指给定一个长为n的文本串1,n]和长为m的模式串P[1,m],找出文本串T中与模式 串所有精确匹配的子串的起始位置。串匹配问题包括精确串匹配( Perfect String matching)、 随机串匹配( Randomized String matching)和近似串匹配( Approximate String Matching) 另外还有多维串匹配( Multidimensional String Matching和硬件串匹配( Hardware String Matching)等 本章中分别介绍改进的KMP串匹配算法,采用散列技术的随机串匹配算法,基于过滤 算法的近似串匹配算法,以及它们的MPI编程实现。 11KMP串匹配算法 111KMP串匹配及其串行算法 KMP算法首先是由 DE Knuth、JH.Mori以及ⅤR.Pa分别设计出来的,所以该算 法被命名为KMP算法。KMP串匹配算的基本思想是:对给出的的文本串T[1,n]与模式 串P[,m,假设在模式匹配的进程中,执行T和P的匹配检查。若T=P,则继续 检查T计+和P[+1是否匹配。若≠P[,则分成两种情况:若j=1,则模式串右移一位 检查Ti+1和P[1是否匹配;若1<j≤m,则模式串右移j- next()位,检查和P[next(] 是否匹配(其中next是根据模式串P1,m]的本身局部匹配的信息构造而成的)。重复此过 程直到j=m或in结東 1.修改的KMP算法 在原算法基础上很多学者作了一些改进工作,其中之一就是重新定义了KMP算法中的 next函数,即求next函数时不但要求P[1,next(-1]=P-(next)-1),}1],而且要求 P[ next()≠P],记修改后的next函数为 newnext。在模式串字符重复高的情况下修改的 KMP算法比传统KMP算法更加有效。 算法141修改的KMP串匹配算法 输入:文本串71,n和模式串P[1,m] 输出:是否存在匹配位置 procedure modifed KMP Begin (1)i=1,j=1 (2) while i≤ndo (2) while j≠0andP[j]≠Tdo

1 1. 2 串匹配 串匹配（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.1 KMP 串匹配及其串行算法 KMP 算法首先是由 D.E. Knuth、J.H. Morris 以及 V.R. Pratt 分别设计出来的，所以该算 法被命名为 KMP 算法。KMP 串匹配算的基本思想是：对给出的的文本串 T［1，n］与模式 串 P[1，m]，假设在模式匹配的进程中，执行 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<j≤m，则模式串右移 j－next(j)位，检查 T[i]和 P[next(j)] 是否匹配（其中 next 是根据模式串 P[1，m]的本身局部匹配的信息构造而成的）。重复此过 程直到 j=m 或 i=n 结束。 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

jnewnextLiI end while (2.2)if j=m then return true J=+1,=1+1 end if end while (3) return false End 算法142next函数和 newnext函数的计算算法 输入:模式串P[1l,m 输出:next,m+1和 newnext[1,m procedure next B (1)next[1] (2)j=2 (3) while j≤mde (3.2) while i≠0andP[]≠P[-]do =next] end while (3.3) nextLi=+1 end while procedure newnext Begi (1) newnext(1)=0 (3) while i≤mdo (3.1)i=next() (3.2)if i=0 or P[=P(i+1]the newnext[]=i newnext[l-newnexti d if end while

2 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 (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算法 易知算法141的时间复杂度为O(n),算法142的时间复杂度为O(m)。算法14.1 中所给出的KMP算法只能找到第一个匹配位置,实际应用中往往需要找出所有的匹配位置。 下面给出改进后的算法14.3便解决了这一问题。 算法143改进KMP串匹配算法 输入:文本串丌1,n和模式串P[1,m 输出:匹配结果 match[1,n] procedure improved KMP Begin (2) while i≤ndo (21) while j≠0andP]≠T[do end while (2.2)if j=m then match i-(m-D)=I j= next[m+l =1+1 j+1 end if end while 3)max prefix len=j-1 算法144next函数和 newnext函数的计算算法 输入:模式串P[1,m] 输出;next1,m+1和 newnext[1,m procedure NEXT (1)next[1]=newnext[ 11=0 (3) while j≤m+1do (3.2) while i≠0andW[i≠W-1])d end while (3.3)next=i+l (34)ifj≠m+ I then ifW]≠W[i+l]then newnext[]=i+I newnext[=newnext[i+ll

3 2. 改进的 KMP 算法 易知算法 14.1 的时间复杂度为 O（n），算法 14.2 的时间复杂度为 O（m）。算法 14.1 中所给出的 KMP 算法只能找到第一个匹配位置，实际应用中往往需要找出所有的匹配位置。 下面给出改进后的算法 14.3 便解决了这一问题。 算法 14.3 改进 KMP 串匹配算法 输入：文本串 T[1，n]和模式串 P[1，m] 输出：匹配结果 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 (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 end while End 在算法14.3中,内层 while循环遇到成功比较时和找到文本串中模式串的一个匹配位置 时文本串指针i均加1,所以至多做n次比较:;内 while循环每次不成功比较时文本串指针 保持不变,但是模式串指针j减小,所以ij的值增加且上一次出内循环时的i一j值等于下 次进入时的值,因此不成功的比较次数不大于i一j的值的增加值,即小于n,所以总的比 较次数小于2n,所以算法143的时间复杂度为O(n)。算法144只比的算法142多计算了 next(m+1),至多多做m-1次比较,所以算法144的时间复杂度同样为O(m)。 112KMP串匹配的并行算法 1.算法原理 在介绍了改进的KMP串行算法基础上,这一节主要介绍如何在分布存储环境中对它进 行实现。设计的思路为:将长为n的文本串T均匀划分成互不重叠的p段,分布于处理器0 到p-1中,且使得相邻的文本段分布在相邻的处理器中,显然每个处理器中局部文本段的长 度为「n/p1(最后一个处理器可在其段尾补上其它特殊字符使其长度与其它相同)。再将长 为m的模式串P和模式串的 newnext函数播送到各处理器中。各处理器使用改进的KMP算 法并行地对局部文本段进行匹配,找到所有段内匹配位置。 但是每个局部段(第p-1段除外)段尾m-1字符中的匹配位置必须跨段才能找到。一个 简单易行的办法就是每个处理器(处理器p-1除外)将本局部段的段尾m-1个字符传送给下 处理器,下一处理器接收到前一处理器传来的字符串后,再接合本段的段首m-1个字符 构成一长为2(m-1)的段间字符串,对此字符串做匹配,就能找到所有段间匹配位置。但是算 法的通信量很大,采用下述两种改进通信的方法可以大大地降低通信复杂度:①降低播送模 式串和 newnext函数的通信复杂度。利用串的周期性质,先对模式串P作预处理,获得其最 小周期长度U、最小周期个数s及后缀长度V(P=UV),只需播送U,s,Ⅳ和部分 newnext 函数就可以了,从而大大减少了播送模式串和 newnext函数的通信量。而且串的最小周期和 next函数之间的关系存在着下面定理1所示的简单规律,使得能够设计出常数时间复杂度的 串周期分析算法。②降低每个处理器(处理器p-1除外)将本局部文本段的段尾m-1个字符 传送给下一处理器的通信复杂度。每个处理器在其段尾m-1个字符中找到模式串P的最长 前缀串,因为每个处理器上都有模式串信息,所以只需传送该最长前缀串的长度就行了。这 样就把通信量从传送模式串P的最长前缀串降低到传送一个整数,从而大大地降低了通信 复杂度。而且KMP算法结束时模式串指针1的值就是文本串尾模式串最大前缀串的长度, 这就可以在不增加时间复杂度的情况下找到此最大前缀串的长度 串的周期性分析 定义141:给定串P,如果存在字符串U以及正整数K≥2,使得串P是串的前缀 ( Prefix),则称字符串U为串P的周期( Period)。字符串P的所有周期中长度最短的周期 称为串P的最小周期( Maximal Period) 串的周期分析对最终并行算法设计非常关键,串的最小周期和next函数之间的关系存 在着如下定理141所示的简单规律,基于该规律可以设计出常数时间复杂度的串周期分析

4 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.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 作预处理，获得其最 小周期长度|U|、最小周期个数 s 及后缀长度|V|（P=UsV），只需播送 U，s，|V|和部分 newnext 函数就可以了，从而大大减少了播送模式串和 newnext 函数的通信量。而且串的最小周期和 next 函数之间的关系存在着下面定理 1 所示的简单规律，使得能够设计出常数时间复杂度的 串周期分析算法。②降低每个处理器（处理器 p-1 除外）将本局部文本段的段尾 m-1 个字符 传送给下一处理器的通信复杂度。每个处理器在其段尾 m-1 个字符中找到模式串 P 的最长 前缀串，因为每个处理器上都有模式串信息，所以只需传送该最长前缀串的长度就行了。这 样就把通信量从传送模式串 P 的最长前缀串降低到传送一个整数，从而大大地降低了通信 复杂度。而且 KMP 算法结束时模式串指针 j-1 的值就是文本串尾模式串最大前缀串的长度， 这就可以在不增加时间复杂度的情况下找到此最大前缀串的长度。 2. 串的周期性分析 定义 14.1：给定串 P，如果存在字符串 U 以及正整数 K≥2，使得串 P 是串 Uk 的前缀 （Prefix），则称字符串 U 为串 P 的周期（Period）。字符串 P 的所有周期中长度最短的周期 称为串 P 的最小周期（Miximal Period）。 串的周期分析对最终并行算法设计非常关键，串的最小周期和 next 函数之间的关系存 在着如下定理 14.1 所示的简单规律，基于该规律可以设计出常数时间复杂度的串周期分析

算法。 定理141:已知串P长为m,则u=m+1-next(m+1)为串P的最小周期长度。 算法145串周期分析算法 输入:next[m+ 输出:最小周期长度 period len 最小周期个数 模式串的后缀长度 pattern- suffixlen procedure PERIOD ANALYSIS B period len=m+1-next(m+1) period num=(int )m/pe pattern suffixlen=m mod period ler 3.并行算法描述 在前述的串行算法以及对其并行实现计的分析的基础上,我们可以设计如下的并行 KMP串匹配算法。 算法146并行KMP串匹配算法 输入:分布存储的文本串T,「n/p](i=0,1,2,…,p-1) 存储于Po的模式串P[1,ml 输出:所有的匹配位置 Be (1) Po call procedure NEXT/*调用算法144,求模式串P的 next函数和 newnext函数* Po call procedure PERIOD ANALYSIS陣*调用算法14.5分析P的周期*/ (2) Po broadcast period eriod num, period suffixlen to other processors/播送 P之最小周期长度、最小周期个数和后缀长度* Po broadcast P[, period len]*不播送P之最小周期*/ if period num= I then/*播送P之部分 newnext函数,如周期为1,则播送整个 newnext函数:否则播送2倍周期长的 newnext函数* broadcast newnext [1, m broadcast newnext[ 1, 2*period len end if (3)fori= I to p-l par-do/*由传送来的P之周期和部分 newnext函数重构整个模式串 和 newnext函数* Pi rebuild newnext end for fori=ltop- I par-do/调用算法147做局部段匹配,并获得局部段尾最大前缀串 之长度* Pi call procedure KMP(T,P,n, 0, match) end for (4)for i=0 to p-2 par-de

5 算法。 定理 14.1：已知串 P 长为 m，则 u=m+1－next(m+1)为串 P 的最小周期长度。 算法 14.5 串周期分析算法 输入：next[m+1] 输出：最小周期长度 period_len 最小周期个数 period_num 模式串的后缀长度 pattern-suffixlen procedure PERIOD_ANALYSIS Begin period_len=m+1-next(m+1) period_num=(int)m/period_len pattern_suffixlen=m mod period_len End 3. 并行算法描述 在前述的串行算法以及对其并行实现计的分析的基础上，我们可以设计如下的并行 KMP 串匹配算法。 算法 14.6 并行 KMP 串匹配算法 输入：分布存储的文本串 Ti[1， n / p ]（i=0，1，2，…，p-1） 存储于 P0 的模式串 P[1，m] 输出：所有的匹配位置 Begin (1) P0 call procedure NEXT /*调用算法 14.4，求模式串 P 的 next 函数和 newnext 函数*/ P0 call procedure PERIOD_ANALYSIS /*调用算法 14.5 分析 P 的周期*/ (2) P0 broadcast period_len，period_num，period_suffixlen to other processors /*播送 P 之最小周期长度、最小周期个数和后缀长度*/ P0 broadcast P[1，period_len] /*不播送 P 之最小周期*/ if period_num=1 then /*播送 P 之部分 newnext 函数，如周期为 1，则播送整个 newnext 函数；否则播送 2 倍周期长的 newnext 函数*/ broadcast newnext [1，m] else broadcast newnext[1，2*period_len] end if (3) for i=1 to p-1 par-do /*由传送来的 P 之周期和部分 newnext 函数重构整个模式串 和 newnext 函数*/ Pi rebuild newnext end for for i=1 to p-1 par-do /*调用算法 14.7 做局部段匹配，并获得局部段尾最大前缀串 之长度*/ Pi call procedure KMP(T，P ，n ，0，match) end for (4) for i =0 to p-2 par-do