改变的，它不带误差地出现在文本串T中，与T的某个（些）子串精确匹配。■
根据上面的引理，我们可设计过滤算法，其原理描述如下： 第1步:
(1) 将模式串P尽可能均匀地划分成2k+1个子模式串P1,P2,…,P2k+1，每个子模式串的长度为??m???2k?1?或??m??m?。 具体地说，如果m=q(2k+1)+r，0≤r＜2k+1，那么可以将模式串P划分成r个长度为??2k?1??2k?1????m?的子模式串。 ??2k?1?的子模式串和(2k+1)-r个长度为?(2) 采用一种快速的精确串匹配算法，在文本串T中查找P1,P2,…,P2k+1这2k+1个子模式串，找到的与某个子模式串P?(1≤?≤2k+1)精确匹配的位置也是可能与整个模式串P发生最多带k个误差的近似匹配的候选位置。
第2步:
采用动态规划算法（算法14.10）验证在各候选位置附近是否真的存在最多带k个误差的近似匹配。假定在第一步中找到了以pj(1≤j≤m)开头的子模式串P?(1≤?≤2k+1)在文本串中的一个精确匹配，且该匹配的起始位置在文本串的ti处，则需要验证从ti-j+1-k到ti-j+m+k之间的文本段T[i-j+1-k, i-j+m+k]。因为在本文所讨论的问题中，允许的编辑操作包括插入，删除，替换和换位，近似匹配允许的最大误差数为k，所以如果在候选位置ti附近存在最多带k个误差的近似匹配，只可能发生在这个长度为m+2k的文本段范围内，超出这个范围，误差数就大于k了。因此在上述情况下，只需要验证T[i-j+1-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+1) (2)
j=1
for ?=1 to 2k+1 do
(3.1) if (?＜=r＝ then len＝? (3)
?m?? 2k?1?? else len＝?
?m? ??2k?1?16
end if
(3.2) for each exact matching position i in T reported by search(T,n,P[j,j+len-1],len) do
check the area T[i-j+1-k, i-j+m+k] end for (3.3) j＝j+len end for End
过滤算法的时间性能与模式串的长度m，近似匹配允许的最大误差数k，以及字母表中各字符出现的概率等因素都密切相关。误差率α定义为近似匹配允许的最大误差数k与模式串长度m的比值，即α=k/m。在误差率α很小的情况下，算法14.11的平均时间复杂度为O（kn）。
3.2 近似串匹配的并行算法
这一节首先介绍扩展近似串匹配过滤算法在PRAM模型上的并行化方法，然后给出了分布式存储模型的并行化过滤算法。
1. 扩展近似串匹配问题的过滤算法在PRAM模型上的并行化
首先假设有p个处理器。由于，最多带k个误差的串匹配问题要求在文本串中找出所有成功匹配的结束位置tj，因此可以将整个问题划分成p个子问题，每个子问题的文本串长度为?=?n/p?（最后一段长度不够可以用特殊字符补齐），用p个处理器并行求解，每个处理器求解一个子问题。子问题i(1≤i≤p)对应于：求结束于t(i-1)?+1,t(i-1)?+2,…,ti?的最多带k个误差的近似匹配。
考虑第i个子问题。由于在定义的扩展近似串匹配问题中，允许的编辑操作包括插入、删除、替换和换位，而允许的最大误差数为k，因此结束于t(i-1)?+1的最多带k个误差的近似匹配的最左起始位置应该是t(i-1)?+1-(k+m-1)。这说明，在求解子问题i(2≤i≤p)时，必须结合前一文本段的最后k+m-1个字符，才能找出所有的匹配位置。
算法14.12 扩展近似串匹配问题的基于PRAM模型的并行化过滤算法 输入：文本串T[1，n]，模式串P[1，m]，近似匹配允许的最大误差数k 输出：所有匹配位置 Begin
(1) ?=?n/p?
(2) K-Diff_Filtration(T[1,?],?,P,m,k)
17
(3) for i=2 to p par-do
K-Diff_Filtration(T[(i-1)?+1-(k+m-1),i?],?+k+m-1,P,m,k) end for End
算法14.12的平均时间复杂度的分析与上一节中串行过滤算法的分析完全类似。此时，用于查找2k+1个子模式串的时间开销为O((2k+1)?+m)+O((2k+1)(?+k+m-1)+m) =O(kn/p+km)，用于验证所有候选位置的时间开销约为2mα/σ
3
1/2α
。通过类似的分析讨论可以得出如下结论：在误差率α很小的情况下，算法
14.12的平均时间复杂度为O(kn/p+km)，其中，n、m、k和p分别是文本串长度、模式串长度、近似匹配允许的最大误差数和算法所使用的处理器个数。
2. 扩展近似串匹配问题的基于分布式存储模型的并行化过滤算法
扩展近似串匹配问题的基于分布式存储模型的并行化过滤算法与前述的基于PRAM模型的并行化过滤算法在设计原理和设计思路上是完全一样的。只不过由于是在分布式存储环境下，文本串和模式串分布存储于不同的处理器上，因此算法中涉及到处理器之间的通信。
算法的设计思路是这样的：将长度为n的文本串T均匀地划分成长度相等且互不重叠的p段（最后一段长度不够可以用特殊字符补齐）。将这p个局部文本串按照先后顺序分布于处理器0到(p-1)上，也就是说，第1个局部文本串放在处理器0上，第2个局部文本串放在处理器1上，……，第p个局部文本串放在处理器p-1上。这样一来，相邻的局部文本串就被分布在相邻的处理器上，而且每个处理器上局部文本串的长度均为?n/p?。算法中假定长度为m的模式串P初始存储于处理器0上，所以必须将它播送到各个处理器上，以便所有处理器并行求解近似串匹配问题。但是根据上小节中的分析，结束位置在各局部文本串（第1个局部文本串除外）的前m+k-1个字符中的那些匹配位置必须跨越该局部文本串才能找到，具体地说，就是必须结合前一局部文本串的最后m+k-1个字符，才能找到结束于这些位置的近似匹配。因此，每个处理器（处理器p-1除外）应将它所存储的局部文本串的最后m+k-1个字符发送给下一处理器，下一处理器接收到上一处理器发送来的m+k-1个字符，再结合自身所存储的长度为?n/p?的局部文本串进行近似匹配查找，就可以找出所有的匹配位置。在播送模式串P到各处理器上，以及发送局部文本串最后m+k-1个字符到下一处理器的通信操作结束之后，各处理器调用K-Diff_Filtration算法并行地进行匹配查找，处理器0求解文本串长度为?n/p?，模式串长度为m的子问题，其它各处理器求解文本串长度为
?n/p?+m+k-1，模式串长度为m的子问题。
算法14.13 扩展近似串匹配问题的基于分布式存储模型的并行化过滤算法 输入：分布存储于处理器Pi上的文本串Ti[1，?n/p?]，
18
存储于处理器P0上的模式串P[1，m]， 近似匹配允许的最大误差数k
输出：分布于各个处理器上的匹配结果 Begin
(1) P0 broadcast m (2) P0 broadcast P[1，m]； (3) for i=0 to p-2 par-do
Pi send Ti[?n/p?-m-k+2,?n/p?] to Pi+1；
end for
(4) for i=1 to p-1 par-do
Pi receive Ti-1[?n/p?-m-k+2,?n/p?] from Pi-1；
end for
(5) P0 call K-Diff_Filtration(T0[1,?n/p?],?n/p?,P,m,k)； (6) for i=1 to p-1 par-do
Pi call K-Diff_Filtration
(Ti-1[?n/p?-m-k+2,?n/p?]+Ti[1,?n/p?],?n/p?+m+k-1,P,m,k)；
end for
End
算法14.13的时间复杂度包括两部分，一部分是计算时间复杂度，另一部分是通信时间复杂度。算法中假定文本串初始已经分布于各个处理器上，最终的匹配结果也分布于各个处理器上。算法的计算时间由算法第(5)步中各处理器同时调用算法14.12（K-Diff_Filtration算法）的时间复杂度构成。根据对算法14.11的平均时间复杂度的分析，在误差率α很小的情况下，算法14.13的平均计算时间复杂度为O（kn/p+km），当模式串长度m远远小于局部文本串长度n/p时，平均计算时间复杂度为O（kn/p）。算法的通信时间由算法第(1)步播送模式串长度m的时间，第(3)步播送模式串P的时间，以及第(4)步发送各局部文本串末尾m+k-1个字符到下一处理器的时间构成。通信时间复杂度与具体采用的播送算法有关。若以每次发送一个字符的时间为单位时间，则通信时间复杂度为O（m+k）。
MPI源程序请参见所附光盘。
19
4. 小结
本章主要讨论了几个典型的并行串匹配算法，关于KMP算法的具体讨论可参考［1］，［2］，［3］，Karp和Rabin在［4］中首先提出了随机串匹配的算法，关于该算法的正确性证明可参阅［5］；文献［6］和［7］分别讨论了近似串匹配，允许由换位操作的近似串匹配算法见文献［8］。
5. 参考文献
1．Knuth D E, Morris J H, Pratt V R. Fast Pattern Matching in Strings. SIAM Journal of Computing, 1977, 6(2):322-350
2．朱洪等. 算法设计与分析. 上海科学技术出版社, 1989
3．陈国良, 林洁, 顾乃杰. 分布式存储的并行串匹配算法的设计与分析. 软件学报, 2002.6, 11(6):771-778
4．Karp R M, Rabin M O. Efficient randomized pattern-matching algorithms. IBM J. Res. Develop., 1987,31(2):249-260
5．陈国良 编著. 并行算法的设计与分析（修订版）. 高等教育出版社, 2002.11
6．Wu S, Manber U. Fast test searching allowing errors. Communications of the ACM, 1993, 35(10):83-91
7．Ricardo B Y, Gonzalo N. Faster Approximate String Matching. In Algorithmica, 1999. 23(2) 8．姚珍. 带有换位操作的近似串匹配算法及其并行实现. 中国科学技术大学硕士论文,2000.5 附录 KMP串匹配并行算法的MPI源程序 1. 源程序gen_ped.c #include
char *string; FILE *fp;
strlen=atoi(argv[1]); pedlen=atoi(argv[2]); srand(atoi(argv[3]));
string=(char*)malloc(strlen*sizeof(char
int strlen,pedlen,suffixlen,num,i,j; ));
20