适合中文的双向比较模式匹配算法

叶 煜

(成都农业科技职业学院电子信息分院,四川成都 611130)

0 引 言

模式匹配(Pattern Matching)问题是计算机相关领域中的一个基本问题,也是复杂性理论中研究得最广泛的问题之一,其在文字编辑处理、图像处理、文献检索、自然语言识别、入侵检测等领域有着广泛的应用.所谓模式匹配,是指给定一个长为n的文本串T[1,n]和长为m的模式串P[1,m],找出文本串T中与模式串P精确匹配的子串的起始位置.好的模式匹配算法能显著地提高模式匹配的效率,因此,研究并设计快速的模式匹配算法具有重要的理论价值和实际意义.

1 算法与分析

目前,模式匹配算法在进行搜索实践时,最有影响的算法是K MP算法[1]和BM算法[2].

1.1 K MP算法

K MP算法由Knuth等于1977年提出,其基本思想是:采用从左向右比较的方法,设计一个与模式串本身局部匹配信息构造的模式值数组next,当匹配过程中出现失配时,利用模式值,将模式串向右“滑动”尽可能远的一段距离,使文本串的指针在匹配过程中不用回溯,保证文本串中每个字符只进行一次比较,从而提高模式匹配的效率.K MP算法的时间复杂度为O(n).

1.2 BM算法

BM算法由Boyer等于1977年提出的,其基本思想是:采用从右向左比较的方法,它包含两个并行的规则,坏字符规则和好后缀规则,当出现不匹配字符时,通过查询预处理好的坏字符移动表与好后缀移动表,选择移动距离较大值向后移动模式串,再进行下一轮匹配尝试.BM算法预处理阶段时间复杂度为O(m+s),s为与模式串P和文本串T相关的有限字符集长度,搜索阶段的最优时间复杂度为O(n/ m),最差时间复杂度为O(mn).

1.3 算法分析

在实际应用中,BM算法的搜索效率远远优于K MP算法,但由于BM算法的坏字符规则所需的坏字符表与所使用的字符集有关.通常,英文的字符集较小,建立坏字符表所需的时间、空间都比较少,而中文字符集非常巨大,要建立坏字符表不太现实,因此,高效率的BM算法并不适合于中文搜索.

此外,为提高字符串模式匹配效率,研究人员在K MP与BM算法的基础上提出了相应的改进算法[3-8].各种改进算法的目的都在于尽量减少匹配过程中的比较次数,且当模式串与文本串发生失配时模式串能够向右移动尽可能大的距离,以减少不必要的比较.但这些算法都是单向比较,缺乏优先考虑,而且改进算法在匹配过程中还会出现,模式串的首字符与文本串相匹配,而尾字符与文本串不匹配,或模式串的尾字符与文本串相匹配,而首字符与文本串不匹配等情况,这就导致了较多不必要的比较,降低了匹配的效率.同时,这些改进算法也同样大都不适用于中文搜索.

2 双向比较模式匹配算法

针对上述问题,本文提出一种字符串匹配算法的新思路:双向比较模式匹配算法.在该方法中,利用模式串尾字符建立一个只与模式串自身有关的特征数组,这个数组在匹配过程中只需要记录下模式串尾字符在模式串前半部分出现的位置.

2.1 双向比较模式匹配算法的具体思路

双向比较模式匹配算法的具体思路是:

(1)用模式串P的尾字符与文本串T进行比较,结果失配,由于汉字是宽字符,所以模式串P右移两位在新的位置继续比较.

(2)用模式串P的尾字符与文本串T进行比较,结果同配(暂且称这个字符为同配字符),再把模式串前半部分与文本串比较,当所有字符都能匹配上时,则找到字符串返回查找结果并结束;如果出现失配,再利用K MP算法的模式值next得到模式串右移的距离,但如果这时开始新一轮的比较,就有可能是无效的,因为已知模式串的尾字符与文本串同配,而模式串移动到这个位置却并没能让文本串中的同配字符与出现在模式串前半部分的同配字符对齐(见图1).此时,可再向右移动模式串,使两者的同配字符对齐后再进行比较(见图2).如果模式串前半部分没有出现同配字符,就可以完全移过该比较窗口(见图3).

(3)特征数组的建立需要在预处理阶段完成,该数组只与模式串自身有关,记录的是模式串尾字符在模式串前半部分出现的位置.设模式串尾字符为b,其计算公式如下:

建立数组specialArray的算法描述如下:

2.2 双向比较模式匹配算法

双向比较匹配算法分为尾字符匹配和前半部分匹配两部分.假设在index位置对模式串P尾字符进行匹配,如果失配,将模式串右移两位在下一个位置进行比较;如果同配,则匹配模式串前半部分,前半部分也同配,字符串找到.当前半部分在j位置失配,结合模式值与特征数组以获得最大距离来移动模式串,减少匹配次数.双向比较模式匹配算法的核心代码如下:

2.3 双向比较模式匹配算法时间复杂度分析

根据双向比较模式匹配算法的匹配过程分析可知:在最优的情况下,模式串尾字符总是与文本串字符同配,而首字符与文本串失配且尾字符未在模式串前半部分出现,使模式串在每次匹配时只比较了两个字符且失配后右移距离为m个字符,即时间复杂度为O(2n/m);在最差的情况下,无论模式串哪个字符与文本串字符失配,由于文本串指针不回溯,保证文本串中的每个字符都只会进行一次比较,故最差时间复杂度为O(n).

3 实 验

在双向比较模式匹配算法的匹配实验中,我们选择一部1 249 020字的小说,其文本大小是2.4 MB.在该文本中随机选择几个长度依次是63、41、36、27、7、3字的字符序列P1、P2、P3、P4、P5、P6为模式串进行实验,分别测试了K MP、双向比较模式匹配算法在查询命中目标过程中的匹配次数及CPU运行时间.测试环境为Windows XP,系统配置为AMD CPU 1.9 GHz,内存1 G B.实验结果如表1所示.

表1 算法实验结果

从表1可以看出,在同一个模式串P的查询过程中,双向比较模式匹配算法比较次数和CPU运行时间都远远少于K MP.由于双向比较模式匹配算法所采用的模式值及特征数组都只与模式串自身有关,所需的辅助空间等于模式串长度,因此,双向比较模式匹配算法无论时间复杂度还是空间复杂度都是较理想的.

4 结 语

本文提出的双向比较模式匹配算法,通过建立模式串尾字符的特征数组,以及尾字符与文本串比较进所获得的信息,使模式串取得更大的右移距离,大大减少了模式匹配中不必要的比较,提高了匹配的效率.实验结果表明,双向比较模式匹配算法的匹配效率是较理想的.

[1]Knuth D E,Morris JR J H,Pratt V R.Fast Pattern Matching In Strings[J].SIAMJ on Comput,1977,6(2):323-350.

[2]Boyer R S,Moore J S.A Fast String Searching Algorithm[J]. Communications of the ACM,1977,20(10):762-772.

[3]李雪梅,代六玲,童新海,等.一种串匹配的快速Boyer-Moore算法[J].计算机应用研究,2005,22(9):49-51.

[4]渠瑜,王亚弟,韩亚红,等.对BM模式匹配算法的一个改进[J].计算机工程,2006,32(23):78-81.

[5]单懿慧,蒋玉明,田诗源.面向入侵检测的改进BMHS模式匹配算法[J].计算机工程,2009,35(24):170-173.

[6]俞松,郑骏,胡文心.一种改进的 K MP算法[J].华东师范大学学报(自然科学版),2009,55(4):92-97.

[7]蔡晓妍,戴冠中,杨黎斌.一种快速的单模式匹配算法[J].计算机应用研究,2008,25(1):45-47.

[8]贺龙涛,方滨兴,余翔湛.一种时间复杂度最优的精确串匹配算法[J].软件学报,2005,16(5):676-683.