蔡婷++楊衛(wèi)帥

摘 要：高效快速的字符串模式匹配算法有助于網(wǎng)絡(luò)信息處理的相關(guān)應(yīng)用。文章在分析相關(guān)字符串匹配算法的基礎(chǔ)之上，針對(duì)模式串中字符重復(fù)次數(shù)較多匹配應(yīng)用，提出了一種快速的字符串匹配改進(jìn)算法。該算法利用文本串中當(dāng)前失敗字符與模式串右對(duì)齊端的文本串下一個(gè)字符來(lái)啟發(fā)模式串向右移動(dòng)。結(jié)合這兩個(gè)字符在模式串中匹配的情況及以這兩個(gè)字符為首末的特征字符串在模式串中的匹配情況來(lái)使計(jì)算模式串向右移動(dòng)最大距離，盡可能地排除無(wú)效匹配。實(shí)驗(yàn)結(jié)果表明，該算法能有效減少模式匹配中字符的比較次數(shù)，提高模式匹配效率。

關(guān)鍵詞：字符串匹配；KMP算法；BM算法；Sunday算法；移動(dòng)距離

中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2095-1302（2017）07-00-03

0 引 言

隨著信息技術(shù)的高速發(fā)展，如何在海量數(shù)據(jù)中提取有用信息是網(wǎng)絡(luò)信息技術(shù)研究的熱點(diǎn)。字符串模式匹配主要用于文本串的處理領(lǐng)域，如信息檢索、拼寫(xiě)檢查、數(shù)據(jù)處理、信息測(cè)試、數(shù)據(jù)壓縮、搜索引擎、網(wǎng)絡(luò)入侵檢測(cè)、DNA序列匹配等。如何用高效快速的字符串模式匹配算法解決網(wǎng)絡(luò)信息處理的相關(guān)問(wèn)題已成為目前研究的重要領(lǐng)域之一。

字符串匹配問(wèn)題的形式化定義是[1]：在有限字母表∑上的字符序列上，給定一個(gè)長(zhǎng)度為n的文本串T[0…n-1]以及一個(gè)長(zhǎng)度為m的模式串P[0…m-1]，m

1 相關(guān)算法介紹

1.1 KMP算法

KMP算法是經(jīng)典的字符串匹配算法，主要在模式匹配過(guò)程中執(zhí)行T[i]和P[j]的匹配檢查。若T[i]=P[j]，則繼續(xù)匹配T[i+1]與P[j+1]；若T[i]≠P[j]，則分成兩種情況：若j=0，模式串P向右移一位，繼續(xù)匹配T[i+1]和P[0]；若1

（1）

其中：

1.2 Horspool算法

Horspool算法是字符串匹配算法中從右向左匹配的創(chuàng)始者。當(dāng)失配發(fā)生時(shí)，模式串P要向右移動(dòng)，T串的失配字符T[i]可能是正確結(jié)果中的一個(gè)元素，也可能不是。如果不是，可將P串的首位與T串中的T[i+1]對(duì)齊，繼續(xù)進(jìn)行比較；如果是，那么從P串失配位置j開(kāi)始向左任意一位與P[i]相等的字符c確定的比較位置可能完全匹配，其產(chǎn)生的位移依次為k1，k2…，ki（k1為j-location（c））。綜合這兩種情況，選擇位移最小值k1，以保證不會(huì)錯(cuò)過(guò)正確匹配的情況。

1.3 BM算法

BM（Boyer-Moore，BM）算法是基于Horspool算法的一種改進(jìn)算法，其廣泛應(yīng)用于實(shí)際項(xiàng)目中。BM算法實(shí)際包含兩個(gè)并行算法，壞字符算法和好后綴算法。匹配時(shí)，同Horspool算法；當(dāng)失配時(shí)，計(jì)算P串失配字符的右邊已經(jīng)匹配的字符串（稱為“好后綴”），在P串中其他位置出現(xiàn)的位置得到一個(gè)右移大小值（實(shí)際該值是預(yù)先計(jì)算好的），將該值與Horspool失配時(shí)P串移動(dòng)大小的值進(jìn)行比較，并選擇其中較大者。P串移動(dòng)后，繼續(xù)進(jìn)行比較。

1.4 Sunday算法

Sunday算法是一種高效算法，可以看成BM算法的簡(jiǎn)化形式。在匹配過(guò)程中，模式串P不一定要按從左向右的順序比較或從右向左進(jìn)行匹配。在失配情況下，選中T串與P串右對(duì)齊端的下一個(gè)字符T[i]，從P串末位向左尋找與該字符相等的字符P[j]，找到后，T[i]與P[j]對(duì)齊，繼續(xù)從右到左比較；若找不到，則P串左端與T[i]的下一個(gè)字符對(duì)齊，從右到左比較。

2 改進(jìn)的字符串匹配算法

字符串模式匹配算法要解決的關(guān)鍵問(wèn)題是在模式與文本某個(gè)位置比較失敗時(shí)，如何使模式串窗口向右移動(dòng)最佳距離，盡量跳過(guò)無(wú)需比較的字符，減少匹配次數(shù)，并使產(chǎn)生這種距離的算法復(fù)雜度降低且易于理解。通過(guò)對(duì)現(xiàn)有各種字符串匹配算法的研究，我們提出一種改進(jìn)算法，該算法主要針對(duì)模式串重復(fù)率較多的情況使用。當(dāng)文本串T與模式串P發(fā)生匹配時(shí)，判斷模式串最右端對(duì)應(yīng)文本串下一個(gè)字符Ti+m是否在模式串中，若不在，匹配規(guī)則同Sunday算法；若在，記下在模式串P0P1…Pm-1中的位置q，同時(shí)記下文本串中當(dāng)前失敗的字符Ti+j在模式串P0P1…Pj-1出現(xiàn)的位置k，根據(jù)q、k的值以及Ti+j+1Ti+j+2…Ti+m-1與Pk+1Pk+2…Pm-1的比較情況來(lái)計(jì)算模式串向右移動(dòng)的最大距離。

2.1 比較順序

與BM算法類似，在模式串的匹配過(guò)程中，字符串采用從右向左的順序依次比較。

2.2 模式串移動(dòng)距離的確定

假設(shè)當(dāng)前匹配的比較窗口是TiTi+1…Ti+m-1，在某次比較過(guò)程中失敗于Pj處，即后m-j個(gè)字符匹配成功：Ti+j+1Ti+j+2…Ti+m-1=Pj+1Pj+2…Pm-1，而Ti+j≠Pj，如圖1所示。