蔡婷++杨卫帅

摘 要：高效快速的字符串模式匹配算法有助于网络信息处理的相关应用。文章在分析相关字符串匹配算法的基础之上，针对模式串中字符重复次数较多匹配应用，提出了一种快速的字符串匹配改进算法。该算法利用文本串中当前失败字符与模式串右对齐端的文本串下一个字符来启发模式串向右移动。结合这两个字符在模式串中匹配的情况及以这两个字符为首末的特征字符串在模式串中的匹配情况来使计算模式串向右移动最大距离，尽可能地排除无效匹配。实验结果表明，该算法能有效减少模式匹配中字符的比较次数，提高模式匹配效率。

关键词：字符串匹配；KMP算法；BM算法；Sunday算法；移动距离

中图分类号：TP301.6 文献标识码：A 文章编号：2095-1302（2017）07-00-03

0 引 言

随着信息技术的高速发展，如何在海量数据中提取有用信息是网络信息技术研究的热点。字符串模式匹配主要用于文本串的处理领域，如信息检索、拼写检查、数据处理、信息测试、数据压缩、搜索引擎、网络入侵检测、DNA序列匹配等。如何用高效快速的字符串模式匹配算法解决网络信息处理的相关问题已成为目前研究的重要领域之一。

字符串匹配问题的形式化定义是[1]：在有限字母表∑上的字符序列上，给定一个长度为n的文本串T[0…n-1]以及一个长度为m的模式串P[0…m-1]，m

1 相关算法介绍

1.1 KMP算法

KMP算法是经典的字符串匹配算法，主要在模式匹配过程中执行T[i]和P[j]的匹配检查。若T[i]=P[j]，则继续匹配T[i+1]与P[j+1]；若T[i]≠P[j]，则分成两种情况：若j=0，模式串P向右移一位，继续匹配T[i+1]和P[0]；若1

（1）

其中：

1.2 Horspool算法

Horspool算法是字符串匹配算法中从右向左匹配的创始者。当失配发生时，模式串P要向右移动，T串的失配字符T[i]可能是正确结果中的一个元素，也可能不是。如果不是，可将P串的首位与T串中的T[i+1]对齐，继续进行比较；如果是，那么从P串失配位置j开始向左任意一位与P[i]相等的字符c确定的比较位置可能完全匹配，其产生的位移依次为k1，k2…，ki（k1为j-location（c））。综合这两种情况，选择位移最小值k1，以保证不会错过正确匹配的情况。

1.3 BM算法

BM（Boyer-Moore，BM）算法是基于Horspool算法的一种改进算法，其广泛应用于实际项目中。BM算法实际包含两个并行算法，坏字符算法和好后缀算法。匹配时，同Horspool算法；当失配时，计算P串失配字符的右边已经匹配的字符串（称为“好后缀”），在P串中其他位置出现的位置得到一个右移大小值（实际该值是预先计算好的），将该值与Horspool失配时P串移动大小的值进行比较，并选择其中较大者。P串移动后，继续进行比较。

1.4 Sunday算法

Sunday算法是一种高效算法，可以看成BM算法的简化形式。在匹配过程中，模式串P不一定要按从左向右的顺序比较或从右向左进行匹配。在失配情况下，选中T串与P串右对齐端的下一个字符T[i]，从P串末位向左寻找与该字符相等的字符P[j]，找到后，T[i]与P[j]对齐，继续从右到左比较；若找不到，则P串左端与T[i]的下一个字符对齐，从右到左比较。

2 改进的字符串匹配算法

字符串模式匹配算法要解决的关键问题是在模式与文本某个位置比较失败时，如何使模式串窗口向右移动最佳距离，尽量跳过无需比较的字符，减少匹配次数，并使产生这种距离的算法复杂度降低且易于理解。通过对现有各种字符串匹配算法的研究，我们提出一种改进算法，该算法主要针对模式串重复率较多的情况使用。当文本串T与模式串P发生匹配时，判断模式串最右端对应文本串下一个字符Ti+m是否在模式串中，若不在，匹配规则同Sunday算法；若在，记下在模式串P0P1…Pm-1中的位置q，同时记下文本串中当前失败的字符Ti+j在模式串P0P1…Pj-1出现的位置k，根据q、k的值以及Ti+j+1Ti+j+2…Ti+m-1与Pk+1Pk+2…Pm-1的比较情况来计算模式串向右移动的最大距离。

2.1 比较顺序

与BM算法类似，在模式串的匹配过程中，字符串采用从右向左的顺序依次比较。

2.2 模式串移动距离的确定

假设当前匹配的比较窗口是TiTi+1…Ti+m-1，在某次比较过程中失败于Pj处，即后m-j个字符匹配成功：Ti+j+1Ti+j+2…Ti+m-1=Pj+1Pj+2…Pm-1，而Ti+j≠Pj，如图1所示。