一種新的特征值的模式匹配算法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