ikr

一种改进的KR模式匹配算法

尚俊平;刘合兵

【摘要】在分析BF、KMP和KR等模式匹配算法的基础上提出一种改进的KR算

法(IKR),在产生哈希冲突时利用双向比较法进行匹配.实验结果表明,该算法可以快速

有效地进行模式匹配.%BadonanalysisofBF,KMPandKR,animproved

gorithmcomparesstringsin

nintheexperimentalresults,

theIKRalgorithmneedsfewertimestocompare,anditifficientfor

patternmatching.

【期刊名称】《河南科学》

【年(卷),期】2012(030)004

【总页数】4页(P473-476)

【关键词】模式匹配;BF算法;KMP算法;KR算法;IKR算法

【作者】尚俊平;刘合兵

【作者单位】河南农业大学计算机科学与技术系,郑州450046;河南农业大学计算

机科学与技术系,郑州450046

【正文语种】中文

【中图分类】TP391.1

随着计算机网络的迅速发展，模式匹配的应用越来越广泛.在信息检索、网络安全

入侵检测、数据处理和语言翻译等方面，都离不开模式匹配技术[1].

目前已提出很多模式匹配算法，如BF（Brute－Force）算法、KMP（Knuth－

Morris－Pratt）算法[2]、KR（Karp－Rabin）算法[3]等.BF算法的实现比较简单，

但是效率低，时间复杂度高.KMP算法对BF算法作了很大改进，利用已匹配好的

部分子串来移动模式串.字符串匹配失败时，正文不需回溯，时间复杂度比BF算法

低，但最坏情况下的时间复杂度与BF算法相同.KR算法是利用Hash方法和素数

理论，将文本串和模式串用Hash函数转换成数值进行模式匹配的算法.本文在对

BF、KMP、KR等模式匹配算法分析的基础上，提出一种改进的模式匹配算法.

字符串模式匹配定义如下：在字符集∑上，给定一个长为n的文本串T和一个长为

m的模式串P，满足Ti=P1，Ti+1=P2，…，Ti+m-1=Pm即P1..m=Ti..i+m-1

（1≤i≤n-m+1）则说明模式串P在文本串T的位置i处出现，即模式串与文本串

匹配.串的模式匹配就是要寻找P在T中是否出现，以及P在T中出现的起始位置

[4-6].

1.1BF算法

BF算法又称朴素模式匹配算法、简单匹配算法，是效率最低的模式匹配算法.BF

算法的步骤是：首先在串T和串P中设置比较的起始下标i和j（初始值为i＝1，j

＝1），然后开始比较，如果T［i］和P［j］相等，则继续比较串T和串P的下

一个字符，直到T［i＋m－1］和P［j＋m－1］相等为止；若比较到第k个字符

时出现T［i＋k-1］≠P［j＋k-1］，则将i和j回溯（i增加1，j＝1），重新开始

比较.如果存在i（1≤i≤n－m＋1），且T［i.i＋m－1］＝P［1.m］，则比较成功，

否则失败.

BF算法的优点是不需要预处理过程，需要的额外空间为常数，每一趟比较时可以

以任意顺序进行.但是算法在某趟匹配失败后，对于文本串T要回溯到本趟匹配开

始字符的下一个字符，模式串P要回溯到第一个字符，所以效率较低，时间复杂

度为O（n×m）.

1.2KMP算法

1970年，从理论上证明了模式匹配问题可以在O（m＋n）时间内解

决.，和在BF算法的基础上提出了一种快速模式

匹配算法，称为KMP算法.造成BF算法效率低的原因是回溯，KMP消除了BF

算法需要回溯的缺点，借助于一个辅助数组next来确定当匹配过程中出现不等时，

模式P右移的位置和开始比较的位置，使算法的效率得到了大幅度提高，时间复

杂度达到最理想的O（m＋n），空间复杂度是O（m）.KMP算法的主要思想是：

每当一趟匹配过程中出现字符比较不等时，不需回溯i指针，而是利用已经得到的

“部分匹配”的结果将模式向右“滑动”尽可能远的一段距离后，继续进行比较.

若令next［j］＝k，则next［j］表明当模式串中第j个字符与文本串中相应位置

“字符”失配时，在模式中需要重新和文本串中该字符进行比较的字符的位置.由

此可得到模式串的next函数的定义：

但如果模式串中重复字符较多的情况下，算法还存在一定缺陷.故在改进的KMP算

法中针对next函数又提出了修正算法：

1.3KR算法

KR算法是Turing奖获得者和在1981年提出来的.该算法

利用Hash方法和素数理论定义一个Hash函数，然后将模式串P和文本串T中长

度为m的子串利用Hash函数转换成数值[3].在比较过程中只需比较那些与模式串

具有相同Hash函数值的子串，从而提高了效率.但由于Hash函数本身的问题，

会存在Hash冲突.所以即使Hash函数值相同，字符串也不一定完全相同，还要

进一步进行字符比较.但只要素数选择恰当，Hash冲突的概率就会很小.

对于长度为m的模式串P来说，Hash函数可以定义如下：

在这里，P［i］的取值为对应字符的ASCII值，q是一个比较大的素数，本文为计

算方便，q取值为int型最大值32767.

同理，将文本串T中长度为m的子串T［i.i＋m－1］映射成整数的方法为：

为了快速计算T中每个长度为m的子串的Hash函数值，可以推导出递推公式：

根据这一递推公式可很容易地计算出T中每个长度为m的子串的Hash函数值.如

果不考虑字符匹配所需时间，KR算法的时间复杂度是O（n＋m），若考虑字符

匹配所需时间，则KR算法的时间应是O（m*n）.在实际应用中可使q取值适当

大，使得在计算机中求余运算简单可行，而Hash冲突又几乎不可能发生，从而使

得KR算法的实际运行时间只需O（m＋n）.

通过对KR算法及其他模式匹配算法的研究分析，KR算法在运算速度及效率等方

面是比较高效的.在实践中由于Hash冲突的存在，会有较多模式串与文本串匹配

的情况.为了进一步提高KR算法的效率，提出对KR算法的改进.为叙述方便将改

进的KR算法记为IKR（ImprovedKarp－Rabin）算法.

2.1算法描述

IKR算法继承了KR算法的思想，改进了算法第一次匹配时（即出现相同Hash值）

对字符进行比较的方式，采用双向比较方式来进行字符匹配.对文本串T中任意m

个字符即T［i.i+m－1］，以及模式串P的m个字符，分别使用哈希函数并比较

其计算结果，如果两值相等，则说明文本串在位置i开始的后m个字符有可能与

模式串匹配.这时对这m个字符进行双向比较.

具体匹配过程是：

Step1.对文本串T中从i开始的m个字符即T［i.i+m－1］，以及模式串P的m

个字符，如果它们的Hash函数值相同，采用双向比较方式来进行文本串与模式串

字符的匹配.初始化j＝1.

Step2.同时对T［i+j－1］与P［j］，T［i+m－j］与P［m－j＋1］进行比较，

如果两者之间有任一不相等，则退出比较.

Step3.如果两值相等，则j值增加1，重复Step2，选取文本串的下一个位置继

续进行比较，直到j＞=m/2，说明匹配成功.

与KR算法比较，KR算法在产生哈希冲突时，是将当前文本串与整个模式串通过

顺序方式进行匹配，而IKR算法利用双向比较法进行匹配，减少比较次数.

2.2算法复杂度分析

KR算法最大的特点是利用哈希函数来决定可能存在匹配的位置，尝试次数为n－

m＋算法的空间复杂度为常数，其预处理阶段的时间复杂度为O（m），最

好情况下时间复杂度可达到O（n+m）.IKR算法基于KR算法的思想，采用哈希

函数来决定匹配位置，一旦发现冲突则对文本串和字符串采用双向比较的方式来进

行匹配.因此在预处理阶段的尝试次数为n－m＋1，在冲突后的匹配阶段采用双向

比较来计算，最好情况下IKR算法的时间复杂度为O（n+m/2），空间复杂度为

常数.

本文实验环境是Inter（R）Core（TM）2.30GHz，4GB内存，Microsoft

WindowsXP专业版，算法设计使用VisualC＋＋6.0.

3.1匹配次数比较

评价—个模式匹配算法优劣程度的一个重要指标是字符的匹配次数.本文对BF、

KMP、KR和IKR四种模式串匹配算法的匹配次数进行了实验比较.实验中测试文

本串采用RFC文档（RequestForComments，互联网通信协议描述文件集）进

行测试比较.分别执行不同的模式匹配算法，得到字符匹配中的比较次数，具体实

验结果如表1所示.

从表1中可以看出，对于相同的文本串和模式串，IKR算法比较次数最少.相对KR

算法，IKR算法的比较次数减少，平均效率提高5%左右.

3.2运行时间比较

图1为采用不同的模式串对BF、KMP、KR和IKR四种算法执行时间的对比.本实

验选用大小为310KB的纯英文文本，分别采用长度为5、7、10和13四个不同

模式串对BF、KMP、KR和IKR算法进行测试.

从图1中可以看出，在对比实验的BF、KMP、KR和IKR四种算法中，IKR算法

执行效率最高.和KR算法比，执行时间明显减少，平均效率提高10%左右.

通过以上实验结果可以看出，相对于KR算法，IKR算法有效减少了匹配的次数，

提高了模式匹配的速度.

本文在对传统模式匹配算法分析的基础上，提出了IKR算法，对算法的设计思想、

原理进行了详细的描述和分析，实验证明改进后的算法在一定程度上可以减少比较

次数，提高模式匹配的效率.

【相关文献】

［1］胡金柱，熊春秀，舒江波，等.一种改进的字符串模式匹配算法［J］.模式识别与人工智能，

2010，23（1）：103－106.

［2］KnuthDE，MorrisJH，tternmatchinginstrings［J］.SIAMJon

Computing，1977，6（2）：323－350.

［3］KarpRM，entrandomizedpattern－matchingalgorithms［J］.IBM

JournalofRearchandDevelopment，1987，31（2）：249－260.

［4］Pou－YungL，：afastermatchalgorithm［J］.IEEETransactionson

KnowledgeandDataEngineering，2002，14（5）：1047－1058.

［5］张先利，于建华.一种新的入侵检测模式匹配算法［J］.计算机应用与软件，2010，27（5）：

272－273，285.

［6］田宏，李君秋.一种改进的模式匹配算法［J］.大连交通大学学报，2010，31（4）：76－

79.