并行计算实验指导免费版[精编]

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

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

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

4、直到j=m或i=n结束。1. 修改的kmp算法在原算法基础上很多学者作了一些改进工作，其中之一就是重新定义了 kmp算法中的 next函数,即求next函数时不但要求p1, next(j) l=pj(next(j) 1), j-1,而且要求 pnext(j) hpj,记修改后的next函数为newnexto在模式串字符重复高的悄况下修改的 kmp算法比传统kmp算法更加冇效。算法14.1修改的kmp串匹配算法输入：文本串711,山和模式串pl, mj输出：是否存在匹配位置procedure modeifed_kmpbegin(1) i=l,j=l(2) while iwn do(2.1) vv

5、hilej0and pjhti doj=newnextjend while(2.2) ifj=m thenreturn trueelsej=j+l,i=i+lend ifend while(3) return falseend算法14.2 next函数和newnext函数的计算算法 输入：模式$p1, m输出：nextl, m+1和 newnextl, mprocedure nextbegin(1) nextl =0j=2(3) while jm do(3.1) i=nextj-l(3.2) while iho and pihpjl doi=nextiend while(3.3) nextj=

6、i+l(3.4) j=j+lend whileendprocedure newnextbegin(1) newnext( 1 )=0j=2(3) whilejm do(3.1) i=next(j)(3.2) if i=0 orpjhpi+l thennewnextj=ielsencwncxtj=ncwncxtiend if(3.3) j=j+lend whileend2. 改进的kmp算法易知算法14的时间复杂度为o (n),算法14.2的时间复杂度为o (m)。算法14 中所给出的kmp算法只能找到第一个匹配位置，实际应用中往往需要找出所有的匹配位置。 下面给出改进后的算法14.3便解决了这

7、一问题。算法14.3改进kmp串匹配算法输入：文本$711, n和模式串fl, m输出：匹配结果matchl, nprocedure improved_kmpbegin(1) i=l, j=l(2) while iwn do(2.1) while jho and pjhti doj=newnextjjend while(2.2) ifj=m thenmatchi-(m-l)=l j=nextm+l i=i+lelsei=i+lj=j+lend ifend while(3) max_prefix_len=j-1end算法14.4 next函数和newnext函数的计算算法 输入：模式串pl, m

8、输出:nextl, m+1 和 newnext 1, mprocedure nextbegin(1) next l=newnextll j=0j=2(3) while jwm+1 do(3.1) i=nextj-l(3.2) while iho and wiw|j-l) doi=nextiend while(3.3) next|j=i+l(3.4) ifjhm+l thenifwj 7wi+l thennewnextjl=i+lelsenewnextj=newnexti+1end ifend if(3.5) j=j+lend whileend在算法14.3屮，内层while循环遇到成功比较时和

9、找到文本串屮模式串的一个匹配位置 时文木串指针i均加1,所以至多做n次比较；内while循环每次不成功比较时文本串指针i 保持不变，但是模式串指针j减小，所以ij的值增加且上一-次出内循环时的ij值等于下 一次进入吋的值，因此不成功的比较次数不大于ij的值的增加值，即小于n,所以总的比 较次数小于2n,所以算法14.3的时间复杂度为o (n)o算法14.4只比的算法14.2多计算了 next(m+l),至多多做次比较，所以算法14.4的时间复杂度同样为o (m)。2.1.2 kmp串匹配的并行算法1. 算法原理在介绍了改进的kmp串行算法基础上，这一节主要介绍如何在分布存储坏境屮对它进 行实现

10、。设计的思路为：将长为n的文木串t均匀划分成互不重證的p段，分布于处理器0 到p-1中，且使得相邻的文本段分布在相邻的处理器中，显然每个处理器中局部文本段的长 度为 /”(最后一个处理器可在其段尾补上其它特殊字符使其长度与其它相同)。再将长 为m的模式串p和模式串的newnext函数播送到各处理器屮。各处理器使川改进的kmp算 法并行地对局部文木段进行匹配，找到所有段内匹配位置。但是每个局部段(第p-1段除外)段尾nrl字符中的匹配位置必须跨段才能找到。一个 简单易行的办法就是每个处理器(处理器p-1除外)将本局部段的段尾m-1个字符传送给下 处理器，下一处理器接收到前一处理器传來的字符串后，

11、再接合本段的段首m-1个字符 构成一长为2(m-l)的段间字符串，对此字符串做匹配，就能找到所有段间匹配位置。但是算 法的通信量很人，采用下述两种改进通信的方法可以人人地降低通信复杂度：降低播送模 式串和newnext函数的通信复杂度。利用串的周期性质，先对模式串p作预处理，获得其最 小周期长度iui、最小周期个数s及后缀长度ivi(f=usv),只需播送u, s, ivi和部分newnext 两数就口j以了，从而大大减少了播送模式串和newnext函数的通信量。而h串的授小周期和 next函数之间的关系存在着下面定理1所示的简单规律，使得能够设计出常数时间复杂度的 串周期分析算法。降低每个处

12、理器(处理器p-1除外)将木局部文木段的段尾m-1个字符 传送给下一处理器的通信复杂度。每个处理器在其段尾n>l个字符中找到模式串p的最长 前缀串，因为每个处理器上都有模式串信息，所以只需传送该最长前缀串的长度就行了。这 样就把通信量从传送模式串p的最长前缀串降低到传送一个整数，从而大大地降低了通信 复杂度。而且kmp算法结束时模式串指针卜1的值就是文本串尾模式串最大前缀串的长度, 这就可以在不增加时间复杂度的情况下找到此最人前缀串的长度。2. 串的周期性分析定义14.1：给定串p,如果存在字符串u以及正整数k22,使得串p是串/的前缀 (prefix),则称字符串u为串p的周期(per

13、iod)o字符串p的所有周期屮长度最短的周期 称为串p的最小周期(miximal period )o串的周期分析对最终并行算法设计非常关键，串的最小周期和next函数之间的关系存 在着如下定理14所示的简单规律，基于该规律可以设计出常数时间复杂度的串周期分析 算法。定理141：已知串p长为m,则u=m+l-next(m+l)为串p的最小周期长度。算法14.5串周期分析算法输入：nextm+l输出：最小周期长度periodjen 最小周期个数period_num 模式串的后缀长度pattem-suffixlenprocedure period_analysisbeginperiod_len=m+

14、 l-next(m+1)period_num=(int)m/period_len pattern_suffixlen=m mod periodjenend3. 并行算法描述在前述的申行算法以及对其并行实现计的分析的基础上，我们可以设计如下的并行 kmp串匹配算法。算法146并行kmp串匹配算法输入：分布存储的文本串till,/?/ (i=0, 1, 2,，p-1)存储于po的模式串pl，m输出：所有的匹配位置begin(1) po call procedure next/*调用算法 14.4,求模式串 p 的next 函数和 newnext 1*1 数*/po call procedure p

15、eriod_analysis/*调用算法 14.5 分析 p 的周期*/(2) p()broadcast periodjen, period_num, period_suffixlen to other processors /*播送pz最小周期长度、最小周期个数和后缀长度*/p()broadcast p 1, perioden/*不播送 p 之最小周期*/if period_num=l then /*播送p之部分newnext函数，如周期为1,则播送整个 newnext函数；否则播送2倍周期长的newnext函数*/ broadcast newnext 1, melsebroadcast n

16、ewnextl, 2*period_lenend if(3) for i=l to p-1 par-do/*由传送来的p z周期和部分newnext函数重构整个模式串和newnext函数*/pi rebuild new nextend 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 r+iend forfor i=l to p-1 pa

17、r-dopi receive maxprefixlen from p】pi call procedure kmp(ti, p, m-1, maxprefixlen, match+m-1) /*调用算法14.7做段间匹配*/end forend该算法中调用的kmp算法必须重新修改如下，因为做段间匹配吋已经匹配了 maxprefixlen长度的字符串，所以模式串指针只需从maxprefixlen+1处开始。算法14.7重新修改的kmp算法输入 分布存储的文木串和存储于p()的模式串pl m输出：所有的匹配位置procedure kmp(t, p, textlen, matched_num, mat

18、ch)begin(1) i=l(2) j=matched_num+1(3) while iwtcxtlcn do(3.1) 、vhile jho and pjhti doj=newnextjend while(3.2) if j=m thenmatchi-(m-1)=1j=nextm+li=i+lelsej=j+l i=i+lend ifend while(4) maxprefixlen=j 1end下面从计算时间复杂度和通信时间复杂度两个方面来分析该算法的时间复杂度。在分析 计算吋间复杂度吋，假定文本串初始已经分布在各个处理器上，这是合理的，因为文本串一 般很大，不会冇大的变化，只需要分布一

19、次就町以，同时也假定结果分布在各处理器上。木 算法的计算时间由算法步(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)传送最大而缀 串长度纽成，所以通信复杂度与具体采用的播送算法有关。若采川二分树通信技术，则总的通信复杂度为0 (u

20、logp) ompi源程序请参见章末附录。2.2随机串匹配算法2.2.1随机串匹配及其串行算法采用上一节所述的kmp算法虽然能够找到所有的匹配位置，但是算法的复杂度十分高， 在某些领域并不实用。本节给出了随机串匹配算法，该算法的主要釆用了散列(hash)技术 的思想，它能提供对数的时间复杂度。其基本思想是：为了处理模式长度为m的串i兀配问题, 可以将任意长为m的串映射到o(logni)整数位上，映射方法须得保证两个不同的串映射到同 一整数的概率非常小。所得到的整数之被视为该串的指纹(fingerprint),如果两个串的指 纹相同则可以判断两个串相匹配。1. 指纹函数本节中假定文本串和模式串取

21、字符集刀二0, 1小的字母。如上所述，随机串匹配算法的基本策略是将串映射到某些小的整数上。令厂是长度为n 的文本串，p是长度为mwn的模式串，匹配的冃的就是识别p在厂中出现的所冇位置。考 虑长度为m的t的所有子串集合b。这样的起始在位置i(lwiwn-m+1)的子串共有n-时1 个。于是问题可重新阐述为去识别与"相同的中元素的问题。该算法中最重要的是如何选 择一个合适的映射函数(mapping function),下面将对此进行简单的讨论。令f = fppes是函数集，使得几将长度为m的串映射到域，仇要求集合尸满足下述 三个性质：对于任意串xeb以及每一个pws(s为模式串的収值域)

22、，/(x)由o(log刃) 位纟r成；随机选择九g f，它将两个不等的串x和y映射到d屮同一元素的概率是很小 的；对于每个pws和b中所有串，应该能够很容易的并行计算兀(x)。上述三个性质中，性质隐含着九(x)和fp(p)可以在0(1)时间内比较，其中fp(x) 被称为串x的指纹；性质是说，如果两个串乂和丫的指纹相等，贝ijx二y的概率很高；性质 主要是针对该算法的并行实现的需求对集合尸加以限制。对丁伸行算法函数九只需要满 足前两个性质即可。本节中我们釆用了这样一类指纹函数：将取值0, 1±的串x集合映射到取值整数环z 上的2x2矩阵。令/(0)和门1)定义如下：/(0)= !1/(

23、1)=.该函数目前只满足性质2,为了使其同时满足性质1需要对该函数作如下更改： 令q是区间1, 2,，呦中的一个素数，其中m是一个待指定的整数；令九是取模门的整数环。对于每个这样的p，我们定义fp(x)为于(x)modp,即九(x)是一个2x2的矩阵，使得九(x)的(i, j)项等于/(x)的相应项取模6由此构造的函数九同时满足前述性质1和2。2. 串行随机串匹配算法用上面定义的指纹函数可以构造一个随机串匹配算法。先计算模式串户(1, m)和子串 7(i, i+m-1)的指纹函数(其中1 wiwn-m+l, mwn),然后每当p的指纹和t(i, i+m-1) 的指纹相等时，则标记在文本7的位置

24、i与尸出现匹配。算法描述如下：算法14.8串行随机串匹配算法输入：数组7(1, n)和ab m),整数必输出：数组match,其分最指明戶在t中出现的匹配位置。begin(1) for i=l to n-m+1 domatch(i)=0end for(2) 在区间1, 2,，朗中随机的选择一素数，并计算/p)(3) for i=l to n-m+1 doli二 ft(i,i + m-v)end for(4) for i=l to n-m+1 doif li二九(p) thenmatch(i)=1end ifend forend很显然在该算法中步骤(1)和(4)的吋间复朵度均为0(n-m)；步骤

25、(2)和(3)屮 求模式串和文本串各个子串的指纹的时间复杂度分别0 (m)和0 (n-m)o222随机串匹配的并行算法对上述串行算法的并行化主要是针对算法14.7中步骤(3)的并行处理，也就是说盂要 选择一个合适的函数几使其同吋满足上述三个性质。前而一节给出了同时满足前两个性质 的两数，这里我们主要针对性质3來讨论己得指纹两数类函数类f = f)的一个关键性质就是每个九都是同态(homomorphic)的，即对于任意两个串x和y, /p(xr)= /p(x)/p(r)o下而给出了一个有效的并行算法来计算文本串 7中所有子串的指纹。对于每个 1 w i w rrm+1令 nj=fp(t(5n严

26、九(卩)几7(2)九)。因为矩阵乘法是可结合的，所以此计算就是一种前缀和的计算；同时每个矩阵的人小为2x2,因此这样的矩阵乘法可以在0(1)时间内完成。 所以，所有的用都可以在0(log)时间内，总共使用0(n)次操作计算。.t 101. fl /? -11定义14.2：耳(0)=几(0尸二#_ ,gp(l) =几=0。则乘积尺二g“(t(i)g“(t(i l)g“(t(d)也是一个前缀和计算，并冃对于1gs，它可以 在0 (log/;)时间内运用0 (n)次操作计算。容易看到，九(卩心+加1)=心凡+心，因此，一口所有的丘和川都计算出來了， 则每个这样的矩阵均可在0(1)时间内计算之。所以，

27、长度为n的正文串t屮所有长度为m wn的子串的指纹均可在0 (log/;)时间内使用0 (n)次操作而计算z。这样，函数力同时满足了前述三个性质。在此基础上我们给出了在分布式存储体系结 构上随机串匹配的并行算法。算法14.9并行随机串匹配算法输入：数组7(1, n)和尸(1, m),整数m。输出：数组match,其分量指明戶在t中出现的位置。begin(1) for i=l to rrm+1 par-domatch(i)=0;end for(2) select a random prime number in 1, 2, ，旳，then count fp (p) o(3) for i=l to

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

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

30、错课。为修正这类错谋引入了换位操作，讨论了允许有插入、删除、替换和换位四 种操作的近似串匹配问题。1 问题描述：给定两个长度分别为m和n的字符串al, m和bl, n,心，bjw工(1 wiwm, 1w j wn,工是字母表)，串a与串b的编辑距离(editor distance)是指将串a变成串b所需 耍的最少编辑操作的个数。最常见的编辑操作有三种：插入(insert)，向申a屮插入一个 字符；删除(delete),从串a中删除一个字符;替换(replace),将串a中的一个字符 替换成串b中的一个字符。其中，每个编辑操作修正的串a与串bz间的一个不同z处称为 一个误差或者错误。最多带k个误

31、差的串匹配问题(简称为k-differences问题)可描述如下：给定一个 长度为n的文本串t二tih, 一个长度为m的模式串p二p】g以及整数k(k21),在文本 串t中进行匹配査找，如果t的某个子串wtj与模式串p的编辑距离小于等于k,则称在 3处匹配成功，要求找出所冇这样的匹配结束位置tj0另外一种很常见的编辑操作是换位(exchange):将串a屮的两个相邻字符进行交换。该 操作用于修正相邻两字符位置互换的错误。一个换位操作相当于一个插入操作加上一个删除 操作。但是，当近似匹配允许的最大误差数k一定时，允许有换位操作的情况较z不允许有 换位操作的情况，往往能够找出更多的匹配位置。例如，

32、假定文本串t二abcdefghij,模式串p二bxcegfhy, k二4,问在文本串的第9个字符 处是否存在最多带4个误差的匹配？首先考虑允许有换位操作的情况，文本串与模式串的对应关系如下：tlt2t3tlts t6t? tst9tlot:abcde f£ h1jp:bxceg fhx©其中，,，,4个位:置分别刈应于删除、插入、换位和替换操作，可见在t9处确实有最多带4个课差的匹配。不允许有换位操作的情况，对应关系如卜：tl t'2t3 t>|t5 t6t7tstg t iot:a bc d e f gh i jp:b x ceg f h ymbmbmbam

33、 可以看出，在s处不存在最多带4个误差的匹配，因为匹配成功所需要的最少编辑操 作个数为5o由此可见，允许有换位操作的近似串匹配算法比以往未考虑换位操作的算法更加实用有 效。尤其是在文本检索和手写体识别等实际应用屮，新算法的检索成功率和识别率更高，准 确性更好，功能更强。2. k-differences问题的动态规划算法般的k-differences问题的一个著名算法采用了动态规划(dynamic progiamming) 的技术，可以在o(mn)时间内解决该问题。其基本思想是：根据文本串tl, n和模式串 pl, m计算矩阵da如),其中di, j(0wiwm, owjwn)是模式串p的前缀子

34、串p】pi 与文本串t的任意以tj结尾的了串z间的最小误差个数(即最小编辑距离)。显然，如果叽m, j wk,则表明在文本串t的tj处存在最多带k个误差的匹配。di, j由以下公式计算:d0, j=0, owjwndi, 0=i, lwiwmdi, j=min(di-l, j+l, di, jt+l, dit, j-l+ s (pi, tj)其中,s (pi, tj) =0,如果 pi=tj；否则,6 (pi, tj)=lo可以看出，di, j的计算是通过递推方式进行的。d0, j对应于模式串为空串，而文 本串长度为j的情况，显然，空串不需要任何编辑操作就能在文本串的任何位置处匹配，所 以d0

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

36、能取值是di-2, j-2+1,即，将"心变成sti只需要进行一次换位操作，从而最小编辑距离只增加1。由 此可对上述算法进行简单的修改，使之适用于允许有-插入、删除、替换和换位以种编辑操作 的情况。算法14. 10允许有换位操作的k-differences问题的动态规划算法。输入：文本串tl, n,模式串pl, m,近似匹配允许的最大误差数k。输出：所有匹配位置。k-diff_dynamicprogramming(t, n, p, m, k)begin(1) for j=0 to n do do,jj=o end for(2) for i=l to m do di,0=i end f

37、or(3) for i=l to m do(3.1) for j=l to n do(i)if (pij=tjj) thendli,j=di-l,j-lelse if (pi=tj-l and pi-l=tj) thendi,j=min(di-2,j-2+1 ,di-l,j+l ,di,jl +l)elsedri,j=min(di-l,j+l,di,j-l+l,di-l,j-l+l)end ifend if(ii) if (i=m and di,j<=k) then找到p在t屮的一个最多带k个课差的近似匹配, 输出匹配结束位置j；end ifend forend forend显然，该算法

38、的时间复杂度为0 (加)。3. 基于过滤思想的扩展的近似串匹配算法：经典的动态规划算法在实际应用中速度很慢，往往不能满足实际问题的需耍。为此,s. wu 和u. man her以及gonzalo navarro和ricardo baeza yates等人先后提出了多个基于过滤 （filtration）思想的更加快速的近似串匹配算法。这些算法一般分为两步：按照一定的过 滤原则搜索文木串，过滤掉那些不可能发牛匹配的文木段；再进一步验证剩下的匹配候选 位置处是否真的存在成功匹配。由于在第一步中已经滤去了大部分不可能发生匹配的文本 段，因此人人加速了匹配查找过程。在实际应用屮，这些过滤算法一般速度都很

39、快。下面我 们针对前面定义的扩展的近似串匹配问题，讨论了加入换位操作后的k-differences问题的 过滤算法。过滤算法基于这样一种氏观的认识：若模式串p在文木串t的匕处有一个最多带k个 谋差的近似匹配，则p屮必然有一些子串是不带误差地出现在t屮的，也就是说，卩屮必然 有一些子串与t中的某些子串是精确匹配的。引理14. 1：在允许冇换位操作的最多带k个误差的串匹配问题中，如果将模式串p划 分成2k+l段，那么对于p在t中的每一次近似出现（最多带k个误差），这2k+l段屮至少 有一段是不带误差地出现在t中的。证明：这个引理很容易证明。试想，将k个误差，也就是对模式串p所做的k个编辑操 作，分

40、布于2k+l个子模式串屮。由于一个插入，删除或替换操作只能改变一个子模式串， 而一个换位操作有可能改变两个子模式串（例如，在子模式串i的最后一个字符与子模式串 i+1的第一个字符之间进行一次换位操作），所以k个编辑操作最多只能改变2k个子模式串。 这就是说，在这2k+l个了模式串屮，至少有一个是未被改变的，它不带课差地出现在文木 串t中，与t的某个（些）了串精确匹配。根据上面的引理，我们可设计过滤算法，其原理描述如下：第1步：（1）将模式串p尽可能均匀地划分成2k+l个子模式串pi, p2,p2k+i,每个子模式串的长度为科具体地说,如果 m=q(2k+l)+r, 0wrv2k+l,那么可以将

41、模式串p划分成"长度为科的子模式串和帥"个长度为的子模式串。l2e + 1(2) 采用一种快速的精确串匹配算法,在文本串t中查找pi, p2, p2k+i这2k+l个子 模式串，找到的与某个子模式串巴(1£0 w2k+1)精确匹配的位置也是可能与整个模 式串p发生最多带k个误差的近似匹配的候选位置。第2步：采用动态规划算法(算法14.10)验证在各候选位置附近是否真的存在最多带k个误差 的近似匹配。假定在第一步中找到了以pj(lwjwm)开头的子模式串匕(lw0w2k+l) 在文木串屮的一个精确匹配，且该匹配的起始位置在文木串的匸处，则需要验证从 ti-屮到stz

42、间的文木段ti-j+l-k, i-j+m+k。因为在木文所讨论的问题中，允 许的编辑操作包括插入，删除，替换和换位，近似匹配允许的最人谋羌数为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)begi

43、n(1) r=m mod (2k+l)j=l(3) for £=1 to 2k+l dom(3.1) if (0 <=r= then len= 2r + 1else len=_2r + 1_end if(3.2) for each exact matching position i in t reported by search(t,n?pj j+len-1 ,len) docheck the arcati-j+l-k, i-j+m+kend for(3.3) j=j+lenend forend过滤算法的时间性能少模式串的长度m，近似匹配允许的最大误差数k,以及字母表屮 各字符

44、出现的概率等因素都密切相关。误差率。定义为近似匹配允许的最大误差数k与模式 串长度m的比值，即a二k/m。在误差率a很小的情况f，算法14. 11的平均时间复杂度为0 (kn)o2.3.2近似串匹配的并行算法这一节首先介绍扩展近似串匹配过滤算法在pram模型上的并行化方法，然后给出了分 布式存储模型的并行化过滤算法。1. 扩展近似串匹配问题的过滤算法在pram模型上的并行化首先假设冇p个处理器。由于，最多带k个误差的串匹配问题要求在文本串中找出所冇 成功匹配的结束位置切因此可以将整个问题划分成p个子问题，每个子问题的文本串长度 为nlp(最后一段长度不够可以用特殊字符补齐)，用p个处理器并行求

45、解，每个处 理器求解一个子问题。子问题i (lwiwp)对应于:求结束于t(卄2,，竝的最多带 k个谋差的近似匹配。考虑第i个子问题。由于在定义的扩展近似皿匹配问题中，允许的编辑操作包括插入、 删除、替换和换位，而允许的最大误差数为k,因此结束于tn 的最多带k个误差的近似 匹配的最左起始位置应该是这说明，在求解子问题i (2wiwp)时，必须结合 询一文本段的最后k+m-1个字符，才能找出所有的匹配位置。算法14. 12扩展近似串匹配问题的基于pram模型的并行化过滤算法输入：文本串tl, n,模式串pl, m,近似匹配允许的最大误碧数k输出：所有匹配位置begin(1) £ =

46、n/p'(2) k-d辻f_f订tration(tl, £, , p, m, k)(3) for i=2 to p par-dok-diff_filtration(t(i-1) f, +1 -(k+mt), i 0 , 0 +k+m-l, p, m, k) end forend算法14.12的平均时间复杂度的分析与上一节中串行过滤算法的分析完全类似。此时, 用于査找2k+l个子模式串的时间开销为0(2k+l) i +m)+0(2k+l) ( h +k+m-l)+m) 二0(kn/p+kni),用于验证所有候选位置的时间开销约为2m3a/o1/2通过类似的分析讨论可 以得出如下

47、结论：在误差率a很小的情况下，算法14. 12的平均时间复杂度为0kn/pkni), 其屮，n、叭k和p分别是文本串长度、模式串长度、近似匹配允许的最大谋差数和算法所 使用的处理器个数。2. 扩展近似串匹配问题的基于分布式存储模型的并行化过滤算法扩展近似串匹配问题的基于分布式存储模型的并行化过滤算法与前述的基于pram模型 的并行化过滤算法在设计原理和设计思路上是完全一样的。只不过由于是在分布式存储坏境 下，文木串和模式串分布存储于不同的处理器上，因此算法中涉及到处理器之间的通信。 算法的设计思路是这样的：将长度为n的文本串t均匀地划分成长度相等且互不重叠的p 段(最后一段长度不够可以用特殊字

48、符补齐)。将这p个局部文本串按照先后顺序分布丁处 理器0至lj(p-l)±,也就是说，第1个局部文木串放在处理器0上，第2个局部文本串放在 处理器1上，第p个局部文本串放在处理器p-1上。这样一来，相邻的局部文本串就 被分布在相邻的处理器上，阳且每个处理器上局部文本串的长度均为n/p 算法中假定 长度为m的模式串p初始存储于处理器0上，所以必须将它播送到各个处理器上，以便所有 处理器并行求解近似串匹配问题。但是根据上小节中的分析，结束位置在各局部文本串(笫 1个局部文本串除外)的前m+k-l个字符屮的那些匹配位登必须跨越该局部文本串才能找到, 具体地说，就是必须结合前一局部文木串的最

49、fti m+k-1个字符，才能找到结束于这些位置的 近似匹祀。因此，每个处理器(处理器p-l除外)应将它所存储的局部文木串的最后m+k-l 个字符发送给下一处理器，下一处理器接收到上一处理器发送来的m+k-l个字符，再结合白 身所存储的长度nlp的局部文木串进行近似匹配查找，就可以找出所侑的匹配位置。在播送模式串p到各处理器上，以及发送局部文木串最后m+k-1个字符到下一处理器的通信 操作结束z后，各处理器调用k-diff_filtration算法并行地进行匹配查找，处理器0求解 文本串长度为n/pf模式串长度为m的子问题，其它各处理器求解文本串长度为n/p-| im+k-l,模式串长度为m的

50、了问题。算法14. 13扩展近似串匹配问题的基于分布式存储模型的并行化过滤算法输入：分布存储于处理器pi上的文本串并1,"/"，存储于处理器p。上的模式串戶1, m,近似匹配允许的最大误差数k输出：分布于各个处理器上的匹配结果begin(1) po broadcast m(2) po broadcast pl, m；(3) for i二0 to p-2 par-dopi send ti / 一m-k+2, p? / p| to pi+i；end for(4) for i=l to p-1 par-dopi receive tii/p-m-k+2,/ from pi-i；en

51、d for(5) po call k-diff_filtration(t°l,斤/p, /p,p,m, k)；(6) for i=l to p-1 par-dopi call k-dif仁filtration(ti-i/p -m-k+2, nl p|+til, nl p|, nl p+m+kt, p, m, k)；end forend算法14. 13的时间复杂度包括两部分，一部分是计算时间复杂度，另一部分是通信时间 复杂度。算法中假定文本串初始已经分布丁各个处理器上，最终的匹配结果也分布丁各个处 理器上。算法的计算时间由算法笫步中各处理器同时调用算法14. 12 (k-diff_fi

52、ltration算法)的时间复杂度构成。根据对算法14. 11的平均时间复杂度的分 析，在谋差率a很小的情况下，算法14. 13的平均计算时间复杂度为0kn/p+km),当模式 串长度m远远小于局部文本串长度n/p时，平均计算时间复杂度为0 (&必)。算法的通信 时间由算法第步播送模式串长度m的时间，第步播送模式串p的时间，以及第(4)步 发送各局部文木串末尾m»k-l个字符到下一处理器的时间构成。通信时间复杂度与具体采川 的播送算法有关。若以每次发送一个字符的时间为单位时间，则通信时间复杂度为05+k)°mpi源程序请参见所附光盘。2.4小结木章主要讨论了几个典型

53、的并行串匹配算法，关于kmp算法的具体讨论可参考1, 2, 3, karp和rabin在4屮首先提出了随机串匹配的算法，关于该算法的正确性 证明可参阅5；文献6和7分别讨论了近似串匹配，允许山换位操作的近似串匹配 算法见文献8o参考文献1 . knuth d e, morris j h, pratt v r. fast pattern matching in strings. siam journal ofcomputing, 1977, 6(2):322-3502 .朱洪等.算法设计与分析.上海科学技术出版社，19893 .陈国良，林洁，顾乃杰.分布式存储的并行串匹配算法的设计与分析.软件学

54、报,2002.6,11(6):771- 7784 . kaip r m, rabin m o. efficient randomized pattern-matching algorithms. ibm j. res.develop., 1987,31(2):249-26()5 .陈国良编著.并行算法的设计与分析(修订版).高等教育出版社,2002.116 . wu s, manber u. fast test searching allowing errors. communications of the acm, 1993,35(10):83-917 . ricardo b y, gonz

55、alo n. faster approximate string matching. in algorithmica, 1999. 23(2)8 .姚珍.带冇换位操作的近似串匹配算法及其并行实现.中国科学技术大学硕士论文,2000.5附录kmp串匹配并行算法的mpi源程序1 源程序 gen_ped.c#include <stdio.h>#include <stdlib.h>#include <malloc.h>#include <string.h>/*根据输入参数生成模式串*/int main(int argc,char *argvj)int strlenjiedlen.suffixlen.numjj; char string;file *fp;strlen=atoi(iirgv 1);pedlen=atoi(argvf2);srand(atoi(argv3);string=(char*)manoc(strlen*sizeof(char)； if(string=null)printf(hmalloc errornh); exit(l);for(i