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}是函数集,使得∫将长度为m的串映射到域D,且要求集合F满足下述 三个性质:①对于任意串X∈B以及每一个p∈S(S为模式串的取值域),fn(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(1)= 该函数目前只满足性质2,为了使其同时满足性质1需要对该函数作如下更改 令p是区间[1,2,…,M中的一个素数,其中M是一个待指定的整数:令Z是取模p 的整数环。对于每个这样的p,我们定义厂(X)为f(X)modp,即fp(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,(T(, 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)=Jn(XJn(Y)。下面给出了一个有效的并行算法来计算文本串 7中所有子串的指纹。 对于每个1≤i≤mmn+1,令N=f((,1),易得 N=fp(T(1)J2((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 。因为矩阵乘法是可结合的，所以此计算就是一种前缀