中国科学技术大学：《并行计算 Parallel Computing》课程教学资源（实验）串匹配 String Matching

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[1,m],假设在模式匹配的进程中,执行币和P的匹配检查。若=P[,则继续 检查T计+和P[+1是否匹配。若≠P[,则分成两种情况:若j=1,则模式串右移一位 检查T计+1和P是否匹配;若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 Begi (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[-1]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[,m] 输出:匹配结果 match1,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 max prefix I 算法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[≠W-1])do end while (3.3)next=i+l (34)ifj≠m+ I then ifW≠w[i+ 1] 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减小,所以i-j的值增加且上一次出内循环时的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-l段除外)段尾m-1字符中的匹配位置必须跨段才能找到。一个 简单易行的办法就是每个处理器(处理器p1除外)将本局部段的段尾m-1个字符传送给下 处理器,下一处理器接收到前一处理器传来的字符串后,再接合本段的段首m-1个字符 构成一长为2(m-1)的段间字符串,对此字符串做匹配,就能找到所有段间匹配位置。但是算 法的通信量很大,采用下述两种改进通信的方法可以大大地降低通信复杂度:①降低播送模 式串和 newnext函数的通信复杂度。利用串的周期性质,先对模式串P作预处理,获得其最 小周期长度U、最小周期个数s及后缀长度Ⅳ(P=UV),只需播送U,s,Ⅳ和部分 newnext 函数就可以了,从而大大减少了播送模式串和 newnext函数的通信量。而且串的最小周期和 next函数之间的关系存在着下面定理1所示的简单规律,使得能够设计出常数时间复杂度的 串周期分析算法。②降低每个处理器(处理器p-1除外)将本局部文本段的段尾m-1个字符 传送给下一处理器的通信复杂度。每个处理器在其段尾m-1个字符中找到模式串P的最长 前缀串,因为每个处理器上都有模式串信息,所以只需传送该最长前缀串的长度就行了。这 样就把通信量从传送模式串P的最长前缀串降低到传送一个整数,从而大大地降低了通信 复杂度。而且KMP算法结束时模式串指针}1的值就是文本串尾模式串最大前缀串的长度, 这就可以在不增加时间复杂度的情况下找到此最大前缀串的长度 串的周期性分析 定义141:给定串P,如果存在字符串U以及正整数K≥2,使得串P是串U的前缀 (Prefⅸx),则称字符串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 最小周期个数 period num 模式串的后缀长度 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串匹配算法 输入:分布存储的文本串T1,m/p(i=0,1,2, 存储于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 len, period num, period suffixlen to other processors /*fhit 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

Pi send maxprefixlen to Pi for iI to p-l par-do Pi receive maxprefixlen from Pi-1 call procedure KMP(Ti, P, m-1, maxprefixlen, match+m-1)/*iHH 算法147做段间匹配* end for End 该算法中调用的KMP算法必须重新修改如下,因为做段间匹配时已经匹配了 axprefixlen长度的字符串,所以模式串指针只需从 maxprefixlen+1处开始 算法14.7重新修改的KMP算法 输入:分布存储的文本串和存储于P的模式串P[1,m 输出:所有的匹配位置 procedure KMP(T, P, textlen, matched num, match) Begin l (2)j=matched num+ (3) while i≤ textlen d (3.1) while j≠0andP]≠Tdo end while (3.2)ifj=m the match i-(m-D=I next[m+1 =1+1 else I=1+1 end if end while (4)maxprefixlen=j-1 下面从计算时间复杂度和通信时间复杂度两个方面来分析该算法的时间复杂度。在分析 计算时间复杂度时,假定文本串初始已经分布在各个处理器上,这是合理的,因为文本串 般很大,不会有大的变化,只需要分布一次就可以,同时也假定结果分布在各处理器上。本 算法的计算时间由算法步(1)中所调用的算法144的时间复杂度O(m)和算法145的时 间复杂度O(1);算法步(3)和算法步(4)所调用的改进的KMP算法14.7的时间复杂度 O(np)和O(m)构成。所以本算法总的计算时间复杂度为O(n/p+m)。通信复杂度由算 法步(2)播送模式串信息(最小周期串U及最小周期长度、周期个数和后缀长度三个整数) 和 newnext函数(长度为2u的整数数组,u为串U的长度)以及算法步(4)传送最大前缀 串长度组成,所以通信复杂度与具体采用的播送算法有关。若采用二分树通信技术,则总的 通信复杂度为O(uogp) MPI源程序请参见章末附录。 6

6 Pi send maxprefixlen to Pi+1 end for for i=1 to p-1 par-do Pi receive maxprefixlen from Pi-1 Pi call procedure KMP(Ti，P，m-1， maxprefixlen，match+m-1) /*调用 算法 14.7 做段间匹配*/ end for End 该算法中调用的 KMP 算法必须重新修改如下，因为做段间匹配时已经匹配了 maxprefixlen 长度的字符串，所以模式串指针只需从 maxprefixlen+1 处开始。 算法 14.7 重新修改的 KMP 算法 输入：分布存储的文本串和存储于 P0 的模式串 P[1，m] 输出：所有的匹配位置 procedure KMP(T，P，textlen， matched_num，match) Begin (1) i=1 (2) j=matched_num+1 (3) while i≤textlen do (3.1)while j≠0 and P[j]≠T[i] do j=newnext[j] end while (3.2)if j=m then match[i-(m-1)]=1 j=next[m+1] i=i+1 else j=j+1 i=i+1 end if end while (4) maxprefixlen=j-1 End 下面从计算时间复杂度和通信时间复杂度两个方面来分析该算法的时间复杂度。在分析 计算时间复杂度时，假定文本串初始已经分布在各个处理器上，这是合理的，因为文本串一 般很大，不会有大的变化，只需要分布一次就可以，同时也假定结果分布在各处理器上。 本 算法的计算时间由算法步（1）中所调用的算法 14.4 的时间复杂度 O（m）和算法 14.5 的时 间复杂度 O（1）；算法步（3）和算法步（4）所调用的改进的 KMP 算法 14.7 的时间复杂度 O（n/p）和 O（m）构成。所以本算法总的计算时间复杂度为 O（n/p+m）。通信复杂度由算 法步（2）播送模式串信息（最小周期串 U 及最小周期长度、周期个数和后缀长度三个整数） 和 newnext 函数（长度为 2u 的整数数组，u 为串 U 的长度）以及算法步（4）传送最大前缀 串长度组成，所以通信复杂度与具体采用的播送算法有关。若采用二分树通信技术，则总的 通信复杂度为 O（ulogp）。 MPI 源程序请参见章末附录

12随机串匹配算法 121随机串匹配及其串行算法 采用上一节所述的MP算法虽然能够找到所有的匹配位置,但是算法的复杂度十分高, 在某些领域并不实用。本节给出了随机串匹配算法,该算法的主要采用了散列(Hash)技术 的思想,它能提供对数的时间复杂度。其基本思想是:为了处理模式长度为m的串匹配问题, 可以将任意长为m的串映射到O(1ogm)整数位上,映射方法须得保证两个不同的串映射到同 整数的概率非常小。所得到的整数之被视为该串的指纹( Fingerprint),如果两个串的指 纹相同则可以判断两个串相匹配 1.指纹函数 本节中假定文本串和模式串取字符集∑={0,1}中的字母。 如上所述,随机串匹配算法的基本策略是将串映射到某些小的整数上。令T是长度为n 的文本串,P是长度为m≤n的模式串,匹配的目的就是识别P在T中出现的所有位置。考 虑长度为m的T的所有子串集合B。这样的起始在位置i(1≤i≤nm+1)的子串共有n-m+ 个。于是问题可重新阐述为去识别与P相同的B中元素的问题。该算法中最重要的是如何选 择一个合适的映射函数( Mapping function),下面将对此进行简单的讨论。 令F=n}me是函数集,使得J将长度为m的串映射到域D,且要求集合F满足下述 三个性质:①对于任意串X∈B以及每一个p∈S(S为模式串的取值域),f,(X)由O(logm) 位组成;②随机选择∫∈F,它将两个不等的串X和Y映射到D中同一元素的概率是很小 的;③对于每个p∈S和B中所有串,应该能够很容易的并行计算f(X)。 上述三个性质中,性质①隐含着f(X)和f(P)可以在1)时间内比较,其中f(x) 被称为串X的指纹;性质②是说,如果两个串X和Y的指纹相等,则X=Y的概率很高:性质 ③主要是针对该算法的并行实现的需求对集合F加以限制。对于串行算法函数∫,只需要满 足前两个性质即可 本节中我们采用了这样一类指纹函数:将取值{0,1}上的串X集合映射到取值整数环Z 上的2×2矩阵。令f(0)和f(1)定义如下 f(0)= f()= 该函数目前只满足性质2,为了使其同时满足性质1需要对该函数作如下更改 令p是区间[1,2,…,M中的一个素数,其中M是一个待指定的整数:令Z是取模p 的整数环。对于每个这样的p,我们定义厂(X)为f()modp,即f1(X)是一个2×2的 矩阵,使得fp(X)的(i,j)项等于f(X)的相应项取模p

7 1.2 随机串匹配算法 1.2.1 随机串匹配及其串行算法 采用上一节所述的 KMP 算法虽然能够找到所有的匹配位置，但是算法的复杂度十分高， 在某些领域并不实用。本节给出了随机串匹配算法，该算法的主要采用了散列（Hash）技术 的思想，它能提供对数的时间复杂度。其基本思想是：为了处理模式长度为 m 的串匹配问题， 可以将任意长为 m 的串映射到 O(logm)整数位上，映射方法须得保证两个不同的串映射到同 一整数的概率非常小。所得到的整数之被视为该串的指纹（Fingerprint），如果两个串的指 纹相同则可以判断两个串相匹配。 1. 指纹函数 本节中假定文本串和模式串取字符集∑={0，1}中的字母。 如上所述，随机串匹配算法的基本策略是将串映射到某些小的整数上。令 T 是长度为 n 的文本串，P 是长度为 m≤n 的模式串，匹配的目的就是识别 P 在 T 中出现的所有位置。考 虑长度为 m 的 T 的所有子串集合 B。这样的起始在位置 i(1≤i≤n-m+1)的子串共有 n-m+1 个。于是问题可重新阐述为去识别与 P 相同的 B 中元素的问题。该算法中最重要的是如何选 择一个合适的映射函数（Mapping Function），下面将对此进行简单的讨论。 令 p p s F f =  { } 是函数集，使得 p f 将长度为 m 的串映射到域 D，且要求集合 F 满足下述 三个性质：①对于任意串 X∈B 以及每一个 p∈S（S 为模式串的取值域）， f (X ) p 由 O（logm） 位组成；②随机选择 f p  F ，它将两个不等的串 X 和 Y 映射到 D 中同一元素的概率是很小 的；③对于每个 p∈S 和 B 中所有串，应该能够很容易的并行计算 f (X ) p 。 上述三个性质中，性质①隐含着 f (X ) p 和 f (P) p 可以在 O(1)时间内比较，其中 f (X ) p 被称为串 X 的指纹；性质②是说，如果两个串 X 和 Y 的指纹相等，则 X=Y 的概率很高；性质 ③主要是针对该算法的并行实现的需求对集合 F 加以限制。对于串行算法函数 p f 只需要满 足前两个性质即可。 本节中我们采用了这样一类指纹函数：将取值{0，1}上的串 X 集合映射到取值整数环 Z 上的 2  2 矩阵。令 f (0) 和 f (1) 定义如下：       =       = 0 1 1 1 (1) 1 1 1 0 f (0) ， f 该函数目前只满足性质 2，为了使其同时满足性质 1 需要对该函数作如下更改： 令 p 是区间[1，2，…，M]中的一个素数，其中 M 是一个待指定的整数；令 Zp 是取模 p 的整数环。对于每个这样的 p，我们定义 f (X ) p 为 f (X )mod p ，即 f (X ) p 是一个 2  2 的 矩阵，使得 f (X ) p 的（i，j）项等于 f (X ) 的相应项取模 p

由此构造的函数∫同时满足前述性质1和2 2.串行随机串匹配算法 用上面定义的指纹函数可以构造一个随机串匹配算法。先计算模式串P(1,m)和子串 T(i,i+m1)的指纹函数(其中1≤i≤nm+1,m≤n),然后每当P的指纹和T(i,i+m-1) 的指纹相等时,则标记在文本T的位置i与P出现匹配。算法描述如下: 算法148串行随机串匹配算法 输入:数组T(1,n)和P(1,m),整数M。 输出:数组 MATCH,其分量指明P在T中出现的匹配位置 Begin (1)for i=l to n-m+l do end for (2)在区间[1,2,…,M中随机的选择一素数,并计算f2(P) (3)for i=l to n-m+l de Li= f,(r(i, i+m-D) end for (4)for i=l to n-m+l do if li=f,(p)then MATCH (i)=l end if end for End 很显然在该算法中步骤(1)和(4)的时间复杂度均为0(n-m);步骤(2)和(3)中 求模式串和文本串各个子串的指纹的时间复杂度分别O(m)和O(n-m) 122随机串匹配的并行算法 对上述串行算法的并行化主要是针对算法14.7中步骤(3)的并行处理,也就是说需要 选择一个合适的函数厂使其同时满足上述三个性质。前面一节给出了同时满足前两个性质 的函数,这里我们主要针对性质3来讨论已得指纹函数类F。 函数类F={Jn}的一个关键性质就是每个J都是同态( Homomorphic)的,即对于任 意两个串X和Y,fp(XY)=J(X)厂()。下面给出了一个有效的并行算法来计算文本串 7中所有子串的指纹。 对于每个1≤i≤mm+1,令N,=J(7(1,1),易得 N,=fp(7()J(7(2)…fp(()。因为矩阵乘法是可结合的,所以此计算就是一种前缀

8 由此构造的函数 p f 同时满足前述性质 1 和 2。 2. 串行随机串匹配算法 用上面定义的指纹函数可以构造一个随机串匹配算法。先计算模式串 P（1，m）和子串 T（i，i+m-1）的指纹函数（其中 1≤i≤n-m+1，m≤n），然后每当 P 的指纹和 T（i，i+m-1） 的指纹相等时，则标记在文本 T 的位置 i 与 P 出现匹配。算法描述如下： 算法 14.8 串行随机串匹配算法 输入：数组 T(1，n)和 P(1，m)，整数 M。 输出：数组 MATCH，其分量指明 P 在 T 中出现的匹配位置。 Begin (1) for i=1 to n-m+1 do MATCH(i)=0 end for (2) 在区间[1，2，…，M]中随机的选择一素数，并计算 f (P) p (3) for i=1 to n-m+1 do Li= f (T(i,i + m −1)) p end for (4) for i=1 to n-m+1 do if Li= f (P) p then MATCH(i)=1 end if end for End 很显然在该算法中步骤（1）和（4）的时间复杂度均为 O（n-m）；步骤（2）和（3）中 求模式串和文本串各个子串的指纹的时间复杂度分别 O（m）和 O（n-m）。 1.2.2 随机串匹配的并行算法 对上述串行算法的并行化主要是针对算法 14.7 中步骤（3）的并行处理，也就是说需要 选择一个合适的函数 p f 使其同时满足上述三个性质。前面一节给出了同时满足前两个性质 的函数，这里我们主要针对性质 3 来讨论已得指纹函数类 F。 函数类 { }p F = f 的一个关键性质就是每个 p f 都是同态（Homomorphic）的，即对于任 意两个串 X 和 Y， f (XY) f (X ) f (Y) P = p p 。下面给出了一个有效的并行算法来计算文本串 T 中所有子串的指纹。 对于每个 1 ≤ i ≤ n-m+1 ， 令 N f (T(1,i)) i = p ，易得 N f (T(1)) f (T(2)) f (T(i)) i = p p  p 。因为矩阵乘法是可结合的，所以此计算就是一种前缀

和的计算;同时每个矩阵的大小为2×2,因此这样的矩阵乘法可以在0(1)时间内完成 所以,所有的M都可以在O(1ogn)时间内,总共使用O(n)次操作计算 定义142:8n(0)=f0)/1 P p-1182(1)=f2(1)= 则乘积 R=g(T()82(T(-1)…g2(()也是一个前缀和计算,并且对于1≤i≤n,它可以 在O(logn)时间内运用O(n)次操作计算。 容易看到,f((,+m-1)=R1N4m,因此,一旦所有的R和M都计算出来了, 则每个这样的矩阵均可在O(1)时间内计算之。所以,长度为n的正文串T中所有长度为m ≤n的子串的指纹均可在O(logn)时间内使用O(n)次操作而计算之 这样,函数同时满足了前述三个性质。在此基础上我们给出了在分布式存储体系结 构上随机串匹配的并行算法。 算法149并行随机串匹配算法 输入:数组(1,n)和P(1,m),整数M。 输出:数组 MATCH,其分量指明P在T中出现的位置 Be (1) for i=l to n-m+l par-do MATCH (i)=0 end for (2)Select a random prime number in [1, 2,", M, then count f,(P) (3)for i=l to n-m+1 par-do Li= f,(T(i, i+m-D) end for ( 4)for i=l to n-m+l par-do if li=f(P)then MATCH (i)=l end if end for End 该并行算法的计算复杂度为O(logn)。处理期间的通信包括在对文本串到各个处理器 的分派,其通信复杂度为O(m/p+m):以及匹配信息的收集,其通信复杂度为O(m/p) MPI源程序请参见所附光盘。 13近似串匹配算法 131近似串匹配及其串行算法 前两节所讨论的串匹配算法均属于精确串匹配技术,它要求模式串与文本串的子串完全

9 和的计算；同时每个矩阵的大小为 2  2 ，因此这样的矩阵乘法可以在 O（1）时间内完成。 所以，所有的 Ni都可以在 O（logn）时间内，总共使用 O（n）次操作计算。 定 义 14.2 ：       − = =       − = = − − 0 1 1 1 , (1) (1) 1 1 1 0 (0) (0) 1 1 p g f p g f p p p p 。则乘积 R g (T(i))g (T(i 1)) g (T(1)) i = p p −  p 也是一个前缀和计算，并且对于 1 i  n ，它可以 在 O（logn）时间内运用 O（n）次操作计算。 容易看到， 1 1 ( ( , 1)) p + m − = Ri− Ni+m− f T i i ，因此，一旦所有的 Ri和 Ni都计算出来了， 则每个这样的矩阵均可在 O（1）时间内计算之。所以，长度为 n 的正文串 T 中所有长度为 m ≤n 的子串的指纹均可在 O（logn）时间内使用 O（n）次操作而计算之。 这样，函数 p f 同时满足了前述三个性质。在此基础上我们给出了在分布式存储体系结 构上随机串匹配的并行算法。 算法 14.9 并行随机串匹配算法 输入：数组 T(1，n)和 P(1，m)，整数 M。 输出：数组 MATCH，其分量指明 P 在 T 中出现的位置。 Begin (1) for i=1 to n-m+1 par-do MATCH(i)=0; end for (2) Select a random prime number in [1，2，…，M]，then count f (P) p 。 (3) for i=1 to n-m+1 par-do Li= f (T(i,i + m −1)) p ; end for (4) for i=1 to n-m+1 par-do if Li= f (P) p then MATCH(i)=1 end if end for End 该并行算法的计算复杂度为 O（logn）。处理期间的通信包括在对文本串到各个处理器 的分派，其通信复杂度为 O（n/p+m）；以及匹配信息的收集，其通信复杂度为 O（n/p）。 MPI 源程序请参见所附光盘。 1.3 近似串匹配算法 1.3.1 近似串匹配及其串行算法 前两节所讨论的串匹配算法均属于精确串匹配技术，它要求模式串与文本串的子串完全

匹配,不允许有错误。然而在许多实际情况中,并不要求模式串与文本串的子串完全精确地 匹配,因为模式串和文本串都有可能并不是完全准确的。例如,在检索文本时,文本中可能 存在一些拼写错误,而待检索的关键字也可能存在输入或拼写错误。在这种情况下的串匹配 问题就是近似串匹配问题 近似串匹配问题主要是指按照一定的近似标准,在文本串中找出所有与模式串近似匹配 的子串。近似串匹配问题的算法有很多,按照研究方法的不同大致分为动态规划算法,有限 自动机算法,过滤算法等。但上述所有算法都是针对一般的近似串匹配问题,也就是只允许 有插入、删除、替换这三种操作的情况。本节中还考虑了另外一种很常见的错误一换位,即 文本串或模式串中相邻两字符的位置发生了交换,这是在手写和用键盘进行输入时经常会发 生的一类错误。为修正这类错误引入了换位操作,讨论了允许有插入、删除、替换和换位四 种操作的近似串匹配问题 1.问题描述: 给定两个长度分别为m和n的字符串A[1,m]和B[1,n],a,b∈∑(1≤i≤m,1≤ ≤n,∑是字母表),串A与串B的编辑距离( Editor distance)是指将串A变成串B所需 要的最少编辑操作的个数。最常见的编辑操作有三种:①插入( Insert),向串A中插入一个 字符:②删除( elete),从串A中删除一个字符:③替换( Replace),将串A中的一个字符 替换成串B中的一个字符。其中,每个编辑操作修正的串A与串B之间的一个不同之处称为 个误差或者错误 最多带k↑误差的串匹配问题(简称为k- differences问题)可描述如下:给定一个 长度为n的文本串T=t…tn,一个长度为m的模式串P=p…pa,以及整数k(k≥1),在文本 串T中进行匹配查找,如果T的某个子串t…t;与模式串P的编辑距离小于等于k,则称在 t;处匹配成功,要求找出所有这样的匹配结束位置t;c 另外一种很常见的编辑操作是换位( Exchange):将串A中的两个相邻字符进行交换。该 操作用于修正相邻两字符位置互换的错误。一个换位操作相当于一个插入操作加上一个删除 操作。但是,当近似匹配允许的最大误差数k一定时,允许有换位操作的情况较之不允许有 换位操作的情况,往往能够找出更多的匹配位置 例如,假定文本串T= abcdefghij,模式串P= bxcegfhy,k=4,问在文本串的第9个字符 处是否存在最多带4个误差的匹配? 首先考虑允许有换位操作的情况,文本串与模式串的对应关系如下: a b g h i j X 其中,①,②,③,④4个位置分别对应于删除、插入、换位和替换操作,可见在ts 处确实有最多带4个误差的匹配。 不允许有换位操作的情况,对应关系如下 ts t9 b x c g 可以看出,在t处不存在最多带4个误差的匹配,因为匹配成功所需要的最少编辑操 作个数为5。 由此可见,允许有换位操作的近似串匹配算法比以往未考虑换位操作的算法更加实用有

10 匹配，不允许有错误。然而在许多实际情况中，并不要求模式串与文本串的子串完全精确地 匹配，因为模式串和文本串都有可能并不是完全准确的。例如，在检索文本时，文本中可能 存在一些拼写错误，而待检索的关键字也可能存在输入或拼写错误。在这种情况下的串匹配 问题就是近似串匹配问题。 近似串匹配问题主要是指按照一定的近似标准，在文本串中找出所有与模式串近似匹配 的子串。近似串匹配问题的算法有很多，按照研究方法的不同大致分为动态规划算法，有限 自动机算法，过滤算法等。但上述所有算法都是针对一般的近似串匹配问题，也就是只允许 有插入、删除、替换这三种操作的情况。本节中还考虑了另外一种很常见的错误—换位，即， 文本串或模式串中相邻两字符的位置发生了交换，这是在手写和用键盘进行输入时经常会发 生的一类错误。为修正这类错误引入了换位操作，讨论了允许有插入、删除、替换和换位四 种操作的近似串匹配问题。 1. 问题描述: 给定两个长度分别为 m 和 n 的字符串 A[1，m]和 B[1，n]，ai，bj∈∑(1≤i≤m，1≤j ≤n，∑是字母表)，串 A 与串 B 的编辑距离（Editor Distance）是指将串 A 变成串 B 所需 要的最少编辑操作的个数。最常见的编辑操作有三种：①插入(Insert)，向串 A 中插入一个 字符；②删除(Delete)，从串 A 中删除一个字符；③替换(Replace)，将串 A 中的一个字符 替换成串 B 中的一个字符。其中，每个编辑操作修正的串 A 与串 B 之间的一个不同之处称为 一个误差或者错误。 最多带 k 个误差的串匹配问题（简称为 k-differences 问题）可描述如下：给定一个 长度为 n 的文本串 T=t1…tn，一个长度为 m 的模式串 P=p1…pm，以及整数 k（k≥1），在文本 串 T 中进行匹配查找，如果 T 的某个子串 ti…tj 与模式串 P 的编辑距离小于等于 k，则称在 tj 处匹配成功，要求找出所有这样的匹配结束位置 tj。 另外一种很常见的编辑操作是换位(Exchange)：将串 A 中的两个相邻字符进行交换。该 操作用于修正相邻两字符位置互换的错误。一个换位操作相当于一个插入操作加上一个删除 操作。但是，当近似匹配允许的最大误差数 k 一定时，允许有换位操作的情况较之不允许有 换位操作的情况，往往能够找出更多的匹配位置。 例如，假定文本串 T=abcdefghij，模式串 P=bxcegfhy，k=4，问在文本串的第 9 个字符 处是否存在最多带 4 个误差的匹配？ 首先考虑允许有换位操作的情况，文本串与模式串的对应关系如下： t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 T: a b c d e f g h i j P: b x c e g f h y ① ② ③ ④ 其中，①，②，③，④ 4 个位置分别对应于删除、插入、换位和替换操作，可见在 t9 处确实有最多带 4 个误差的匹配。 不允许有换位操作的情况，对应关系如下： t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 T: a b c d e f g h i j P: b x c e g f h y ① ② ③ ④ ⑤ 可以看出，在 t9 处不存在最多带 4 个误差的匹配，因为匹配成功所需要的最少编辑操 作个数为 5。 由此可见，允许有换位操作的近似串匹配算法比以往未考虑换位操作的算法更加实用有