QS快速单模式匹配的两种改进算法

周志平，庄金莲，陈佳丽

（龙岩学院数学与计算机科学学院，福建龙岩364000）

QS快速单模式匹配的两种改进算法

周志平，庄金莲，陈佳丽

（龙岩学院数学与计算机科学学院，福建龙岩364000）

模式匹配算法已广泛应用于各个领域，针对如何减少匹配次数，提高算法效率，提出两种改进的QS快速匹配算法。第一种算法通过检测匹配窗口的末字符是否出现于模式串中，并依据情况滑动模式串。第二种算法通过构造BM及QS算法两个坏字符滑动表，经查表比较后确定每一次的滑动距离，使得模式串的滑动距离达到最大，从而大大减少了尝试的次数。实验结果表明，UCD与MSD算法的尝试匹配次数明显优于QS及其他算法，具有更高的效率。

QS算法；模式匹配；串搜索；字符串匹配

模式匹配算法广泛应用于入侵检测、病毒检测和生物序列检测等领域。在入侵检测中[1-2]，需要快速模式匹配算法对各种入侵事件进行匹配和检测。随着网络传输速度的不断提高，计算机需要处理的数据量也越来越大，如果模式匹配算法来不及处理这些大量的数据包，必然会造成漏报。因此，模式匹配算法的性能成为制约入侵检测系统效率的瓶颈。模式匹配问题可以描述为大小为C的字符集合Σ，在长度为n的文本串（T=T0T1T2…Tn-1）中查找长度为m的模式串（P=P0P1P2…Pm-1）出现的位置。在匹配过程中，T与P中正在比较的子串称为匹配窗口，一次比较称为一次尝试。模式匹配算法优化的目的是使尝试的次数最少而滑动距离最大。在实际应用中，常用的单模式匹配算法有BM[3]，QS[4]，BMH[5]等。QS算法以其简单快速且易于实现的特点被广泛应用。本文提出失配字符检测算法和最大滑动距离算法，具有比QS算法更大的移动距离以及更快的查找速度。

1 相关算法

1.1 QS算法

在QS算法中，只建立一个坏字符滑动表qsBc[][6]。在匹配的过程中，滑动的距离与失配字符的位置无关。若发生失配，则使用T[j+m]字符查找qsBc[T[j+m]]，以确定滑动的距离，其中j为文本串中当前匹配窗口指针。由于模式串P中出现的字符的数量通常要小于字符集合Σ的大小，当字符不出现在模式串P中时，QS算法的最大的滑动距离可达到m+1，从而有效提高了算法的匹配效率。然而，当T[j+m]与P[m-1]匹配，且字符T[j+m-1]不出现在模式串时，滑动距离仅为1，导致尝试匹配次数大大增加，算法效率大打折扣。

1.2 基于QS的改进算法

文献[7]中提出了一种基于QS的改进算法（improved quick search，IQS）。根据各字符在文章中出现概率的统计结果，生成数组pro[]，之后将模式串进行预处理，记录特征字符chk及其出现的位置pos。匹配过程对文本串T中第i位的字符text[i]与模式串P中的pos位进行比较，并将模式串的尾字符text[i+p_len-pos-1]与主串进行比较，其中i为文本串中当前的匹配窗口指针。若两者均匹配成功，则进行精确匹配；否则，判断文本串中的第i＋p_len-pos个字符是否出现在模式串中：若没有出现，移动p_len+1；否则，移动p_len-pat[text[i+p_len-pos]]+1。循环执行，直到整个主串匹配完成。

该算法增加了一个按字符概率排序的字符串，在一定程度上减小了字符匹配的概率，由于查找滑动距离表与QS算法相同，仅用i＋p_len-pos移动模式串，无法克服QS算法存在的问题，在实际文本匹配过程中，效果不是很理想。

2 改进算法

2.1 UCD算法描述

针对QS算法存在的问题，本文提出一种失配字符检测算法（un-occurrence character detect，UCD）。该算法采用一个与QS算法相同的坏字符滑动表qsBc[]，检测匹配窗口中字符T[j+m-1]的滑动距离，查找qsBc[T[j+m-1]]，若滑动距离为m+1，则表示字符T[j+m-1]不出现于模式串P中。查找qsBc[T[j+m]]，若滑动距离为m+1，则模式串滑动距离为m+1，否则模式串滑动距离为m。其中qsBc[]表的构造方法如下：

假设模式串P=“ababc”，长度m=5；文本串T=“ababdababc”，长度n=10。表1所示为UCD算法建立的滑动表，图1所示为匹配过程。将两字符串左对齐，查找滑动距离表，qsBc[d]=6，说明字符d不在模式串中。qsBc[a]=3，则移动5位。

2.2 MSD算法描述

针对QS算法存在的问题，提出另一种最大滑动距离算法（maximum shifting distance，MSD），该算法采用两个坏字符滑动表qsBc[]和bmBc[]，两张表分别针对字符T[j+m]与T[j+m-1]建立的滑动距离表，通过查找qsBc[T[j+m]]与bmBc[T[j+m-1]]，取较其较大值来滑动模式串，可使模式串的滑动距离达到最大值。其中qsBc[]表的构造与QS算法相同，bmBc[]表的构造与BM算法所提出的坏字符表相同，具体构造方法如下：

表1 UCD算法滑动距离表

图1 UCD算法匹配过程

假设模式串P=“ababc”，长度m=5；文本串T=“ababdababc”，长度n=10。表2所示为MSD算法建立的滑动表，图2所示为匹配过程。

表2 MSD算法滑动距离表

图2 MSD算法匹配过程

将两字符串左对齐，查找滑动距离表，qsBc[a]=3，bmBc[d]=5，取其较大值，则移动5位。

2.3 算法分析

设字符集合Σ，大小为c。文本串T长度为n。模式串P长度为m，所含字符集合为Π，大小为k，其中Π为Σ的子集。qsBc[]、bmBc[]分别为QS、BM算法的滑动距离表。

在模式串匹配过程中，QS、BMH和MSD算法尝试匹配次数表示为：

其中shift表示模式串的滑动距离，各算法的滑动距离计算如下：

（1）QS算法平均滑动距离：

（2）BMH算法平均滑动距离：

由（1）可得tMSD≤tQS≤tBM，并且当k□c效果好。

UCD算法使用了一张坏字符滑动表，MSD算法使用了两张坏字符滑动表，空间复杂度都为O(c)。预处理的时间复杂度为O(m+c)。若文本串所出现的字符不出现在匹配串中，则模式串可滑动m+1。在极端的情况下，每一次尝试匹配后的滑动距离都是m+1，因此在最好的情况下时间复杂度是O(n/m+1)。由于文本串中的每一个字符的匹配次数不超过m次，那么文本串中的所有字符的匹配次数不超过m·(n-m+1)次。在极端的情况下，每一次尝试匹配后的滑动距离都是1，因此时间复杂度是O(m·(n-m+1))。

综上所述，UCD算法及MSD算法复杂度与QS算法相同,并且优于BMH算法。

3 实验结果

在实验中，测试环境为Intel Core 2 Duo CPU 2.10GHz、2G内存、Windows 7；编译环境为Microsoft Visual Studio2005。对QS，BM，BMH，IQS，UCD与MSD算法进行比较，文本串来自于Reuters[8]中的feldmancia-worldfactbook-data.txt，删除换行及空格符后文件大小为256 kB。尝试次数比较结果如表3所示。

由表3可看出，当模式串较短时，QS算法、IQS、UCD及MSD相比BM及BMH算法大大降低了尝试次数。随着模式串的增长，UCD与MSD算法较其他算法提升效果越明显。由于MSD算法采用两张滑动距离表并取最大值，算法尝试的次数最少。4种算法的尝试次数比较如图3所示。

表3 6种算法尝试次数的比较

图3 算法尝试次数比较

4 结束语

为了提高字符串模式匹配速度，本文提出了针对QS算法改进的两种思路，两种算法各有优缺点：失配字符检测算法UCD只需要通过检测匹配窗口的末字符是否出现来滑动模式串，就能有效地避免失配字符对算法效率的影响，是最直接避免QS存在问题的方法，该算法简单快捷且开销小；最大滑动距离的QS快速匹配算法MSD，它结合了BM和QS算法的思想，通过查找两张表使滑动的距离达到最大，该算法滑动快并且简单高效，但需要更大的存储空间。实验结果表明，改进的算法与其他算法进行比较，尝试次数少，具有较高的效率。且当模式串较长且字符较少时，效果更好。

[1]CHEN T，FU Z，HE L，et al.Recent developments in Nnetwork intrusion detection[J].IEEE Network,2009：4-5.

[2]张晓惠.基于数据融合的入侵检测研究[J].三明学院学报,2012,29(4)：56-60.

[3]BOYER R S，MOORE J S.A fast string searching algorithm[J].Communications of ACM,1977,20(10)：762-772.

[4]SUNDAY D M.A very fast substring search algorithm[J].Communication of the ACM,1990,33(1)：132-142.

[5]HORSPOOL N R.Practical fast searching in strings[J].Software Practice and Experience,1980,10(6)：501-506.

[6]CHARRAS C，LECROQ T T.Handbook of exact string matching algorithm[M].London：London King’s College London Publications,2004.

[7]万晓榆，杨波，樊自甫.改进的Sunday模式匹配算法[J].计算机工程,2009,35(7)：125-129.

[8]DAVID D.Lewis,Reuters-21578 test collection[EB/OL].http：//www.daviddlewis.com/resources/testcollections/ reuters21578/，2004.

Two Improved Fast Single Pattern Matching Algorithms of QS

ZHOU Zhi-ping,ZHUANG Jin-lian,CHEN Jia-li
(School of Mathematics and Computer Science，Longyan University，Longyan 364000,China)

Pattern matching algorithms has been widely used in various fields.Aiming at how to reduce the number of attempts as well as improve the efficiency of the algorithm,two pattern matching algorithms are presented to improve the algorithm of quick search.The first algorithm matches the text window by checking whether the last character occurs in the pattern string,and then shiftsthe pattern stringdependingon the situation.The second algorithm constructs two bad character shift tables ofBMand QSalgorithms',then look up these two tablesto determine the shift distance each time,making the pattern string reach the maximum shift distance.This greatly reduces the number of attempts and increases the shift distance.The experimental resultsshow thatUCD and MSD algorithms'matchingspeed issignificantlyfasterthan QSand otheralgorithms'.

QS algorithm;pattern matching;string searching;string matching

TP301.6

A

1673-4343（2013）04-0030-04

2013-04-10

周志平，男，福建顺昌人，助教。研究方向:计算机网络，网络安全。