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

余飛，劉思宏

（安徽電子信息職業(yè)技術(shù)學(xué)院軟件學(xué)院，安徽蚌埠233060）

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

余飛，劉思宏

（安徽電子信息職業(yè)技術(shù)學(xué)院軟件學(xué)院，安徽蚌埠233060）

提出一種基于特征值的模式匹配算法——FLC（First-Last-Characters）算法，可打破經(jīng)典算法有序偏移的思想，突破BMHS（Boyer-Moore-Horspool-Sunday）算法最大偏移量（m+1）的上限，從而增大偏移距離，減少匹配時(shí)間.測試結(jié)果表明：FLC算法的匹配效率優(yōu)于BMHS算法.

模式匹配；BMHS；FLC

模式（Schema）是指按照某種結(jié)構(gòu)組織起來的多個(gè)元素的集合.模式匹配指將兩個(gè)模式作為輸入，計(jì)算模式元素之間語義上的對應(yīng)關(guān)系的過程.模式匹配的關(guān)鍵是匹配方法.模式匹配算法就是用來描述匹配方法及過程的.

經(jīng)典的模式匹配算法采用文本串保持不動(dòng)，模式串有序偏移的方式進(jìn)行字符匹配.最早的BF（Brute Force）算法[1]就是一種有序查找算法，它將模式串（匹配對象）與文本串（被匹配對象）按位從左到右依次進(jìn)行比較.如果完全相同，則匹配成功；若有一個(gè)字符不同，則匹配不成功，模式串向右移動(dòng)一個(gè)字符的位置，繼續(xù)比較，直到將文本串的所有位都進(jìn)行比較.BF算法實(shí)現(xiàn)簡單，但模式串每次僅偏移一個(gè)字符，這導(dǎo)致模式串幾乎要與文本串中的每一個(gè)字符進(jìn)行比較，運(yùn)行效率極其低下.

KMP算法[2]是BF的一種改進(jìn)算法，該算法由Knuth等人提出.KMP算法根據(jù)給定的模式串，定義一個(gè)next函數(shù).模式串與文本串按順序進(jìn)行從左到右匹配，若匹配不成功，next函數(shù)將給出模式串向右移動(dòng)的位置，即模式串與文本串重新開始比較的起始位.KMP算法的創(chuàng)新之處在于，利用next函數(shù)能夠科學(xué)計(jì)算出模式串偏移距離，解決了BF算法中模式串偏移的盲目性，實(shí)現(xiàn)了其大幅度的有序偏移，提高了匹配效率，為后續(xù)研究奠定了基礎(chǔ).

1977年，Boyer和Moore提出了一種著名的單模式匹配算法——BM算法[3-4]，該算法使用壞字符規(guī)則（Bad Character）和好后綴規(guī)則（Good Suffix）來計(jì)算模式串右移距離，實(shí)現(xiàn)模式串的跳躍式偏移.BM算法效率較BF和KMP算法有顯著的提高，也開始投入實(shí)用，應(yīng)用于入侵檢測系統(tǒng)，防火墻系統(tǒng)[5]等.

此后，對BM算法的改進(jìn)成為該領(lǐng)域的熱門，重要的改進(jìn)算法有1980年Horspool提出的BMH（Boyer-Moore-Horspool）算法[6]和1990年Sunday提出的BMHS（Boyer-Moore-Horspool-Sunday）算法[7].BMH與BMHS算法的改進(jìn)集中在模式串與文本串失配后模式串偏移量的計(jì)算，減少了匹配次數(shù)和消耗時(shí)間，匹配效率得到提升.

近幾年對模式匹配算法的研究主要集中在對算法的改進(jìn)與應(yīng)用上.陳瀛等將數(shù)理統(tǒng)計(jì)的方法帶入模式匹配算法[8]，運(yùn)用抽樣統(tǒng)計(jì)理論從文本串中采集可能與模式串匹配成功的抽樣點(diǎn)，在其周圍進(jìn)行精確匹配.姚亞鋒等提出了AC-BM算法[9]，該算法結(jié)合了AC算法與BM算法兩種經(jīng)典算法的優(yōu)長，顯著提高了效率.劉勝飛、張?jiān)迫贐MH算法的基礎(chǔ)上提出BMH2算法[10-11]，該算法增加了一個(gè)移動(dòng)距離的特征數(shù)組，來輔助模式串進(jìn)行最大幅度的偏移.

本文在探討經(jīng)典算法的基礎(chǔ)上，提出一種基于特征值的模式匹配算法——FLC（First-Last-Characters）算法，該算法打破經(jīng)典算法有序偏移的思想，突破最大偏移量的限制，實(shí)現(xiàn)跳躍式偏移，從而減少偏移次數(shù)，有效提升匹配效率.

1 BMHS算法

Horspool提出的BMH算法是對BM算法的簡化與改進(jìn)，而BMHS算法是對BMH算法進(jìn)一步的改進(jìn)和優(yōu)化.BMH和BMHS算法的共同點(diǎn)是簡化了BM算法的好后綴規(guī)則，只使用其壞字符規(guī)則.而BMHS算法則對壞字符規(guī)則進(jìn)行了進(jìn)一步的改進(jìn)與優(yōu)化，它根據(jù)當(dāng)前與模式串尾字符對齊的文本串中字符的下一個(gè)字符來決定模式串向右偏移量.如果該字符不在模式串中，則可實(shí)現(xiàn)最大右移量.

設(shè)文本串為T[0,1,2…n-1]，長度為n；模式串P [0,1,2…m-1]，長度為m.BMHS算法的匹配過程是：文本串T保持不動(dòng)，模式串P從左向右移動(dòng)，移動(dòng)至T[j]處進(jìn)行匹配，匹配的順序是自右向左進(jìn)行的，即先匹配T[j+m-1]和P[m-1]，再比較T[j+m-2]與P[m-2]是否相等，直到比較至T[j]和P[0]處.如果全部相同，則匹配成功；如果在T[i+j]和P[i]處不相等，則使用壞字符規(guī)則（設(shè)壞字符T[j+m]的值為d）：

（1）如果在模式串P中，找到P[k]處值為d.則模式串P向右偏移，讓T[j+m]與P[k]對齊，并從模式串末端開始，從右向左繼續(xù)比較.如圖1所示.

（2）如果在模式串P中，沒有找到值為d的字符.則模式串P直接向右偏移m+1位，并從模式串末端開始，從右向左開始新的一輪比較.如圖2所示.

BMHS是所有經(jīng)典算法中，匹配效率較高的算法，其應(yīng)用成熟而廣泛.但BMHS算法也有以下缺陷：①最大偏移量是m+1（未找到壞字符時(shí)的偏移量），即偏移量上限是m+1，這意味著，該算法的任何偏移都無法超越該值.②偏移之后，必須進(jìn)行逐個(gè)字符的匹配，這將造成系統(tǒng)資源和時(shí)間的浪費(fèi)，影響匹配效率.③模式串長度越長，在模式串中尋找壞字符消耗的時(shí)間就越多，這將延長匹配時(shí)間，降低匹配效率.

圖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算法

通過對經(jīng)典算法的分析，得出如下結(jié)論：（1）在字符匹配過程中，若找到一個(gè)不匹配的字符，則匹配失敗，后續(xù)字符無需繼續(xù)比較.因此，盡快找到一個(gè)不匹配的字符能夠縮短匹配時(shí)間.（2）模式串的長度越長，字符比較的次數(shù)越多，匹配消耗的時(shí)間越長.因此，縮短模式串長度能夠減少匹配時(shí)間.

基于上述結(jié)論，本文提出一種基于特征值的模式匹配算法——FLC（First-Last-Characters）算法.

2.1 FLC算法思想

FLC算法的基本思想，是將模式串抽象成一個(gè)三元組（首字符，首尾字符間距，尾字符）作為其特征值.在文本串中首先按照特征值進(jìn)行匹配，利用特征值快速預(yù)判匹配成敗，實(shí)現(xiàn)跳躍式偏移.特征值的使用縮減了模式串的長度，打破了經(jīng)典算法有序偏移的思想，其偏移量可遠(yuǎn)遠(yuǎn)大于BMHS算法的最大偏移量m+1，從而減少偏移次數(shù)，提高算法效率.

設(shè)模式串是P，長度為m；文本串是T，長度為n，則模式串的特征值為：（P[0]，m-1，P[m-1]）.FLC算法首先在文本串中查找P[m-1]（模式串尾字符），在T[i]處找到后，比較T[i-(m-1)]的字符是否等于P[0]（模式串首字符）.若相等，則特征值匹配成功；否則特征值匹配失敗.一般情況下，在一次匹配過程中，文本串中待匹配的字符串與特征值完全吻合的概率較小，即特征值匹配失敗的概率較大，而特征值匹配失敗意味著模式串匹配失敗，從而可繼續(xù)在文本串中查找下一個(gè)特征值，實(shí)現(xiàn)跳躍式偏移.

2.2 FLC算法步驟

（1）選取模式串的首字符，尾字符以及它們之間的距離作為特征值，記為（P[0]，m-1，P[m-1]）.

（2）在文本串T[m-1,m,m+1…n-1]中查找模式串尾字符P[m-1].若找到（假設(shè)為T[i]），繼續(xù)步驟（3）；若找不到，則輸出匹配失敗，程序結(jié)束.

（3）比較模式串首字符P[0]與T[i-(m-1)]的值是否相等.若相等，則繼續(xù)步驟（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)]進(jìn)行比較.若所有字符相同，則匹配成功；若有一處字符不相同，則匹配失敗.

（5）檢查T[i]是否是文本串T的尾字符.若是，則輸出匹配成功，程序結(jié)束；否則，返回步驟（2）.

2.3 FLC算法分析

在兩種極端情況下，對BMHS與FLC算法移動(dòng)過程的比較分析.

（1）最好情況：BMHS與FLC算法每次偏移均移動(dòng)最大長度，如圖3所示.

設(shè)文本串：ecfdrnbfihocaghtrehnoralghm，模式串:alghm

圖3 BMS和FLC算法移動(dòng)過程（最好情況）Fig.3 Themoving processof the BMHS and FLCalgorithm (the bestcase)

BMHS算法偏移了4次，每次的偏移量都在6（即m+1）以內(nèi)；FLC算法偏移了1次，偏移量為22.最好情況下FLC算法的偏移次數(shù)優(yōu)于BMHS算法.

BMHS算法最大偏移長度是m+1，或者說，BMHS算法偏移量的上限是m+1.FLC算法的偏移量不設(shè)上限，其值可遠(yuǎn)遠(yuǎn)大于m+1.這是FLC算法在偏移量上優(yōu)于BMHS算法的主要原因.

（2）最壞情況：BMHS與FLC算法每次偏移均移動(dòng)最小長度.如圖4所示：

設(shè)：文本串：aaaammmmaaaammmmaemnmralghm，模式串：alghm

圖4 BMS和FLC算法移動(dòng)過程（最壞情況）Fig.4 Themoving processof the BMHS and FLCalgorithm (theworstcase)

FLC與BMHS算法在最壞情況下偏移次數(shù)都為9次，每次偏移量全部相同.在這種情況下，偏移之后字符匹配所消耗時(shí)間成為兩個(gè)算法優(yōu)劣的關(guān)鍵.

BMHS算法每次匹配要執(zhí)行兩次循環(huán)，一次循環(huán)確認(rèn)模式串與其在文本串中對應(yīng)的字符串是否匹配；一次循環(huán)要在模式串中查找文本串中的字符，以確定下一次偏移的位置.FLC算法只要一個(gè)循環(huán)，確認(rèn)模式串與其在文本串中對應(yīng)的字符串是否匹配即可.所以，最壞情況FLC算法消耗的時(shí)間少于BMHS算法.

圖5顯示，在最壞情況下，BMHS算法100萬次的循環(huán)匹配消耗時(shí)間0.234 000秒，F(xiàn)LC算法100萬次的循環(huán)匹配消耗時(shí)間0.109 000秒.FLC算法比BMHS算法快了一倍多.

圖5 BMS和FLC算法字符串測試Fig.5 The charactersstring testof the BMHS and FLCalgorithm

綜上所述，F(xiàn)LC算法在以兩方面優(yōu)于BMHS算法：（1）BMHS算法的最大偏移長度是m+1；FLC算法的最大偏移長度可遠(yuǎn)遠(yuǎn)大于m+1.偏移量越大，偏移次數(shù)越少.因此，F(xiàn)LC算法的偏移次數(shù)少于BMHS算法.（2）BMHS算法每次匹配需要執(zhí)行兩次循環(huán)，一次循環(huán)確認(rèn)匹配成敗，一次循環(huán)確定偏移位置；FLC算法每次匹配只需要一次循環(huán)，即確認(rèn)匹配成敗.因此，F(xiàn)LC算法的匹配時(shí)間少于BMHS算法.

3 BMHS與FLC算法性能測試

3.1 算法性能測試

為確保測試數(shù)據(jù)的準(zhǔn)確和有效，BMHS和FLC算法均使用Visual C++6.0語言進(jìn)行編程實(shí)現(xiàn).實(shí)驗(yàn)主機(jī)的配置為：Pentium?Dual-Core E5800處理器，3.20 GHz主頻，2 GB內(nèi)存，Windows XP操作系統(tǒng).使用精確到微秒的時(shí)間函數(shù)clock()計(jì)算每個(gè)算法運(yùn)行一次的時(shí)間消耗.

測試隨機(jī)抽取三個(gè)英文文本文件和三個(gè)中文文本文件，使用BMHS和FLC算法在六個(gè)文本文件中進(jìn)行關(guān)鍵字匹配測試，通過統(tǒng)計(jì)匹配時(shí)間和偏移次數(shù)對兩種算法的性能進(jìn)行比較.結(jié)果如表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文本大?。˙yte）3 731 245 4 404 443 10 050 008 5 719 511 7 011 504 20 871 525模式串Monkey God look after黑暗惱羞成怒維娜BMHS算法偏移次數(shù)（次）616 816 1 177 097 1 320 364 1 216 070 820 747 4 448 296時(shí)間（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算法偏移次數(shù)（次）104 865 54 308 110 631 107 013 51 232 105 610時(shí)間（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 測試結(jié)果分析

如表1所示，英文文本和中文文本都隨著文本大小的增加，消耗的時(shí)間不斷增多，兩者成正比.在文本大小相近的情況下，模式串越短，消耗的時(shí)間越長.偏移次數(shù)與文本大小，模式串長度無明顯關(guān)系.

（1）將表1里BMHS和FLC算法消耗的時(shí)間數(shù)據(jù)進(jìn)行橫向比較.如圖6所示，F(xiàn)LC算法的時(shí)間消耗只有BMHS算法的51.61%到84.95%.證明在消耗時(shí)間上FLC算法較BMHS算法有一定的優(yōu)勢.

（2）將表1里BMHS和FLC算法在測試中模式串的偏移次數(shù)進(jìn)行橫向比較.如圖7所示，F(xiàn)LC算法的偏移次數(shù)只有BMHS算法0.13%到0.81%，遠(yuǎn)遠(yuǎn)少于BMHS算法.由此可見，F(xiàn)LC算法在偏移次數(shù)方面較BMHS算法有較大優(yōu)勢，大多數(shù)沒有必要的偏移都被剔除.FLC算法也是匹配成功次數(shù)與偏移次數(shù)最接近的算法.

圖6 FLC與BMHS算法消耗時(shí)間比較Fig.6 Thetime-consum ing comparison of the FLC a nd BMHalgorithm

圖7 FLC與BMHS算法偏移次數(shù)比較Fig.7 The deviation frequency comparison of FLC algorithm and BMHS algorithm

4 結(jié)語

本文在經(jīng)典算法的基礎(chǔ)上，提出了一種基于特征值的模式匹配算法FLC.FLC算法的主要特點(diǎn)有：特征值匹配，跳躍式偏移，不設(shè)偏移上限等.對FLC與BMHS算法進(jìn)行性能對比測試.測試結(jié)果表明，F(xiàn)LC算法在偏移次數(shù)和時(shí)間消耗上有所減少，匹配效率優(yōu)于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防火墻的研究與應(yīng)用[J].內(nèi)蒙古農(nóng)業(yè)大學(xué)學(xué)報(bào):自然科學(xué)版,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ìn)的字符串查找算法[J].機(jī)電產(chǎn)品開發(fā)與創(chuàng)新，2007 (3):140-141.

[9]姚亞峰,方賢進(jìn),賽文莉.新型內(nèi)容過濾防火墻的研究[J].計(jì)算機(jī)技術(shù)與發(fā)展,2010(11):3-4.

[10]劉勝飛,張?jiān)迫?一種改進(jìn)的BMH模式匹配算法[J].計(jì)算機(jī)科學(xué),2008,35(11):164-173.

[11]張娜.內(nèi)容過濾防火墻的設(shè)計(jì)與實(shí)現(xiàn)[D].合肥:合肥工業(yè)大學(xué), 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

安徽電子信息職業(yè)技術(shù)學(xué)院教科研項(xiàng)目“基于數(shù)據(jù)挖掘技術(shù)的高職院校招生決策系統(tǒng)研究與應(yīng)用”（ADZX1306）

余飛（1983-），男，碩士，講師，研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)安全、數(shù)據(jù)挖掘、分布式操作系統(tǒng)

時(shí)間：2014-09-12 13:00

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