一种新的特征值的模式匹配算法FLC

余飞，刘思宏

（安徽电子信息职业技术学院软件学院，安徽蚌埠233060）

一种新的特征值的模式匹配算法FLC

余飞，刘思宏

（安徽电子信息职业技术学院软件学院，安徽蚌埠233060）

提出一种基于特征值的模式匹配算法——FLC（First-Last-Characters）算法，可打破经典算法有序偏移的思想，突破BMHS（Boyer-Moore-Horspool-Sunday）算法最大偏移量（m+1）的上限，从而增大偏移距离，减少匹配时间.测试结果表明：FLC算法的匹配效率优于BMHS算法.

模式匹配；BMHS；FLC

模式（Schema）是指按照某种结构组织起来的多个元素的集合.模式匹配指将两个模式作为输入，计算模式元素之间语义上的对应关系的过程.模式匹配的关键是匹配方法.模式匹配算法就是用来描述匹配方法及过程的.

经典的模式匹配算法采用文本串保持不动，模式串有序偏移的方式进行字符匹配.最早的BF（Brute Force）算法[1]就是一种有序查找算法，它将模式串（匹配对象）与文本串（被匹配对象）按位从左到右依次进行比较.如果完全相同，则匹配成功；若有一个字符不同，则匹配不成功，模式串向右移动一个字符的位置，继续比较，直到将文本串的所有位都进行比较.BF算法实现简单，但模式串每次仅偏移一个字符，这导致模式串几乎要与文本串中的每一个字符进行比较，运行效率极其低下.

KMP算法[2]是BF的一种改进算法，该算法由Knuth等人提出.KMP算法根据给定的模式串，定义一个next函数.模式串与文本串按顺序进行从左到右匹配，若匹配不成功，next函数将给出模式串向右移动的位置，即模式串与文本串重新开始比较的起始位.KMP算法的创新之处在于，利用next函数能够科学计算出模式串偏移距离，解决了BF算法中模式串偏移的盲目性，实现了其大幅度的有序偏移，提高了匹配效率，为后续研究奠定了基础.

1977年，Boyer和Moore提出了一种著名的单模式匹配算法——BM算法[3-4]，该算法使用坏字符规则（Bad Character）和好后缀规则（Good Suffix）来计算模式串右移距离，实现模式串的跳跃式偏移.BM算法效率较BF和KMP算法有显著的提高，也开始投入实用，应用于入侵检测系统，防火墙系统[5]等.

此后，对BM算法的改进成为该领域的热门，重要的改进算法有1980年Horspool提出的BMH（Boyer-Moore-Horspool）算法[6]和1990年Sunday提出的BMHS（Boyer-Moore-Horspool-Sunday）算法[7].BMH与BMHS算法的改进集中在模式串与文本串失配后模式串偏移量的计算，减少了匹配次数和消耗时间，匹配效率得到提升.

近几年对模式匹配算法的研究主要集中在对算法的改进与应用上.陈瀛等将数理统计的方法带入模式匹配算法[8]，运用抽样统计理论从文本串中采集可能与模式串匹配成功的抽样点，在其周围进行精确匹配.姚亚锋等提出了AC-BM算法[9]，该算法结合了AC算法与BM算法两种经典算法的优长，显著提高了效率.刘胜飞、张云泉在BMH算法的基础上提出BMH2算法[10-11]，该算法增加了一个移动距离的特征数组，来辅助模式串进行最大幅度的偏移.

本文在探讨经典算法的基础上，提出一种基于特征值的模式匹配算法——FLC（First-Last-Characters）算法，该算法打破经典算法有序偏移的思想，突破最大偏移量的限制，实现跳跃式偏移，从而减少偏移次数，有效提升匹配效率.

1 BMHS算法

Horspool提出的BMH算法是对BM算法的简化与改进，而BMHS算法是对BMH算法进一步的改进和优化.BMH和BMHS算法的共同点是简化了BM算法的好后缀规则，只使用其坏字符规则.而BMHS算法则对坏字符规则进行了进一步的改进与优化，它根据当前与模式串尾字符对齐的文本串中字符的下一个字符来决定模式串向右偏移量.如果该字符不在模式串中，则可实现最大右移量.

设文本串为T[0,1,2…n-1]，长度为n；模式串P [0,1,2…m-1]，长度为m.BMHS算法的匹配过程是：文本串T保持不动，模式串P从左向右移动，移动至T[j]处进行匹配，匹配的顺序是自右向左进行的，即先匹配T[j+m-1]和P[m-1]，再比较T[j+m-2]与P[m-2]是否相等，直到比较至T[j]和P[0]处.如果全部相同，则匹配成功；如果在T[i+j]和P[i]处不相等，则使用坏字符规则（设坏字符T[j+m]的值为d）：

（1）如果在模式串P中，找到P[k]处值为d.则模式串P向右偏移，让T[j+m]与P[k]对齐，并从模式串末端开始，从右向左继续比较.如图1所示.

（2）如果在模式串P中，没有找到值为d的字符.则模式串P直接向右偏移m+1位，并从模式串末端开始，从右向左开始新的一轮比较.如图2所示.

BMHS是所有经典算法中，匹配效率较高的算法，其应用成熟而广泛.但BMHS算法也有以下缺陷：①最大偏移量是m+1（未找到坏字符时的偏移量），即偏移量上限是m+1，这意味着，该算法的任何偏移都无法超越该值.②偏移之后，必须进行逐个字符的匹配，这将造成系统资源和时间的浪费，影响匹配效率.③模式串长度越长，在模式串中寻找坏字符消耗的时间就越多，这将延长匹配时间，降低匹配效率.

图1 BMHS算法找到坏字符的偏移情况[11]Fig.1 The deviation case of the bad characters found by the BMHS algorithm[11]

图2 BMS算法未找到坏字符的偏移情况[11]Fig.2 The deviation caseof thebad charactersnot found by the BMHalgorithm[11]

2 FLC算法

通过对经典算法的分析，得出如下结论：（1）在字符匹配过程中，若找到一个不匹配的字符，则匹配失败，后续字符无需继续比较.因此，尽快找到一个不匹配的字符能够缩短匹配时间.（2）模式串的长度越长，字符比较的次数越多，匹配消耗的时间越长.因此，缩短模式串长度能够减少匹配时间.

基于上述结论，本文提出一种基于特征值的模式匹配算法——FLC（First-Last-Characters）算法.

2.1 FLC算法思想

FLC算法的基本思想，是将模式串抽象成一个三元组（首字符，首尾字符间距，尾字符）作为其特征值.在文本串中首先按照特征值进行匹配，利用特征值快速预判匹配成败，实现跳跃式偏移.特征值的使用缩减了模式串的长度，打破了经典算法有序偏移的思想，其偏移量可远远大于BMHS算法的最大偏移量m+1，从而减少偏移次数，提高算法效率.

设模式串是P，长度为m；文本串是T，长度为n，则模式串的特征值为：（P[0]，m-1，P[m-1]）.FLC算法首先在文本串中查找P[m-1]（模式串尾字符），在T[i]处找到后，比较T[i-(m-1)]的字符是否等于P[0]（模式串首字符）.若相等，则特征值匹配成功；否则特征值匹配失败.一般情况下，在一次匹配过程中，文本串中待匹配的字符串与特征值完全吻合的概率较小，即特征值匹配失败的概率较大，而特征值匹配失败意味着模式串匹配失败，从而可继续在文本串中查找下一个特征值，实现跳跃式偏移.

2.2 FLC算法步骤

（1）选取模式串的首字符，尾字符以及它们之间的距离作为特征值，记为（P[0]，m-1，P[m-1]）.

（2）在文本串T[m-1,m,m+1…n-1]中查找模式串尾字符P[m-1].若找到（假设为T[i]），继续步骤（3）；若找不到，则输出匹配失败，程序结束.

（3）比较模式串首字符P[0]与T[i-(m-1)]的值是否相等.若相等，则继续步骤（4）；若不相等，则返回步骤（2）.

（4）将模式串偏移至文本串中特征值尾字符T [i]处对齐，按照从右向左的顺序，模式串P[m-2]，P [m-3]，P[m-4]…P[1]与文本串T[i-1]，T[i-2]，T[i-3]…T[i-(m-2)]进行比较.若所有字符相同，则匹配成功；若有一处字符不相同，则匹配失败.

（5）检查T[i]是否是文本串T的尾字符.若是，则输出匹配成功，程序结束；否则，返回步骤（2）.

2.3 FLC算法分析

在两种极端情况下，对BMHS与FLC算法移动过程的比较分析.

（1）最好情况：BMHS与FLC算法每次偏移均移动最大长度，如图3所示.

设文本串：ecfdrnbfihocaghtrehnoralghm，模式串:alghm

图3 BMS和FLC算法移动过程（最好情况）Fig.3 Themoving processof the BMHS and FLCalgorithm (the bestcase)

BMHS算法偏移了4次，每次的偏移量都在6（即m+1）以内；FLC算法偏移了1次，偏移量为22.最好情况下FLC算法的偏移次数优于BMHS算法.

BMHS算法最大偏移长度是m+1，或者说，BMHS算法偏移量的上限是m+1.FLC算法的偏移量不设上限，其值可远远大于m+1.这是FLC算法在偏移量上优于BMHS算法的主要原因.

（2）最坏情况：BMHS与FLC算法每次偏移均移动最小长度.如图4所示：

设：文本串：aaaammmmaaaammmmaemnmralghm，模式串：alghm

图4 BMS和FLC算法移动过程（最坏情况）Fig.4 Themoving processof the BMHS and FLCalgorithm (theworstcase)

FLC与BMHS算法在最坏情况下偏移次数都为9次，每次偏移量全部相同.在这种情况下，偏移之后字符匹配所消耗时间成为两个算法优劣的关键.

BMHS算法每次匹配要执行两次循环，一次循环确认模式串与其在文本串中对应的字符串是否匹配；一次循环要在模式串中查找文本串中的字符，以确定下一次偏移的位置.FLC算法只要一个循环，确认模式串与其在文本串中对应的字符串是否匹配即可.所以，最坏情况FLC算法消耗的时间少于BMHS算法.

图5显示，在最坏情况下，BMHS算法100万次的循环匹配消耗时间0.234 000秒，FLC算法100万次的循环匹配消耗时间0.109 000秒.FLC算法比BMHS算法快了一倍多.

图5 BMS和FLC算法字符串测试Fig.5 The charactersstring testof the BMHS and FLCalgorithm

综上所述，FLC算法在以两方面优于BMHS算法：（1）BMHS算法的最大偏移长度是m+1；FLC算法的最大偏移长度可远远大于m+1.偏移量越大，偏移次数越少.因此，FLC算法的偏移次数少于BMHS算法.（2）BMHS算法每次匹配需要执行两次循环，一次循环确认匹配成败，一次循环确定偏移位置；FLC算法每次匹配只需要一次循环，即确认匹配成败.因此，FLC算法的匹配时间少于BMHS算法.

3 BMHS与FLC算法性能测试

3.1 算法性能测试

为确保测试数据的准确和有效，BMHS和FLC算法均使用Visual C++6.0语言进行编程实现.实验主机的配置为：Pentium®Dual-Core E5800处理器，3.20 GHz主频，2 GB内存，Windows XP操作系统.使用精确到微秒的时间函数clock()计算每个算法运行一次的时间消耗.

测试随机抽取三个英文文本文件和三个中文文本文件，使用BMHS和FLC算法在六个文本文件中进行关键字匹配测试，通过统计匹配时间和偏移次数对两种算法的性能进行比较.结果如表1所示.

表1 FLC算法与BMHS算法性能测试情况Table 1 FLCand BMHalgorithm performance testcases

表1 FLC算法与BMHS算法性能测试情况Table 1 FLCand BMHalgorithm performance testcases

文本文件JourneyToTheWest.txt The Holy Bible.txt BadBoy.txt Bacchus(chinese).txt GoldenEyes(chinese).txt ZeroBeginning(chinese).txt文本大小（Byte）3 731 245 4 404 443 10 050 008 5 719 511 7 011 504 20 871 525模式串Monkey God look after黑暗恼羞成怒维娜BMHS算法偏移次数（次）616 816 1 177 097 1 320 364 1 216 070 820 747 4 448 296时间（s）0.031 000 0 0.047 000 0 0.093 000 0 0.046 000 0 0.062 000 0 0.188 000 0FLC算法偏移次数（次）104 865 54 308 110 631 107 013 51 232 105 610时间（s）0.016 000 0 0.032 000 0 0.079 000 0 0.031 000 0 0.046 000 0 0.157 000 0

3.2 测试结果分析

如表1所示，英文文本和中文文本都随着文本大小的增加，消耗的时间不断增多，两者成正比.在文本大小相近的情况下，模式串越短，消耗的时间越长.偏移次数与文本大小，模式串长度无明显关系.

（1）将表1里BMHS和FLC算法消耗的时间数据进行横向比较.如图6所示，FLC算法的时间消耗只有BMHS算法的51.61%到84.95%.证明在消耗时间上FLC算法较BMHS算法有一定的优势.

（2）将表1里BMHS和FLC算法在测试中模式串的偏移次数进行横向比较.如图7所示，FLC算法的偏移次数只有BMHS算法0.13%到0.81%，远远少于BMHS算法.由此可见，FLC算法在偏移次数方面较BMHS算法有较大优势，大多数没有必要的偏移都被剔除.FLC算法也是匹配成功次数与偏移次数最接近的算法.

图6 FLC与BMHS算法消耗时间比较Fig.6 Thetime-consum ing comparison of the FLC a nd BMHalgorithm

图7 FLC与BMHS算法偏移次数比较Fig.7 The deviation frequency comparison of FLC algorithm and BMHS algorithm

4 结语

本文在经典算法的基础上，提出了一种基于特征值的模式匹配算法FLC.FLC算法的主要特点有：特征值匹配，跳跃式偏移，不设偏移上限等.对FLC与BMHS算法进行性能对比测试.测试结果表明，FLC算法在偏移次数和时间消耗上有所减少，匹配效率优于BMHS算法.

[1]Charras C,Lecroq T.Brute force algorithm[EB/OL].(1997-03-04) [2014-04-26].http://www.r-igm.univ-mlv.fr/～lecroq/string/node3. htm l.

[2]Knuth D E,Morris JH,Pratt V R.Fast pattern matching in string [J].SLAM Journalon Computing,1977,6(6):323-350.

[3]Boyer R S,Moore JS.A fast string searching algorithm[J].Communication of the ACM,1977,20(10):762-772.

[4]Franek F,Jennings CG,Smyth PW F.A simple fasthybrid ptternmatching algorithm[J].Journal of Discrete Algorithms,2007,4(5): 682-695.

[5]李玉峰,杨婷,卜永波.Linux下基于Netfilter/Iptables防火墙的研究与应用[J].内蒙古农业大学学报:自然科学版,2012(1):15-19.

[6]Nigel-Horspool R.Practical fast searching in strings[J].Practice and Experience,1980,10(6):501-506.

[7]Daniel M S.Very fast substring search algorithm[J].Communicationsof the ACM,1990,33(8):132-142.

[8]陈瀛.改进的字符串查找算法[J].机电产品开发与创新，2007 (3):140-141.

[9]姚亚峰,方贤进,赛文莉.新型内容过滤防火墙的研究[J].计算机技术与发展,2010(11):3-4.

[10]刘胜飞,张云泉.一种改进的BMH模式匹配算法[J].计算机科学,2008,35(11):164-173.

[11]张娜.内容过滤防火墙的设计与实现[D].合肥:合肥工业大学, 2006.

【编校：许洁】

Pattern Matching Algorithm Based on Feature Value

YU Fei,LIU Sihong
(Software College,AnhuiVocationalCollegeofElectronics&Information Technology,Bengbu,Anhui233060,China)

Amethod was proposed for the first time to use the FLC(First-Last-Characters)algorithm based on eigenvalue.It broke through the idea of orderly deviation with classical algorithm and the upper limit of deviation(m+1)with BMHS(Boyer-Moore-Horspool-Sunday)so that it increased the offset distance and reduced thematch time.The test resultof thisalgorithm shows that thematch of FLCalgorithm ismoreefficient than BMHSalgorithm.

patternmatching;BMHS;FLC

TP301.6

A

1671-5365(2014)12-0077-05

2014-07-03修回：2014-09-05

安徽电子信息职业技术学院教科研项目“基于数据挖掘技术的高职院校招生决策系统研究与应用”（ADZX1306）

余飞（1983-），男，硕士，讲师，研究方向为计算机网络安全、数据挖掘、分布式操作系统

时间：2014-09-12 13:00

http://www.cnki.net/kcms/detail/51.1630.Z.20140912.1300.004.htm l