【摘 要】本文采用mpich2这一并行处理的环境，并用mpich2并行处理串匹配问题，研究了随机算法的优点及用途，并用它解决串匹配，降低串匹配的时间复杂度。
【关键词】并行算法；随机算法1 串匹配问题提出
Kmp算法虽然能找到匹配位置，但是时间复杂度高，在某些领域还不能用，能否找到一种时间复杂度为对数数量级的匹配函数。
2 问题分析
我们在这里采用数据结构中散列函数的方法，它可提供较低的时间复杂度，把一个长的串映射到较小的范围，保证不同的串映射到相同的位置概率很小。所得到的指纹函数可在O（1）时间复杂度内进行比较。
3 问题解决
指纹函数：我们求串的匹配的基本策略是将串映射到某些小的整数上。令T是长度为n的正文串，P是长度为m的模式串，匹配的结果是识别P在T中出现的所有位置。考虑长度为m的T所有子串的集合B。这样的起始在位i的子串共n-m+1个。于是我们的问题可重新阐述为去识别与P相同的B中元素的位置。令A={fp}p∈s是函数集，使得fp将长度为的串映射到域D.A要满足下属三个性质：
性质（1） 对于任意串x∈B和每个p∈S，fp（ｘ）由O（log m）位组成。
性质（2） 随机选择fp∈A，它将两个不等的串X和Y映射到到同一位置的机率非常小。
性质（3） 对于每个p∈S和B中的所有串，应能很容易计算fp（ｘ）。
上述三个性质对于模式匹配问题的内涵应是清楚的：性质1隐含着fp（ｘ）可在时间O（1）内比较，性质2是说如果两个串X和Y指纹相等，则X=Y的概率很高；性质3 的解释与利用集合A的并行算法实现有关。
因为确定的串匹配的时间复杂度为O（logn）时间和O（n）次操作，所以希望计算中诸串的指纹函数亦具有相同的时间复杂度。
3.1 一类指纹函数
试考虑下列函数：它将取值{0，1}上的串集合映射到取值整数环z上的2×2矩阵。此函数满足性质2，但不满足性质1，3。稍后修改它，使其满足所有性质。对于任意两个串行x和y定义为环z上矩阵集合的乘积。
引理（1） 函数f是一到一的，使得对于任意串x，f（X）的行列式为1。如果X的长度为m，则f（x）的每一项都是一个不大于Fm+1的整数，其中Fm+1是m+1个Fibonnacci数，F1=F1=1, Fm+1= Fm+1+Fm+1。
3.2 失配概率
令X和Y是两个长度各为m的串，且令fp∈A。当X≠Y但fp（X）=fp（Y）时就出现失配。注意此性质与特定的指纹函数fp有关。
定理 令fp是从集合A={fp}中随机选定的函数，其中p是区间[1,2…,M]中的某一素数，那么任意两个长度为m的不同串失配概率≦∏（2.776）/∏（m），如果m≧11。
引理（2） 如果素数的区间为（1,2…, mk）对于与给定的常数k>1，则两个长度为m的串的失配概率≦3.48k/mk-1。
区间[1,2…, M]中的一个素数p，对于固定的k要求O（logm+logt）位。对于t这样的串，指向它们特定位置的指针亦要求同数量级的位数，因此，能够假定两个的串的指纹可在O（1）时间内比较之。显然，此值与比较两串需要O（m）次操作是大不一样的。
这样，函数同时满足前述性质。在此基础上给出了分布式存储处体系结构上随机串匹配的并行算法。
随机串匹配算法
算法1.1（下转第140页）
（上接第170页）随机串匹配算法
输入: 数组T（1,n） P（1,m）和整数M
输出: 数组match ,其分量指明P在T中出现的匹配位置
（１）for i=1 to n-m+1 do
match[i]=0;
end for
（２）select a randon prime number in [1,2.....m],then count fp（p）
（３）for i=1 to n-m+1 do
Li=fp（T（i,i+m-1））
end for
（４）for i=1 to n-m+1 do
if Li=fp（p）then
match（i）=1
end if
end for
end
显然，在该算法中步骤（1）（4）的时间复杂度为O（n-m），步骤（2）（3）中求模式串和文本串各个子串指纹的时间复杂度分别为O（m），O（n-m）。
［责任编辑：王洪泽］
推荐访问： 并行 数值 算法 研究 软件
