第1页 / 共22页
第2页 / 共22页
第3页 / 共22页
第4页 / 共22页
第5页 / 共22页
第6页 / 共22页
第7页 / 共22页
第8页 / 共22页
KMP串匹配算法，并行计算.docx
1.2 串匹配
1.1KMP串匹配算法
1.1.1KMP串匹配及其串行算法
1. 修改的KMP算法
2. 改进的KMP算法
1.1.2KMP串匹配的并行算法
1. 算法原理
2. 串的周期性分析
3. 并行算法描述
1.2随机串匹配算法
1.2.1随机串匹配及其串行算法
1. 指纹函数
2. 串行随机串匹配算法
1.2.2随机串匹配的并行算法
1.3近似串匹配算法
1.3.1近似串匹配及其串行算法
1. 问题描述:
2. k-differences问题的动态规划算法
3. 基于过滤思想的扩展的近似串匹配算法:
1.3.2近似串匹配的并行算法
1. 扩展近似串匹配问题的过滤算法在PRAM模型上的并行化
2. 扩展近似串匹配问题的基于分布式存储模型的并行化过滤算法
1.4小结
参考文献
附录 KMP串匹配并行算法的MPI源程序
1. 源程序gen_ped.c
2. 源程序 kmp.c
3. 运行实例
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=newnext[j]
end while
(2.2)if j=m then
else
return true
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
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)
(2) while i≤n do
i=1，j=1
(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]
3
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 中，且使得相邻的文本段分布在相邻的处理器中，显然每个处理器中局部文本段的长
pn / （最后一个处理器可在其段尾补上其它特殊字符使其长度与其它相同）。再将长
度为
为 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 所示的简单规律，基于该规律可以设计出常数时间复杂度的串周期分析
4
算法。
定理 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，
存储于 P0 的模式串 P[1，m]
pn /
]（i=0，1，2，…，p-1）
输出：所有的匹配位置
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]
if period_num=1 then
/*不播送 P 之最小周期*/
/*播送 P 之部分 newnext 函数，如周期为 1，则播送整个
newnext 函数；否则播送 2 倍周期长的 newnext 函数*/
broadcast newnext [1，m]
else
broadcast newnext[1，2*period_len]
end if
for i=1 to p-1 par-do
(3)
Pi rebuild newnext
end for
for i=1 to p-1 par-do
/*由传送来的 P 之周期和部分 newnext 函数重构整个模式串
和 newnext 函数*/
/*调用算法 14.7 做局部段匹配，并获得局部段尾最大前缀串
之长度*/
Pi call procedure KMP(T，P ，n ，0，match)
end for
(4) for i =0 to p-2 par-do
5
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 源程序请参见章末附录。
6
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），下面将对此进行简单的讨论。
令
F
{
pf
}
sp
是函数集，使得 pf 将长度为 m 的串映射到域 D，且要求集合 F满足下述
三个性质：①对于任意串 X∈B 以及每一个 p∈S（S为模式串的取值域），
(Xf p
)
由 O（logm）
位组成；②随机选择
f p ，它将两个不等的串 X 和 Y 映射到 D 中同一元素的概率是很小
F
的；③对于每个 p∈S 和 B 中所有串，应该能够很容易的并行计算
(Xf p
)
。
上述三个性质中，性质①隐含着
(Xf p
)
和
(Pf p 可以在 O(1)时间内比较，其中
)
(Xf p
)
被称为串 X 的指纹；性质②是说，如果两个串 X 和 Y 的指纹相等，则 X=Y 的概率很高；性质
③主要是针对该算法的并行实现的需求对集合 F加以限制。对于串行算法函数 pf 只需要满
足前两个性质即可。
本节中我们采用了这样一类指纹函数：将取值{0，1}上的串 X 集合映射到取值整数环 Z
上的 22 矩阵。令 )0(f 和 )1(f 定义如下：
f
)0(
01
11
，
f
)1(
11
10
该函数目前只满足性质 2，为了使其同时满足性质 1 需要对该函数作如下更改：
令 p是区间[1，2，…，M]中的一个素数，其中 M 是一个待指定的整数；令 Zp 是取模 p
是一个 22 的
的整数环。对于每个这样的 p，我们定义
(
Xf
)
mod
，即
p
(Xf p
)
为
(Xf p
)
矩阵，使得
(Xf p
)
的（i，j）项等于
(Xf
)
的相应项取模 p。
7
由此构造的函数 pf 同时满足前述性质 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]中随机的选择一素数，并计算
(Pf p
)
(3) for i=1 to n-m+1 do
miiTf p
,((
Li=
))1
end for
(4) for i=1 to n-m+1 do
if Li=
(Pf 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）的并行处理，也就是说需要
选择一个合适的函数 pf 使其同时满足上述三个性质。前面一节给出了同时满足前两个性质
的函数，这里我们主要针对性质 3 来讨论已得指纹函数类 F。
函数类
F
{ pf
}
的一个关键性质就是每个 pf 都是同态（Homomorphic）的，即对于任
意两个串 X 和 Y，
f
P
(
XY
)
T中所有子串的指纹。
)(
YfXf
p
)
(
p
。下面给出了一个有效的并行算法来计算文本串
对于每个 1≤i≤n-m+1，令
N
i
Tf
p
,1((
i
))
，易得
N
i
Tf
p
))1((
Tf
p
))2((
iTf
p
))((
。
因为矩阵乘法是可结合的，所以此计算就是一种前缀和的计算；同时每个矩阵的大小为 22 ，
因此这样的矩阵乘法可以在 O（1）时间内完成。所以，所有的 Ni都可以在 O（logn）时间
8
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
