一种改进的Sunday匹配算法

李明月，张善卿，陆剑锋，孙冬梅

(杭州电子科技大学计算机学院，浙江 杭州 310018)

摘要：字符串的模式匹配算法在多协议识别技术中，起着至关重要的作用，为了提高多协议识别效率，该文在分析几种经典模式匹配算法的基础上，提出一种基于Sunday算法的改进算法。算法主要是在每次匹配开始前通过一个条件判断语句，判断主串中的相应后缀是否在模式串中，从而减少了无意义的匹配次数，提高了算法的执行效率，通过对比实验证明了该算法的有效性。

关键词：Sunday算法；RoSunday算法；匹配模式

DOI: 10.13954/j.cnki.hdu.2015.01.019

一种改进的Sunday匹配算法

李明月，张善卿，陆剑锋，孙冬梅

(杭州电子科技大学计算机学院，浙江 杭州 310018)

摘要：字符串的模式匹配算法在多协议识别技术中，起着至关重要的作用，为了提高多协议识别效率，该文在分析几种经典模式匹配算法的基础上，提出一种基于Sunday算法的改进算法。算法主要是在每次匹配开始前通过一个条件判断语句，判断主串中的相应后缀是否在模式串中，从而减少了无意义的匹配次数，提高了算法的执行效率，通过对比实验证明了该算法的有效性。

关键词：Sunday算法；RoSunday算法；匹配模式

DOI:10.13954/j.cnki.hdu.2015.01.019

收稿日期：2014-05-09

基金项目：浙江省自然科学基金资助项目(LY14F020043)

通信作者：

作者简介：李明月(1989-)，男，河南固始人，在读研究生，数据可视化技术.张善卿副教授，E-mail: zhangsq71@126.com.

中图分类号：TP301.6

文献标识码：：A

文章编号：：1001-9146(2015)01-0093-04

Abstract:Pattern-matching algorithm of string plays an important role in multi-protocol recognition technology， in order to improve the efficiency of multi-protocol recognition， this paper analyzed several classical pattern matching algorithms and presented a modified SuSunday algorithm on the base of RoSunday algorithm. The algorithm mainly judged the suffix of the main string whether contain in the pattern string through the conditional judgment before the start of each matching， thereby reducing the frequency of meaningless matching， improve the execution efficiency of the algorithm， and verified the effectiveness of this algorithm through comparison testing.

0引言

1字符串匹配算法

1.1　Sunday算法

Sunday算法的思想是：在匹配过程中，模式串首先按从左向右进行逐个匹配，当发现有不匹配的字符时，当前匹配的位置就跳过尽可能大的步长，再进行下一轮的匹配，从而达到提高匹配效率的摸底。Sunday算法匹配失败时，判断主串中参加匹配的最末位字符的下一位字符是否在模式串中出现。如果未出现，跳转步长为模式串长度加1；如果出现，其跳转步长为模式串中最右端的该字符到末尾的距离加1。

1.2　RoSunday算法

RoSunday算法是在经典的Sunday算法的基础上进行改进的，其核心思想是：先判断，再匹配，以减少无效的匹配次数[6]。在每一次开始匹配前，算法都要判断主串T中参与匹配的字符串中的最后位置上的那个字符是否在模式串中出现。如果没有出现，则直接跳过整个模式串长度，并从该字符的下一位字符开始进行下一轮的匹配，这样就避免了无效的字符匹配次数，提高了匹配效率；如果出现，就按照Sunday算法的方法继续匹配。

2改进的算法

2.1　算法改进

RoSunday算法是在Sunday算法的基础上效率上有所提高。但有时存在这样的问题，若主串为“CACBC”，模式串为“CACAC”，主串中对应的最后一位字符“C”，在模式串中，于是就匹配了4次，才发现字符“B”不在主串中，于是整个匹配失败了，这4次匹配是无意义的。为了解决这个问题，本文对RoSunday算法进行了改进，提出了SuSunday算法。其核心思想是匹配前先判断主串中相应的后缀，再匹配，最后再跳转。

假设，每次匹配时，将模式串(patten)的最后后缀长度t个字符组成的子字符串设为后缀(Suffix)，匹配时，Suffix与主串(text)中对应位置上的子字符串的下一个字符设为K，主串当前匹配字符的位置设为Pos，模式串中每个字符到模式串尾部距离数组设为next[i]。具体改进步骤如下：

1)若Pos加模式串长度小于主串长度，则进入步骤2，否则进入步骤5；

2)在开始匹配前都要检验Suffix在模式串中有没有出现过；

3)如果Suffix没有出现，则直接跳过，即移动步长为模式串长度，并从K字符开始进行步骤1、步骤2操作；如果Suffix在模式串中出现，则开始匹配。若匹配成功，返回匹配结果；若匹配失败，则进入步骤4操作；

4)检验K字符是否出现在模式串中。若出现，则跳转步长为next(K)，然后进入操作步骤1；若没出现，则跳转步长为模式串长度加1，然后进入操作步骤1；

5)匹配失败。

下面用SuSunday算法来运行上文中的例子来说明该算法的过程。

text=“BACACBBAACECACAC”，patten=“CACAC”，后缀长度取3，具体匹配过程如图1所示。

图1　SuSunday算法匹配过程

从图1可以看到，用改进后的SuSunday算法只需要6次匹配就匹配成功了。

2.2　改进算法实现

假设patten与text匹配时，对应后后缀字符串为Suffix，Suffix下一个字符为K，模式串长度为len_p，主串长度为len_t。SuSunday算法在实现过程的流程如图2所示。

2.3　后缀长度的分析

一个算法的执行效率决定于算法的匹配次数[7]，经过实验得出SuSunday算法中后缀长度与匹配次数的关系是后缀长度越长，匹配次数越少。后缀长度为len_p时，匹配次数达到最小值，但是在SuSunday算法中判断后缀是否在模式串中也会消耗时间，经过试验得出SuSunday算法中后缀长度与匹配时间的关系：随着后缀长度的增长，消耗时间逐渐减少，当后缀长度t=1+len_p/2时，消耗时间最少，效率最高，实验结果如图3所示。

图3中的实验，用的主串text与模式串patten内容，见2.4节中的测试样例。由图3实验结果分析可知，当后缀长度为len_p/2+1时，算法的效率达到峰值。

图2　SuSunday算法的流程图

图3　不同模式串长度，后缀长度与匹配时间的关系

2.4　改进算法性能分析

假设测试文本长度为n，模式串长度为m，其中n远大于m，则Sunday算法的空间复杂度为O(1)，时间复杂度最好情况为O(2m+n/m)，最差情况为O(n×m)[7]。RoSunday算法的空间复杂度为O(1)，时间复杂度最好情况为O(m+n/m)，最差情况为O(n×m)。SnSunday算法的空间复杂度为O(m/2+1)，时间复杂度最好情况下为O(m+n/m)，最差情况为O((n/m)×(m/2+1)+m)。

再假设RoSunday算法和SuSunday算法中出现各种情况的概率分别Pr和Ps，则这两种算法的平均时间复杂度为：

(1)

(2)

式(1)中，Pr为第r种情况的概率，O(f(r))为第r中情况下的时间复杂度。式(2)中，Ps为第s种情况的概率，O(f(s))为第s中情况下的时间复杂度。

假设在同一种情况下Pr=Ps，由SoSunday时间复杂度在最好情况下和RoSunday算法相同，最差情况下，时间复杂度远小于RoSunday算法，因而，当Pr=Ps时，SuSunday算法的平均时间复杂度小于RoSunday算法的时间复杂度，即F(SuSunday)

3对比实验结果

为了评测本算法的性能，从匹配次数和匹配时间两项参数进行实验对比。从大量的测试用例中，随机抽取一段大小为10 kB的文本和长度大于2且各不相同的6个模式串(由于测试文本内容较多，文中只列出测试文本的部分内容)，在相同的平台下，对Sunday算法、RoSunday算法和SuSunday算法进行实验并记录下每种算法匹配一次的时间和匹配次数。由于模式串长度不等，所以后缀长度取各个模式串都能满足的长度。测试机器的处理器为3.1 GHz的Inter(R) Core i5-2400 CPU，内存为4 GB。测试文本text=“The first film explores the complex structure of the coral reef itself and the wildlife that lives on it. So vast it is visible from space， the reef is actually built by tiny animals in partnership with microscopic plants. It is a place full of surprises that is always changing， responding to the rhythms of weather， full tide，sun and moon….”；模式串paten分别为“sun”，“reef”，“lives”，“plants”，“animals”，“changing”；测试结果如图4、图5所示。

图4　不同模式串成功匹配一次的次数

图5　不同模式串成功匹配一次的时间

图4中，Sunday表示Sunday算法的匹配次数，RoSunday表示RoSunday算法匹配次数，SuSunday表示SuSunday算法匹配次数。图5中，Sunday表示Sunday算法匹配一次所用的时间，RoSunday表示RoSunday算法匹配一次所用时间，SuSunday表示SuSunday算法匹配一次所用时间。

从图5中的两项参数的实验对比结果可以看出SuSunday算法比Sunday算法和RoSunday算法效率高很多。

4结束语

本文在分析几种经典模式匹配算法的基础上，提出一种基于Sunday算法的改进算法SuSunday算法。算法思想简单易懂，主要是在每次匹配开始前通过一个条件判断语句，判断主串中的相应子串是否在模式串中，从而减少了无意义的匹配次数，提高了算法的执行效率，从理论上对本算法的性能进行了分析和比较，并通过对比实验测试结果，证明了本算法的有效性。

参考文献

[1]刘蜻歆.异构融合网络中接入安全机制研究[D].北京：北京邮电大学，2006:1-4.

[2]鲁文静.异构无线融合网络中通用接入认证协议研究[D].郑州：解放军信息工程大学，2009:1-3.

[3]Salmela L. Average complexity of backward q-gram string matching algorithms[J]. Information Processing Letters，2012，112(11):433-437.

[4]Kandhan R， Teletia N， Patel J M. SigMatch: fast and scalable multi-pattern matching[J]. Proceedings of the VLDB Endowment，2010，3(1-2):1 173-1 184.

[5]Sunday D M. A very fast substring search algorithm[J]. Communications of the ACM，1990，33(8):132-142.

[6]徐珊，袁小坊，王东，等.Sunday字符串匹配算法的效率改进[J].计算机工程与应用，2011，47(29):96-98.

[7]潘冠桦，张兴忠.Sunday算法效率分析[J].计算机应用，2012，32(11):3 082-3 084.

A Modified Sunday Matching Algorithm

Li mingyue， Zhang shanqing， Lu jianfeng， Sun dongmei

(SchoolofComputer，HangzhouDianziUniversity，HangzhouZhejiang310018，China)

Key words: Sunday algorithm; RoSunday algorithm; matched pattern