并行KMP算法的研究

周昊 韩彦李斌 殷晓玲

摘要：对KMP算法做出了分析，针对模式串出现在主串较靠后位置这一特殊情况提出对KMP算法的改进算法：并行KMP算法.这一算法在此特殊情况下显著地减小了算法的时间复杂度.

关键词：模式匹配;KMP算法;并行算法

中图分类号：TP301  文献标识码：A  文章编号：1673-260X（2019）05-0030-03

1 引言

字符串的模式匹配是对字符串的基本操作之一，广泛应用于生物信息学、信息检索、拼写检查、语言翻译、数据压缩、网络入侵检测等领域，如何简化其复杂性一直是算法研究中的经典问题.字符串的模式匹配实质上就是寻找模式串P是否在主串T中，且其出现的位置.现如今我们对字符串匹配的效率的要求越来越高，应不断地改良模式匹配算法，减少其时间复杂度.

2 相关模式匹配算法分析（n为主串长，m为模式串长）

2.1 BF（Brute Force）算法

BF算法的思想是将主串T中的第一个字符与模式串P中的第一个字符比较，若相等那么继续比较T中的第二个字符与模式串P中的第二个字符.若匹配过程中发生不匹配，那么T的第二个字符（下一个字符）与P中的第一个字符比较.重复此过程，若最终P的全部字符匹配成功那么返回本趟匹配的T中的起始位置，否则匹配失败.算法如下：

Abstract BF：

int start=0，j=0，i;

i=start;

While（i<n && j<m）

{

If（T[i]==p[j]）

{i++;j++;}

else

{start++;i=start;j=0}

}

If（j==m）return start+1;

else No found;

此种方法也被称为蛮力算法.例：

第一趟：T： a b a b c a b d a

P： a b c

第二趟：T： a b a b c a b d a

P： a b c

第三趟：T： a b a b c a b d a

P： a b c

在第三趟匹配成功，可以看出主串中i不断回溯，在这过程中很多比较都是无谓的，所以这种算法效率很低，时间复杂度为O（n+m）.

2.2 KMP算法

KMP算法是由D.E.Knuth、J.H.Morris和V.R.Pratt创造的算法，该算法减少了BF算法中i回溯所进行的无谓操作，极大地提高了算法的效率.算法如下：

Abstract get_next：

int j=-1，i=0，next[0]=-1;

while（i<m）

{

if（j==-1 || P[i]==P[j]）

{

i++;j++;

if（P[i]==P[j]）

next[i]=next[j];

else

next[i]=j

}

else

j=next[j];

}

Abstract KMP：

int next[]，i=-1，j=-1;

get_next（P，next）;

while（i<n && j<m）

{

if（j==-1 || T[i]==P[j]）

{i++;j++;}

else

j=next[j];

if（j==m）return i-j;

}

if（j<m） No found;

例：

第一趟：T： a b c a b d b b d

P： a b d

第二趟：T： a b c a b d b b d

P： a b d

第三趟：T： a b c a b d b b d

P： a b d

可以看出，get_next算法是該匹配算法的核心，通过next数组可以让模式串在失配时快速地向右移动，主串中i也不用回溯.遍历模式串得到next数组，所以时间复杂度是O（m），模式串在主串中的匹配过程由于模式串每次移动的长度j-next[j]与i的移动距离大致相当，所以匹配的时间复杂度是与主串长成线性关系，为O（n）[1].综上，该模式匹配算法的复杂度为O（m+n）.

3 并行KMP算法

假设模式串出现在主串的尾部，按照KMP算法需要从第一个开始一直匹配到最后一个开始，需要遍历整个主串.现提出并行KMP算法同时在主串的末尾开始匹配，既然要从末尾开始匹配，那么就需要新的数组从m串的末尾开始记录前后缀的长度，有两种选择：1.存储一个新串，使新串为原模式串的逆序，再调用get_next函数得到next2数组记录前后缀长度[2].2.定义新的get_nextrev函数，直接从模式串的尾部开始通过调用get_nextrev获得新的nextrev数组记录前后缀长度.这两种方法明显后者优于前者，因为方法1还得额外存储一个字符串浪费空间[3].get_next函数伪代码如下：

Abstract get_next：

{

int j=-1，i=0，next[0]=-1;

while（i<m）

{

if（j==-1 || P[i]==P[j]）

{

i++;j++;

if（P[i]==P[j]）

next[i]=next[j];

else

next[i]=j

}

else

j=next[j];

}

get_nextrev函数伪代码如下：

Abstract get_nextrev：

{int k，i=0，j=-1;

k=m-1;

while（k+i>0）

{

if（j==-1 || P[k+i]==P[k-j]）

{

i--;

j++;

if（P[k+i]==P[k-j]）

nextrev[-i]=nextrev[j];

else

nextrev[-i]=j;

}

else

j=nextrev[j];

}

}

}

并行KMP算法偽代码如下：

{

int sstart1，sstart2，wstart1，wstart2，k，pos1，pos2;

get_next（P，next1）;

get_nextrev（P，next2）;

sstart1=-1;

sstart2=n;

wstart1=-1;

wstart2=m;

if（m==1）

{

for（k=0;k<n;k++）

{

if（w==s[k]）

return k+1;

else：

return -1;

}

}

while（sstart1 < n && wstart1< m && sstart2>=0 && wstart2>=0）

{

if（wstart1==-1 || s[sstart1]==w[wstart1]）

{

wstart1+=1;

sstart1+=1;

}

else

wstart1=next1[wstart1];

if（wstart1==m）

return sstart1-m;

if（wstart2==m || s[sstart2]==w[wstart2]）

{

wstart2-=1

sstart2-=1

}

else

wstart2=m-1-next2[m-1-wstart2];

if（wstart2==-1）

return sstart2+2;

if（sstart1+1==sstart2）

{

pos1=sstart2;

pos2=sstart1;

}

if（sstart2<=pos2）

if（pos2-sstart2<m-1）

if（wstart2>=m-1-（pos2-1）-1）

return -1;

if（pos2-sstart2>=m-1）

return -1;

if（sstart1>=pos1）

if（sstart1-pos1<m-1）

if（wstart1<=sstart1-pos1）

return -1;

if（sstart1-pos1>=m-1）

return -1;

}

}

例：

T： a b a b b a d c c a b a c b c a

P： a b a                   a b a

首尾同时匹配，最终成功的位置在第1个字符，共比较5次，近似等于KMP需要比较的3次.

T： a b a b b a d c c a b a c b c a

P： d c c                  d c c

首尾同时匹配，最终成功的位置在第8个字符，共比较18次，大于KMP所需比较的9次

T： a b a b b a d c c a b a c b c a

P： b c a                  b c a

首尾同时匹配，最终成功的位置在第14个字符，共比较8次;远小于KMP需要比较的20次.

可以看出匹配成功的位置pos=n-km+1，随着k的增大，并行KMP算法的时间复杂度在增加，KMP算法的时间复杂度在减小.

若K>n/2m+1/m时：

主串中副串前部分的字符出现的概率越小，并行KMP算法的時间复杂度就越接近KMP算法的时间复杂度.

若K>n/2m+1/m时：

主串中副串后部分的字符出现的概率越小，并行KMP算法相对于KMP算法对时间复杂度的优化效果越明显[4].

由于在最坏情况下依然要遍历整个主字符串，所以并行KMP的时间复杂度是O（n+2m）.但是当模式串出现在主字符串越靠后的位置时（远大于m/2），提前匹配成功的可能性越大，字符串匹配效率大大提高[5].

4 结束语

随着计算机科学的发展，对模式串匹配效率的要求不断提高，我们应不断研究如何提高模式串匹配效率这一问题.本文介绍的改进算法是针对模式串所在主串位置较靠后这一特殊情况，该算法从串头和串尾同时开始匹配，相当于是并行运行，在大量处理字符串匹配时优化效果明显.

参考文献：

〔1〕严蔚敏，吴伟民.（C语言版）数据结构[M].清华大学出版社，1996.

〔2〕周雅翠，孙磊.基于KMP算法的next函数理解与分析[J].吉林建筑大学学报，2012，29（1）：79-82.

〔3〕杨俊丽，吕晓燕，满晰.基于改进的KMP算法的词频统计[J].微计算机信息，2010，26（27）：161-162.

〔4〕孟晓笑.KMP算法的并行研究[J].湖北第二师范学院学报，2011，28（2）：20-21.

〔5〕李艳鵾，付维娜，刘帅，等.并行系统中KMP串匹配算法的实现[J].制造业自动化，2011，33（2）：189-191.