并行计算实验指导(1)版

1、大家支持免费共享2串匹配串匹配(string matching)问题是计算机科学屮的一个基本问题，也是复杂性理论中研 究的最广泛的问题么一。它在文字编辑处理、图像处理、文献检索、白然语言识别、生物学 等领域有着广泛的应川。而h,串匹配是这些应川屮最耗时的核心问题，好的串匹配算法能 显著地提高应用的效率。因此，研究并设计快速的申匹配算法具有重要的理论价值和实际意 义。串匹配问题实际上就是一种模式匹配问题，即在给定的文本串中找出与模式串匹配的子 串的起始位置。最基本的串匹配问题是关键词匹配(keyword matching)。所谓关键词匹配, 是指给定一个长为n的文本串71b n和长为m的模式串p

2、l, m,找出文本串t中与模式 串所有精确匹配的子串的起始位置。申匹配问题包括精确串匹配(pcifccl siring matching)> 随机串匹配(randomized string malching)和近似串匹配(approximate string matching)。 另外还有多维串匹配(multidimensional string matching)和硬件串匹配(haidware string matching)等。本章中分别介绍改进的kmp串匹配算法，采用散列技术的随机串匹配算法，基于过滤 算法的近似串匹配算法，以及它们的mpi编程实现。2.1 kmp串匹配算法2.1.

3、1 kmp串匹配及其串行算法kmp算法首先是由d.e. knuth> j.h. morris以及v.r. pratt分别设计出来的，所以该算 法被命名为kmp算法。kmp串匹配算的基木思想是：对给出的的文木串tl, n与模式 串pl, m,假设在模式匹配的进程中,执行71i和啲匹配检查。若ti=pj»则继续 检查ti+1和pj+1是否匹配。若则分成两种情况：若j=i,则模式串右移一位, 检查w+1j和pl是否匹配;若1 vjwm,则模式串右移j-next位,检查hijfil pnext(j)j 是否匹配(其中next是根据模式串pl, m的本身局部匹配的信息构造而成的)。重复此

4、过 程直到j=m或i=n结束。修改的kmp算法在原算法基础上很多学者作了一些改进工作，其中z就是重新定义了 kmp算法中的 next函数，即求next函数时不但要求pl, next(j) l=pj(next(j) 1), j-1,而且要求 pnext(j)记修改后的next函数为newnexto在模式串字符重复高的情况卜修改的kmp算法比传统kmp算法更加有效。算法141修改的kmp串匹配算法输入：文本串71, n和模式串pl, m输出：是否存在匹配位置procedure modeifed_kmpbegini=l,j=lwhile in dowhile j h0 and pjhti doj=n

5、ewnextjend whileif j=m thenreturn trueelsej=j+l,i=i+lend ifend whilereturn falseend算法14.2 next函数和newnext函数的计算算法 输入：模式串pl，m输出：nextl, m+1和 newnextl, mprocedure nextbegin(1) nextl=0j=2(3) whilejm do(3.1) i=nextj-l(3.2) while iho and pihpjl doi=nextiend while(3.3) next|j=i+l(3.4) j=j+lend whileendproced

6、ure newnextbeginnewnext(l)=oj=2(3) whilejm do(3.1) i=next(j)(3.2) if i=0 or pjhpi+l thennewnext fj=ielsenewnextj=newnextiend if(3.3) j=j+lend whileend改进的kmp算法易知算法14的时间复杂度为o (n),算法14.2的时间复杂度为o (m)。算法14 中所给出的kmp算法只能找到第一个匹配位置，实际应用中往往需要找出所有的匹配位置。 下面给出改进后的算法14.3便解决了这一问题。算法143改进kmp串匹配算法输入：文本串tl, n和模式串pl,

7、m输出：匹配结果matchfl, nprocedure imp rove d_kmpbegini=l, j=lwhile in dowhile jho and pjhti doj=newnextjend whileif j=m thenmatchi-(m-1)=1j=nextm+li=i+lelsei=i+lj=j+lend ifend whilemax_prefix_len=j-lend算法14.4 next函数和newnext函数的计算算法输入：模式串pl, m输出：nextl, m+1和 newnext1, mprocedure nextbegin(ii) nextlj=newnextl

8、j=o(iii) j=2(iv) while jwm+1 doiv. i=nextj-liv. while iho and wihwjl) doi=ncxlfiend whileiv. nextj=i+liv. if jhm+l thenifwj wi+1 thennewnextj=i+lelsenewnextj=newnexti+l end ifend ifiv. j=j+lend whileend在算法14.3中，内层while循环遇到成功比较时和找到文木串中模式串的一个匹配位置 时文本串指针i均加1，所以至多做n次比鮫；内while循环每次不成功比4交时文本申指针i 保持不变，但是模式串

9、指针j减小，所以i-j的值增加且上一次出内循环时的i-j值等于下 次进入时的值，因此不成功的比较次数不大于ij的值的增加值，即小于n,所以总的比 较次数小于2n,所以算法14.3的时间复杂度为0 5)。14.4只比的算法14.2多计算了 next(m+l),至多多做ml次比较，所以算法14.4的时间复杂度同样为0 (m)。2.1.2 kmp串匹配的并行算法1. 算法原理在介绍了改进的kmp申行算法基础上，这一节主耍介绍如何在分布存储坏境中对它进 行实现。设计的思路为：将长为n的文本串7均匀划分成互不重叠的p段，分布于处理器0 到pl中，且使得相邻的文本段分布在相邻的处理器中，显然每个处理器中局

10、部文本段的长 度为n/p (最后一个处理器可在其段尾补上其它特殊字符使其氏度与其它相同)。再将氏 为m的模式串p和模式串的newnext函数播送到各处理器中。各处理器使用改进的kmp算 法并行地对局部文本段进行匹配，找到所有段内匹配位置。但是每个局部段(第p-1段除外)段尾m-1字符中的匹配位置必须跨段才能找到。一个 简单易行的办法就是每个处理器(处理器p-1除外)将木局部段的段尾m-1个字符传送给下 一处理器，下一处理器接收到前一处理器传來的字符串后，再接合本段的段怜m-1个字符 构成一长为2(m-l)的段间字符串，对此字符串做匹配，就能找到所有段间匹配位置。但是算 法的通信量很大，采用下述

11、两种改进通信的方法口j以大大地降低通信复杂度：降低播送模 式串和newnext函数的通信复杂度。利用串的周期性质，先对模式串p作预处理，获得其最 小周期长度iui、最小周期个数s及后缀长度ivi(p=usv),只需播送u, s, ivi和部分newnext 函数就可以了，从而大大减少了播送模式串和newnext函数的通信量。而ii串的最小周期和 next函数z间的关系存在着下血定理1所示的简单规律，使得能够设计出常数时间复朵度的 串周期分析算法。降低每个处理器(处理器p-1除外)将木局部文本段的段尾个字符 传送给下一处理器的通信复杂度。每个处理器在其段尾m-1个字符中找到模式串p的最长 前缀串

12、，因为每个处理器上都有模式串信息，所以只需传送该最长前缀串的长度就行了。这 样就把通信量从传送模式串p的最长前缀串降低到传送一个整数，从而人人地降低了通信 复杂度。而h.kmp算法结束时模式串指针j-1的值就是文木串尾模式串最人前缀串的长度, 这就可以在不增加时间复杂度的情况下找到此最大前缀串的长度。2. 串的周期性分析定义14.1：给定串p,如果存在字符串u以及正報数kn2,使得串p是串/的前缀 (prefix),则称字符串u为串p的周期(period)。字符串p的所有周期屮长度最短的周期 称为串p的最小周期(miximal period )o串的周期分析对最终并行算法设计非常关键，串的最小

13、周期和next函数z间的关系存 在着如下定理14.1所示的简单规律，基于该规律可以设计出常数时间复杂度的串周期分析 算法。定理14.1：已知串p长为m,则u=m+lnext(m+l)为串p的最小周期长度。算法14.5串周期分析算法输入：nextm+l 输出：最小周期t度pcriod_lcn最小周期个数period_num模式串的后缀长度pattern-suffixlenprocedure period_analysisbeginperiod_len=m+1 -next(m+1)period_num=(int)m/period_lenpattern_suffixlen=m mod period_

14、lenend3. 并行算法描述在前述的串行算法以及对其并行实现计的分析的皋础上，我们可以设计如下的并行 kmp串匹配算法。算法146并行kmp串匹配算法输入：分布存储的文木串tj1, n/ p (i=0, 1, 2,，p-1)存储于po的模式串pl, m输出：所有的匹配位置begin(1) pocall procedure next /*调用算法 14.4,求模式串 p 的next两数和newnext函数*/po call procedure period_analysis /*调川算法 14.5 分析 p 的周期*/(2) po broadcast period_len, period_nu

15、m, period_suffixlen to other processors /*播送pz最小周期长度、最小周期个数和后缀长度*/po broadcast p 1, period_len /*不播送 p 之最小周期*/if period_num=l then /*播送p之部分newnext函数，如周期为1,则播送整个 newnext函数；否则播送2倍周期长的newnext函数*/ broadcast newnext i, melsebroadcast newnext 1, 2*period_lenjend if(3) for i=l to p-1 par-do /*由传送来的p之周期和部分n

16、ewnext函数重构整个模式串和newnext函数*/pi rebuild newnextend forfor i=l 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-dopi send maxprefixlen to pj+end forfor i=l to pl par-dopi receive maxprefixlen from pmpi call procedure kmp(ti, p, m-

17、1, maxprefixlen, match+m-1) /*调用算法14.7做段间匹配*/end forend该算法中调用的kmp算法必须重新修改如下，因为做段间匹配时已经匹配了 maxprefixlen长度的字符串，所以模式串指针只需从maxprefixlen+1处开始。算法14.7重新修改的kmp算法输入：分布存储的文本串和存储于p()的模式串pl，m输出：所有的匹配位置procedure kmp(t, p, textlen, matchednum, match)begini=lj=matched_num+1while iwtextlen dowhile jho and pjhti doj

18、=newnextjend whileif j=m thenmatchi-(m-l)=lj=nextm+li=i+lelsej=j+li=i+lend ifend whilemaxprefixlen=j1end下而从计算吋间复杂度和通信吋间复杂度两个方而来分析该算法的吋间复杂度。在分析 计算吋间复杂度吋，假定文木串初始已经分布在各个处理器上，这是合理的，因为文本串一 般很大，不会有大的变化，只需要分布一次就可以，同吋也假定结果分布在各处理器上。本 算法的计算时间由算法步(1)中所调川的算法14.4的时间复杂度o (m)和算法14.5的时 间复杂度o(1);算法步(3)和算法步(4)所调用的改进的

19、kmp算法14.7的时间复朵度 o (n/p)和o (m)构成。所以本算法总的计算时间复杂度为o (n/p+m)o通信复杂度中算 法步(2)播送模式串信息(最小周期串u及最小周期长度、周期个数和后缀长度三个整数) 和newnext函数(长度为2u的整数数组，u为串u的长度)以及算法步(4)传送最人前缀 串长度组成，所以通信复杂度与具体采川的播送算法有关。若采川二分树通信技术，则总的 通信复杂度为o (ulogp)。mpi源程序请参见章末附录。2.2随机串匹配算法2.2.1随机串匹配及其串行算法采用上一节所述的kmp算法虽然能够找到所有的匹配位置，但是算法的复杂度十分高， 在某些领域并不实用。本

20、节给出了随机串匹配算法，该算法的主要采用了散列(hash)技术 的思想，它能提供对数的时间复杂度。其基本思想是：为了处理模式长度为m的串匹配问题， 可以将任意长为m的串映射到o(logm)整数位上，映射方法须得保证两个不同的串映射到同 -整数的概率非常小。所得到的整数之被视为该串的指纹(fingerprint),如果两个串的指 纹相同则可以判断两个串相匹配。1. 指纹函数本节中假定文本串和模式串取字符集e = 0, 1中的字母。如上所述，随机串匹配算法的基本策略是将串映射到某些小的整数上。令厂是长度为n 的文木串，戶是长度为mwn的模式串，匹配的目的就是识别p在厂中出现的所有位置。考 虑长度为

21、m的7的所有子串集合b。这样的起始在位置i (1 wi wn-in+1)的子串共if n-m+1 个。于是问题可重新阐述为去识别与户相同的屮元素的问题。该算法屮最重要的是如何选 择一个合适的映射函数(mapping function),下面将对此进行简单的讨论。令f = 呻是函数集，使得匚将长度为0)的串映射到域，且要求集合f满足下述 三个性质：对于任意串xeb以及每一个pgs(s为模式串的取值域),/x)由0(log/) 位组成；随机选择仁訂,它将两个不等的串x和y映射到d中同一元素的概率是很小 的；对丁每个pes和b中所有串，应该能够很容易的并行计算/"(x)。上述三个性质中，性

22、质隐含着几(x)和f/p)可以在0(1)时间内比较,其中九(x) 被称为串x的指纹；性质是说，如果两个串x和y的指纹相等，则x=y的概率很高；性质 主要是针对该算法的并行实现的需求对集合尸加以限制。对于串行算法函数.几只需要满 足前两个性质即可。本节中我们采用了这样一类指纹函数：将取值0, 1上的串x集合映射到取值整数环z 上的2x2矩阵。令/(0)和/定义如下：1 0 1 1/(0)=, 广=1 1j_0 1该函数目前只满足性质2,为了使其同时满足性质1需要对该函数作如下更改：令p是区间1, 2,，旳中的一个索数，其中m是一个待指定的整数；令是取模卩的整数环。对于每个这样的p，我们定义九(x

23、)为/(x)modp,即九(x)是一个2x2的矩阵，使得九(x)的(i, j)项等于/(x)的相应项取模小山此构造的函数乙同时满足前述性质1和2。2. 串行随机串匹配算法用上而定义的指纹函数可以构造一个随机串匹配算法。先计算模式串7(1, m)和子串 t(i, i+m-1)的指纹函数(其中lwiwn-m+1, mwn),然后每当戶的指纹和r(i, i+m-1) 的指纹相等时，则标记在文本t的位置i与户出现匹配。算法描述如下：算法14.8串行随机串匹配算法输入：数组al, n)和p(l, m),整数必输出：数组match,其分量指明p在厂卩出现的匹配位置。begin(1) for i=l to

24、n-m+1 domatch(i)=0end for(2) 在区间1, 2,，网屮随机的选择一素数，并计算fp(p)(3) for i=l to r)-m+l doli二+end for(4) for i=l to n-m+1 doif li=/p(p) thenmatch(i)=lend ifend forend很显然在该算法中步骤(1)和(4)的时间复杂度均为(n-m)；步骤(2)和(3)中 求模式串和文本串各个子串的指纹的时间复杂度分别0 (m)和0 (n-m)o2.2.2随机串匹配的并行算法对上述串行算法的并行化左要是针对算法14. 7中步骤(3)的并行处理，也就是说需要 选择一个合适的

25、函数./；,使其同时满足上述三个性质。前面一节给岀了同时满足前两个性质 的函数，这里我们主要针对性质3来讨论已得指纹函数类凡函数类f = fp 的一个关键性质就是每个fp都是同态(homomorphic)的，即对于任 意两个串x和y, fp(xy) = fp(x)fp(y)o下而给出了一个有效的并行算法来计算文木串 卩中所有子串的指纹。对于每个 1 w i w n-m+1,令,易得a. = fp (t(l)/; (t(2)- - - fp (t(i) o因为矩阵乘法是可结合的,所以此计算就是一种前缀 和的计算；同时每个矩阵的大小为2x2,因此这样的矩阵乘法可以在0(1)时间内完成。 所以，所有

26、的"；都可以在0 (log/?)吋间内，总共使用0 (n)次操作计算。定义 14.2 : g (0) = / (0)"=1 i=九(1尸=："j o 则乘积_p-i 1j|_01/?, =£“(7°)£”(丁0_1).£“(丁(1)也是一个前缀和计算，并且对于它可以 在0 (log/7)时间内运用0 (n)次操作计算。容易看到，几(t(i,i + fn v) = ringt，因此，一旦所有的丘和.m都计算出来了， 则每个这样的矩阵均可在0(1)时间内汁算乙 所以，长度为n的正文串7'中所有长度为m wn的子串的指纹均

27、可在(log/2)时间内使用0(n)次操作而计算之。这样，函数同时满足了前述三个性质。在此基础上我们给出了在分布式存储体系结 构上随机串匹配的并行算法。算法14.9并行随机串匹配算法输入：数组厂(1, n)和p(l, m),整数m。输出：数组match,其分量指明戶在t中出现的位置。beginfor i=l to n-m+1 par-domatch(i)=0;end forselect a random prime number in 1, 2, ，旳，then count f/f (p) 0for i=l to n-m+1 par-doli二 fp(t(i,i + m-v);end forf

28、or i=l to n-m+1 par-doif li= fp(p) thenmatch(i)=lend ifend forend该并行算法的计算复杂度为0(log/2)。处理期间的通信包括在对文本串到各个处理器 的分派，其通信复杂度为0 5/p+m)；以及匹配信息的收集，其通信复杂度为0(必)。mpi源程序请参见所附光盘。2.3近似串匹配算法2.3.1近似串匹配及其串行算法前两节所讨论的串匹配算法均属于精确串匹配技术,它要求模式串与文本串的子串完全 匹配，不允许有错谋。然而在许多实际情况中，并不要求模式串与文木串的子串完全精确地 匹配，因为模式串和文本串都有可能并不是完全准确的。例如，在检索

29、文本时，文本中可能 存在一些拼写错误，而待检索的关键字也可能存在输入或拼写错误。在这种情况下的串匹配 问题就是近似串匹配问题。近似串匹配问题主要是指按照一定的近似标准，在文本串中找出所有与模式串近似匹配 的子串。近似串匹配问题的算法有很多，按照研究方法的不同大致分为动态规划算法，有限 自动机算法，过滤算法等。但上述所有算法都是针对一般的近似串匹配问题，也就是只允许 有插入、删除、替换这三种操作的情况。本节屮还考虑了另外一种很常见的错误一换位，即, 文本串或模式串屮相邻两字符的位置发牛了交换，这是在手写和用键盘进行输入时经常会发 牛的一类错误。为修正这类错误引入了换位操作，讨论了允许有插入、删除

30、、替换和换位四 种操作的近似串匹配问题。1 问题描述：给定两个长度分别为m和n的字符串al, ni和131, n, b.d (lwiwm, lwj wn,刀是字母表)，串a与串b的编辑距离(editor distance)是指将串a变成串b所需 要的最少编辑操作的个数。最常见的编辑操作有三种：插入仃nsert),向串a中插入一个 字符;删除(delete),从串a中删除一个字符;替换(replace),将串a中的一个字符 替换成串b中的一个字符。其中，每个编辑操作修正的串a与串bz间的一个不同之处称为 一个误差或者错误。最多带k个误差的串匹配问题(简称为k-differences问题)可描述如

31、下：给定一个 长度为n的文本串t=ti-tn, 一个长度为m的模式串p二pip“*以及整数k(knl),在文本 串t中进行匹配查找，如果t的某个子串titj与模式串p的编辑距离小于等于k,贝u称在 tj处匹配成功，要求找出所有这样的匹配结束位置tj。另外一种很常见的编辑操作是换位(exchange) :a屮的两个相邻字符进行交换。该操作川于修正相邻两字符位置互换的错谋。一个换位操作相当于一个插入操作加上一个删除 操作。但是，当近似匹配允许的最大误差数k一定时，允许有换位操作的情况较z不允许有 换位操作的情况，往往能够找!li更多的匹配位置。例如，假定文本串l-abcdefghij,模式串p=b

32、xcegfhy, k二4,问在文本串的第9个字符 处是否存在最多带4个误差的匹配？首先考虑允许有换位操作的情况，文本串与模式串的对应关系如下：tl t2t1ts teto tiot:ab .cde f£ h1jp:b_ ceg fh其中，,，,4个位置分别对应丁删除、插入、换位和替换操作，可见在t9处确实有故多带4个误差的匹配。 不允许有换位操作的情况，对应关系如下：11 t2t：? t4 t$ t6 t7tg 110t:a bc d e f gh i j j ap:bc.e.gfhh 可以看出，在t9处不存在最多带4个误差的匹配，因为匹配成功所需要的最少编辑操 作个数为5。山此可见

33、，允许有换位操作的近似串匹配算法比以往未考虑换位操作的算法更加实用有 效。尤其是在文木检索和手写体识别等实际应用中，新算法的检索成功率和识别率更高，准 确性更好，功能更强。2. k-differences问题的动态规划算法-般的k-differenccs问题的一个著名算法釆用了动态规划(dynamic programming) 的技术，可以在o(nin)时间内解决该问题。其基本思想是：根据文本串tl, n和模式串 pl, m计算矩阵1治|)如)，其中di, j (owiwm, owjwn)是模式串p的前缀子串p】pi 与文木串t的任意以t结尾的子串之间的最小谋差个数(即最小编辑距离)。显然，如

34、果dm, j wk,则表明在文本串t的tj处存在最多带k个误差的匹配。di, j由以下公式计算:d0, j二0, owjwndi, 0=i, lwiwmdi, j=min(di-l, j+l, di, jl + l, di-1, j-l+6 (pi, tj)其中,s (pi, tj) =0,如果 pi二切 否则，6 (pi, tj) =1 o可以看出，叽i, j的计算是通过递推方式进行的。d0, j对应于模式串为空串，而文 本串长度为j的情况，显然，空串不需要任何编辑操作就能在文本串的任何位置处匹配，所 以d0, j二0。di, 0对应于模式串长度为i,而文本串为空串的情况，此时，至少需要对

35、模式串进行i次删除操作才能与文本串(空串)匹配，所以di, 0=io在计算di, j时, di-1, j, di, j-1, di-1, j-l都已计算出,di-1, j+l, di, j-1j+1, di-1, j-l + s (p：, tj分别对应于对模式串进行插入、删除、替换操作的情况,由于di, j是最小编 辑距离，所以取三者中的最小值。上述动态规划算法只考虑了插入、删除、替换三种编辑操作，但很容易将其推广到允许 有换位操作的情况。考虑di, j的计算，若pi-ipi=titi-i,则di, j的一个可能取值是di-2, j-2+l,即，将ppi变成tis只需要进行一次换位操作，从而最

36、小编辑距离只增加1。由 此可对上述算法进行简单的修改，使之适用于允许有插入、删除、替换和换位山种编辑操作 的情况。算法14. 10允许有换位操作的k-differences问题的动态规划算法。输入：文本串tl, n,模式串pl, m,近似匹配允许的最大误差数k。输出：所有匹配位置。k-diff_dynamicprogramming(t, n, p, m, k)begin(1.0) for j=0 to n do do,jj=o end for(2.0) for i=l to m do di,0=i end for(3.0) for i=l to m do(3) for j=l to n do(

37、i)if(pi=tj) thendi,j=di-l,j-lelse if(pi=tj-l and pi-l=tj) thendi,j=min(di-2,j-2+l,dm,j+l,dij-l+l)elsedi,j=min(di-l,j+l,di,j-l+l,di-l,j-l+l)end ifend ifif (i=m and di,j<=k) then找到p在t中的一个坟多带k个误差的近似匹配, 输岀匹配结束位置j；end ifend forend forend显然，该算法的时间复杂度为0(/刀)。3. 基于过滤思想的扩展的近似串匹配算法：经典的动态规划算法在实际应川中速度很慢，往往不能满

38、足实际问题的需要。为此,s.wu 和u. manber以及gonzalo navarro和ricardo baeza-yates等人先后提出了多个基于过滤 (filtration)思想的更加快速的近似串匹配算法。这些算法一般分为两步：按照一定的过 滤原则搜索文本串，过滤掉那些不可能发生匹配的文木段；再进一步验证剩下的匹配候选 位置处是否真的存在成功匹配。由于在第一步屮已经滤去了人部分不可能发生匹配的文木 段，因此大大加速了匹配查找过程。在实际应用中，这些过滤算法一般速度都很快。下而我 们针对前面定义的扩展的近似串匹配问题，讨论了加入换位操作后的k-differences问题的 过滤算法。过滤算

39、法基丁这样一种直观的认识：若模式串p在文本串t的tj处有一个最多带k个 误差的近似匹配，则p中必然有一些子串是不带谋差地出现在t中的，也就是说，p中必然 有一些子串与t中的某些子串是粕确匹配的。引理14.1：在允许有换位操作的最多带k个误差的串匹配问题中，如果将模式串p划 分成2k+l段，那么对于p在t中的每一次近似出现(最多带k个误差)，这2k+l段中至少 有一段是不带误差地出现在t中的。证明：这个引理很容易证明。试想，将k个误差，也就是对模式串p所做的k个编辑操 作，分布于2k+l个子模式串屮。由于一个插入，删除或替换操作只能改变一个子模式串， 而一个换位操作有可能改变两个子模式串(例如，

40、在子模式串i的最后一个字符与子模式串 i+1的第一个字符z间进彳亍一次换位操作)，所以k个编辑操作绘多只能改变2k个子模式串。 这就是说，在这2k+l个子模式串中，至少有一个是未被改变的，它不带误差地出现在文本 串t中，与t的某个(些)子串精确匹配。根据上面的引理，我们可设计过滤算法，其原理描述如下：第1步：(1)将模式串p尽可能均匀地划分成2k+l个子模式串pi, p2,p2k+i,每个子模式巾的长度为那么可以将模式串p划分成r个长度为2r+1的子模式串和(2k+l)-r个长度为具体地说,如果 m二q(2k+l)+r, 0wrv2k+l,m_2r + 1_的子模式串。(2)釆用一种快速的精确

41、串匹配算法,在文本串t中查找pb p2,-,p2k+i这2k+l个子 模式串，找到的与某个子模式串pf(lw 0 w2k+1)精确匹配的位置也是可能为整个模 式串p发生最多带k个误差的近似匹配的候选位置。第2步：采用动态规划算法(算法14. 10)验证在各候选位置附近是否真的存在最多带k个误差 的近似匹配。假定在第一步中找到了以pj (1w j wm)开头的子模式串pf (1w t w2k+1) 在文本串中的一个精确匹配，且该匹配的起始位置在文本串的心处，则需要验证从 ti-j+i到ti卄k之间的文木段ti-j+l-k, i-j+m+k 0因为在本文所讨论的问题中，允 许的编辑操作包括插入，删

42、除，替换和换位，近似匹配允许的最人课差数为k,所以 如果在候选位置b附近存在最多带k个误差的近似匹配，只可能发生在这个长度为 m+2k的文本段范围内，超岀这个范围，误差数就大于k了。因此在上述情况下，只需 要验证ti-j+l-k, i-j+m+k就足够了。算法14. 11允许有换位操作的k-differences问题的过滤算法。输入：文木串t (长度n),模式串p (长度m),近似匹配允许最人误差数k。输出：所有匹配位置。k-diff_filtration(t, n, p, m, k)begin(1) r=m mod (2k+l)j=l for £=1 to 2k+l do(3.l)

43、 if(x十 then len=else len=_2r + 1_end if(3) for each exact matching position i in t reported by search(t9n,pj,j+len-lljen) docheck the areatij+l-k, i-j+m+kend for(3) j=j+lenend forend过滤算法的吋间性能与模式串的长度m,近似匹配允许的最大谋差数k,以及字母表中 各字符出现的概率等因素都密切相关。误差率a定义为近似匹配允许的最大误差数k与模式 串长度m的比值，即a =k/nio在误差率a很小的情况下，算法14. 11的

44、平均时间复杂度为0 (kn)o2.3.2近似串匹配的并行算法这一节首先介绍扩展近似串匹配过滤算法在pram模型上的并行化方法，然后给岀了分 布式存储模型的并行化过滤算法。扩展近似串匹配问题的过滤算法在pram模型上的并行化首先假设有p个处理器。由于，最多带k个误差的串匹配问题要求在文木串中找出所有 成功匹配的结束位置口，因此可以将整个问题划分成p个子问题，每个子问题的文本串长度 为(最后一段长度不够可以用特殊字符补齐)，用p个处理器并行求解，每个处 理器求解一个子问题。子问题i (lwiwp)对应于：求结束于tie, t(i-o+2,，t“的最多带 k个误差的近似匹配。考虑第i个子问题。由于在

45、定义的扩展近似串匹配问题屮，允许的编辑操作包括插入、 删除、替换和换位，而允许的最大误差数为k,因此结束于的最多带k个课差的近似 匹配的最左起始位置应该是do这说明，在求解子问题i (2wiwp)时，必须结合 询一文本段的最后k+m-1个字符，才能找出所有的匹配位置。算法14. 12扩展近似串匹配问题的基于pram模型的并行化过滤算法输入：文木串tl, n,模式串pl, m,近似匹配允许的最人课差数k输出：所有匹配位置begin = n/pkdiff_filtration(tl, 0, 0,p, m, k)for i=2 to p par-dokdi ff filtrat ion(t (i-1

46、) 0 +1 - (k+m-1), i 0 , £ +k+mt, p, m, k)end forend算法14. 12的平均时间复杂度的分析与上一节屮串行过滤算法的分析完全类似。此时, 用于査找2k+l个子模式串的时间开销为0(2k+l) t +m)+0(2k+l) ( £ +k+m-l)+m) 二mkn/p+炯,用于验证所有候选位置的时间开销约为2m3a/o ,/2通过类似的分析讨论可 以得出如下结论：在误差率a很小的情况下，算法14. 12的平均时间复杂度为o(kn/p+k血, 其中，n、叭k和p分别是文本串长度、模式串长度、近似匹配允许的最大误差数和算法所 使川的处理

47、器个数。扩展近似串匹配问题的基于分布式存储模型的并行化过滤算法扩展近似串匹配问题的基于分布式存储模型的并行化过滤算法与前述的基丁 pram模型 的并行化过滤算法在设计原理和设计思路上是完全一样的。只不过由丁是在分布式存储环境 下，文本串和模式串分布存储于不同的处理器上，因此算法中涉及到处理器之间的通信。 算法的设计思路是这样的：将长度为n的文木串t均匀地划分成长度相等且互不重叠的p 段(最后一段氏度不够可以用特殊字符补齐)。将这p个局部文本串按照先后顺序分布于处 理器0到(p-l)上，也就是说，第1个局部文本串放在处理器0上，第2个局部文木串放在 处理器1上，第p个局部文本串放在处理器p-1上

48、。这样一来，相邻的局部文本串就 被分布在和邻的处理器上，而且每个处理器上局部文本串的长度均为n/p.算法中假定 长度为m的模式串p初始存储于处理器0上，所以必须将它播送到各个处理器上，以便所有 处理器并行求解近似串匹配问题。但是根据上小节屮的分析，结束位置在各局部文木串(第 1个局部文本串除外)的前m+k-1个字符屮的那些匹配位置必须跨越该局部文木串才能找到, 具体地说，就是必须结合前一局部文木审的最后m+k-1个字符，才能找到结束于这些位置的 近似匹配。因此，每个处理器(处理器p-1除外)应将它所存储的局部文本串的最后m+k-1 个字符发送给下一处理器，下一处理器接收到上一处理器发送来的m+

49、k-1个字符，再结合自 身所存储的长度为/的局部文本串进行近似匹配查找，就可以找出所有的匹配位置。在播送模式串p到各处理器上，以及发送局部文本串瑕后m+k-1个字符到下一处理器的通信 操作结束之后，各处理器调用k-diff_filtration算法并行地进行匹配查找，处理器0求解 文本串长度为"/,模式串长度为m的子问题，其它各处理器求解文木串长度为nl p|+m+k-l,模式串长度为m的子问题。算法14. 13扩展近似串匹配问题的基于分布式存储模型的并行化过滤算法输入：分布存储于处理器上的文本串zl,/，存储于处理器p°上的模式串凤1, ni,近似匹配允许的最大误差数k输

50、出：分布于各个处理器上的匹配结果beginpo broadcast mpo broadcast p1, m；for i=0 to p-2 par-dopi send ti“/“-m-k+2,/ to pin；end forfor i二1 to p-1 par-dopi receive ti-iz?/p |-m-k+2,/ from p：-i：end forpo call k-diff_filtration (tol,n / p|, p? / p, p,叫 k)；for i二1 to p-1 par-dopi call k-diff_f订tration(ti-i/?/p"|-m-k+2

51、, nt p"|+til, nl p|, n! p+m+kt, p, m, k)；end forend算法14.13的吋间复杂度包括两部分，一-部分是计算吋间复杂度，另一部分是通信吋间 复杂度。算法中假定文本串初始已经分布于各个处理器上，最终的匹配结果也分布于各个处 理器上。算法的计算时间由算法第步中各处理器同时调用算法14. 12 (k-diff_filtration算法)的时间复杂度构成。根据对算法14. 11的平均时间复杂度的分 析，在误差率a很小的情况下，算法14. 13的平均计算时间复杂度为0 (kn/p+hn),当模式 串长度m远远小于局部文本串长度n/p时，平均计算时间

52、复杂度为0 (kn/p)o算法的通信 时问由算法第(1)步播送模式串长度m的时间，第(3)步播送模式串戶的时i'可，以及第(4)步 发送各局部文木串末尾m+k-1个字符到下一处理器的时间构成。通信时间复杂度与具体采川 的播送算法有关。若以每次发送一个字符的时间为单位时间，则通信时间复杂度为05m)。mpi源程序请参见所附光盘。2.4小结本章主要讨论了几个典型的并行串匹配算法，关于kmp算法的具体讨论叮参考1, 2, 3, karp和rabin在4屮首先提出了随机串匹配的算法，关于该算法的正确性 证明可参阅5；文献6和7分别讨论了近似串匹配，允许由换位操作的近似串匹配 算法见文献8。参考

53、文献1 . knuth d e, morris j h, pratt v r. fast pattern matching in strings- siam journal ofcomputing, 1977, 6(2):322-3502 .朱洪等.算法设计与分析.上海科学技术出版社,1989.陈国良，林洁，顾乃杰.分布式存储的并行串匹配算法的设计与分析.软件学报,2002.6, 11(6):771-778(1) . karp r m, rabin m o. efficient randomized pattematching algorithms. ibm j. res.develop.,

54、1987,31(2):249-260(2) .陈国良编著.并行算法的设计与分析(修订版)高等教育出版社,2002.11(3) . wu s, manber u fast test searching allowing errors communications of the acm, 1993,35(10):83-91(4) . ricardo b y, gonzalo n. faster approximate string matching. in algorithmica, 1999. 23(2)(5) .姚珍.带有换位操作的近似串匹配算法及其并行实现.中国科学技术大学硕士论文,2000

55、.5附录kmp串匹配并行算法的mpi源程序源程序 genjded.c#include <stdio.h>#include <stdlib.h>#include <malloc.h># include <string.h>/*根据输入参数生成模式串*/int main(int argc,char *argv)int strlen,pedlen,suftlxlen,num,ij; char string:file *fp;strlcn=atoi(argv 1 );pedlen=atoi(argv2);srand(atoi(argv 3);string=(char*)malloc(strle n*sizeof(char); if(string=null)printf(hmalloc eitornn); exit(l);)for(i=0; i<pedlen; i+)num=rand()%26;1for(j=l;j<(int)(strlen/pedlen);j+) strncpy(string4j*pedlen,string,pedlen);if(suffixlen=strlen%pe