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

2013-11-04李映刚

四川轻化工大学学报(自然科学版) 2013年2期

李映刚

(成都理工大学管理科学学院，成都 610059)

引言

随着网络应用范围的不断扩大，对实时网络信息的快速搜索的要求也与日俱增。字符串匹配在网络领域有着广泛的应用，比如，拼写检查、语言翻译、数据压缩、搜索引擎、网络入侵检测、DNA序列匹配等。如何用高效的字符匹配算法解决问题成为目前研究的重要领域之一。

字符串匹配问题的形式化定义是［1-2］:在字符集@上，给定一个长度为N的主字符串T［1…N］，以及一个长度为M的模式串P［1…M］，M＜＜N。如果对于位置S(1＜=S＜=N-M+1)，字符串T［S…S+M-1］与P［1…M］相同，则认定模式串P出现在主串T的S位置。字符串匹配问题就是要寻找P在T中是否出现以及出现的位置。

1 相关算法简介

1.1 BF算法

BF(Brute Force)算法是最原始且效率最低的算法。它从主串第一个字符开始逐个与模式串的每个字符相比较是否相同，如果不匹配，然后从主串下一个字符重新与模式串作相同性比较。BF算法原理简单、易实现，但效率太低。

1.2 KMP算法

KMP(Knuth-Morris-Pratt)［3-4］算法是D.E.Kunth、J.H.Morris和V.R.Pratt等人在1977年提出的。KMP算法在一次匹配失败后可以利用部分匹配的结果直接将模式串向右移动尽量远的距离来进行下一次匹配。KMP算法虽然对BF算法有了很大的改进，但是原理复杂，不易推广实现。

1.3 BM算法

BM算法［4-5］是Boyer和Moore提出的一种算法。最主要的特点就是在匹配过程中，可以跳过很多无用的字符，这种跳跃式的匹配可以获得很高的匹配效率。

1.4 ZZL算法

ZZL算法［6］是纪福建等人提出的一种可用作特殊用途的字符串匹配算法。ZZL算法的核心思想是:首先在主串T中查找模式串P的首字母，每找到一个则将它的位置存储，然后依次提取这些位置，从这些位置来匹配模式串P。对于频繁使用的主串和模式串，匹配速度会非常快，缺点是可能会需要大量的存储空间来存储那些频繁使用的模式串的首字母的位置。

1.5 Sunday算法

Sunday算法［5，7］在匹配过程中并不要求字符比较的方向，在一次匹配完后，利用主串的下一个字符逆序搜索模式串，找到这个字符第一次出现的位置或者不出现。从而达到利用一个字符的遍历就能决定模式串的后移位置，极大的提高了移动效率。其核心思想就是用较少的字符比较来确定较长的模式串的位移。

一般情况下，BF算法效率最低，KMP算法与BM算法原理复杂不易实现，Sunday算法原理简单执行速度最快。本文就选取快速的Sunday算法进行改进。Sunday算法有两个缺点:首先就是对前一次匹配结果没有进行有效的利用;其次就是Sunday算法利用主串下一个字符来遍历模式串的作法也过于简单。当模式串很长的时候(很多实际应用中，模式串都比较长)，主串下一个字符在模式串中出现的概率会提高，这样的出现会增加很多的无效匹配。针对Sunday算法的两个缺陷，提出了将原理简单易实现的前一次比较结果再利用方法与主串下一个字符搜索加强方法相结合的思想，以此来改进Sunday算法，以期得到更高的匹配效率。

2 改进Sunday算法思路

2.1 前一次比较结果简单再利用

得益于BM算法的逆序比较思想，提出一种简单易理解的逆序比较结果再利用的算法。

算法描述:将模式字符串P［1…M］与主字符串T［1…N］在一次匹配比较过程中，按照字符串的逆向进行比较。从模式字符串的最后一个字符与主串相应位置开始，依次向前比较并最后确定匹配字符的数目(记为A)。根据模式串的特性，最后A个字符组成的模式串P的子串(记为SP［A］)，从模式串后面往前遍历，可以找到的第一个再次出现的子串SP［A］(本身除外)的位置(记为S)，这一过程可以在匹配前作预处理，作为模式串的特征值记录下来。如果主串与模式串从后向前最多A个字符相同，那么根据预处理的特征值的位置S，就可以不用进行字符比较，而直接决定下一次模式串的移动距离。

例如，模式串为“facdefa”，主串为“ekjacfadbcea……”，进行第一次匹配比较，倒序比较发现模式串的最后两个字符“fa”和主串的相应位置的字符相同，而“fa”在模式串中倒序再次出现的位置为1，那么可以直接决定模式串在主串中向后移动5步的距离，而不用多余的比较。算法优点就是仅仅利用预处理的结果就能决定移动步数，是一种原理简单易实现的前一次匹配结果再利用方法。算法缺点就是预处理数据能否有效果要看模式串的最后一个字符在主串中出现的概率，就平均情况而言，这与字符集@的大小有关。

2.2 增加Sunday算法中的遍历模式串的字符数

Sunday算法的核心体现在P与T进行比较确定是否匹配后，用主串下一个字符来遍历模式串进行比较就能确定模式串下一次右移的距离，仅仅通过增加遍历模式串的字符数目，就能极大的提高移动效率。比如增加一个遍历字符，在进行一次匹配后，用主串后两个字符来遍历模式串，进行比较来确定模式串下一次右移的距离。能极大提高移动步数的原因就是两个字符的比较不仅仅包含是否相等，还包含了他们之间的位置关系，位置关系所包含的信息是不用浪费时间去比较的，但是却能用来辨别模式串的移动距离。模式串越长Sunday算法的下一个字符在模式串中出现的概率就越大，无效匹配的次数就越多，由此可以预见，对于此改进方法，模式串越长，效率越高。

2.3 改进算法的处理过程

(1)模式串预处理

在进行字符匹配前，先建立一个数组fea［M-1］，M为模式串字符数，用于记录模式串的倒序特征值。

例如，模式串为P=“afkdfk”。那么倒序s个字符在模式串中除自己以外的下一次出现位置就是:

那么fea［5］={3，2，0，0，0}。如果一次倒序匹配中，匹配到的最多字符数目为s，那么直接决定模式串的下一次位移数就为D1=M-s+1-fea［s］。

(2)字符倒序匹配

记录下倒序匹配得到的最大字符数s，利用位移公式得到下一次位移数D1。

(3)增加Sunday算法的遍历模式串字符数

利用一次字符匹配后的主串的后x个字符来遍历模式串，思想与Sunday算法是一致的，只有在这x个字符与模式串中的某x个字符完全一致时，才能确定模式串的下一次位移数，记为D2。

(4)选取D1与D2中较大的一个作为模式串的后移步数D。

(5)进行下一次字符倒序匹配，重复(2)。

3 改进算法的性能分析

3.1 性能分析

不考虑对模式串的预处理过程，统计算法运行过程中总的字符比较次数，并作为算法的性能指标。倒序比较结果再利用算法的效率与模式串的最后一个字符在主串中出现的概率有关，出现概率越大，效率越高;通过将遍历模式串的字符数增加到x个，那么在模式串中出现这x个字符并且顺序一致的情况将大为减少，能提高匹配效率。同时，当模式串越长时，两种思想发生效果时后移的步数就越大，效果越好。

3.2 实验与结果

为了测试改进算法的性能，先用简单的数据来分析验证改进算法的效率。假如得到模式串为P={a，k，f，a};主串为T={a，j，f，l，d，s，j，f，s，f，a，d，a，k，f，a…..}。那么当模式串在与主串第7个子串进行匹配后，可以直接得到下一次模式串位移数D1=3;当模式串与主串第9个子串进行匹配后，可以直接得到下一次模式串位移数D1=3。模式串与主串第4个子串匹配后，若采用常规的Sunday算法，可以得到的下一次模式串位移数D2=2，但是若采用遍历字符数x=2的改进算法，可以得到的下一次模式串位移数D2=5。可见改进算法效率是有提高的。

现在用电脑随机生成长度为N的主串，以及长度为M的模式串，匹配到模式串的数目记为S，遍历模式串的字符数x=3。运行并统计相关算法的总的字符匹配数目。结果统计见表1。