一種快速的單模式匹配算法

摘要：在對(duì)Boyer Moore(BM)算法及其改進(jìn)的Tuned Boyer Moore(TunedBM)算法進(jìn)行分析的基礎(chǔ)上，提出了一種更加快速的單模式匹配算法——NFS。該算法利用當(dāng)前嘗試中匹配失敗字符的位置信息進(jìn)行更大的嘗試位置移動(dòng)，使算法具有更高的效率。實(shí)驗(yàn)結(jié)果表明，NFS算法的性能優(yōu)于同類的其他算法，特別是在模式長(zhǎng)度較短的情況下，優(yōu)勢(shì)更為明顯。

關(guān)鍵詞：模式匹配；BM算法；TunedBM算法；新的快速搜索算法

中圖分類號(hào)：TP301．6文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001－3695(2008)01－0045－02



0引言

模式匹配是計(jì)算機(jī)技術(shù)領(lǐng)域的一個(gè)基本問(wèn)題。它在入侵檢測(cè)、數(shù)據(jù)壓縮、WWW搜索引擎以及計(jì)算機(jī)病毒特征碼匹配等系統(tǒng)中都有十分重要的應(yīng)用價(jià)值。模式匹配就是在給定的文本串中查找模式串的出現(xiàn)次數(shù)。若出現(xiàn)次數(shù)為0，稱匹配失敗；若出現(xiàn)的次數(shù)大于或等于1，則稱匹配成功。

本文使用P=P[0..m-1]表示要匹配的模式串，長(zhǎng)度為m；文本串表示為T=T[0..n 1]，長(zhǎng)度為n；字符表以Σ表示，大小為σ。將匹配過(guò)程中P與T中長(zhǎng)度為m的子串作一次比較稱為一次嘗試，并將當(dāng)前嘗試中與模式串對(duì)齊的T的子串稱為當(dāng)前窗口。

在通常應(yīng)用中，BM[1]算法被看做是最有效的單模式匹配算法。它采用從右向左的比較方式，并利用當(dāng)前嘗試中的已匹配信息和匹配失敗的字符，查找預(yù)處理好的好后綴跳躍表(good suffix shift table)和壞字符跳躍表(bad character shift table)，使嘗試跳躍式地進(jìn)行。其最大可能跳躍距離為m。TunedBM[2]算法則是BM算法的簡(jiǎn)化實(shí)現(xiàn)。由于它只使用了壞字符跳躍表，有效地減少了字符比較次數(shù)，在實(shí)際應(yīng)用中效率比BM算法高，但最壞情況時(shí)的性能不如BM。本文在對(duì)這兩種算法進(jìn)行簡(jiǎn)要介紹和分析的基礎(chǔ)上，綜合兩者之長(zhǎng)，提出了一種更加快速的單模式匹配算法，即NFS。該算法充分利用當(dāng)前嘗試中匹配失敗字符的位置信息，以期在每一次跳躍中跳躍盡量大的距離。實(shí)驗(yàn)結(jié)果表明，與其他同類算法相比，NFS算法更加有效。尤其是在模式長(zhǎng)度較短的情況下，表現(xiàn)出優(yōu)越的查找性能。考慮到漢語(yǔ)詞的平均長(zhǎng)度約為4 Byte，故該算法對(duì)中文信息處理中的信息檢索問(wèn)題尤為適用。

1BM和TunedBM算法

1)BM算法

BM算法在當(dāng)前窗口中對(duì)模式P自右向左進(jìn)行掃描。當(dāng)匹配失敗或完全匹配時(shí)，用兩個(gè)預(yù)先計(jì)算的偏移函數(shù)BadCha racter和GoodSuffix來(lái)確定文本指針的右移距離。該算法預(yù)處理階段的時(shí)間復(fù)雜度為O(m+σ)；匹配階段的時(shí)間復(fù)雜度為O(mn)，但當(dāng)匹配一個(gè)非周期化的模式時(shí)至多需要匹配3n個(gè)文本字符，最好情況下的時(shí)間復(fù)雜度為O(n/m)。

2)TunedBM算法

考慮到字符的比較操作是模式匹配算法中最費(fèi)時(shí)的部分，可以在實(shí)際比較前盡量向前移動(dòng)模式。TunedBM算法只使用了BadCharacter偏移函數(shù)。在匹配階段，算法在文本串中查找P[m-1](即模式P的最后一個(gè)字符)。若不匹配則指針一直向前移動(dòng)，直到找到它。在找到P[m-1]的情況下，再比較模式中的其他字符。此后無(wú)論相等與否都將使文本指針向前移動(dòng)P[m-1]對(duì)應(yīng)的偏移位置。預(yù)處理階段的時(shí)間復(fù)雜度為O(m+σ)。匹配階段時(shí)間復(fù)雜度最壞情況下可達(dá)到平方級(jí)，但在實(shí)際應(yīng)用中效率很高。

2NFS算法

進(jìn)一步提高模式匹配算法效率的主要途徑是利用當(dāng)前嘗試中可以獲取的信息進(jìn)一步增大跳躍距離。綜合BM和TunedBM算法的優(yōu)點(diǎn)，本文提出了NFS算法。它采用TunedBM的BadCharacter和BM的GoodSuffix對(duì)模式進(jìn)行預(yù)處理；然后根據(jù)當(dāng)前嘗試中匹配失敗字符的位置信息，決定是查找好后綴跳躍表還是壞字符跳躍表，以期獲得更大的跳躍距離。算法分為模式的預(yù)處理階段和文本的查找階段。

2．1預(yù)處理階段

預(yù)處理階段的任務(wù)是計(jì)算BadCharacter和GoodSuffix兩個(gè)偏移量函數(shù)。

1)BadCharacter函數(shù)的計(jì)算

5結(jié)束語(yǔ)

NFS算法綜合了BM和TunedBM算法的優(yōu)點(diǎn)，使每一次匹配不成功后都能跳過(guò)盡可能多的字符以進(jìn)行下一輪匹配，有效地提高了匹配速度。由于查找問(wèn)題的普遍性，該方法具有廣闊的應(yīng)用前景。

參考文獻(xiàn)：

［1］BOYER R S，MOORE J S.A fast string searching algorithm[J].Commun ACM，1977，20(10):762 772.

[2]CHARRAS C，LECROR T.Exact string matching algorithms[EB/OL].(1997).http://www igm.univ mlv.fr/~lecroq/string/.

[3]COLE R.Tight bounds on the complexity of the Boyer Moore string matching algorithm[J].SIAM J Comput，1994，23(5):1075 1091.

[4]LECROQ T.Experimental results on string matching algorithms[J].Software Practice and Experience，1995，25(7):727 765.

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

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”