提出了改進的AC-BM算法，將待匹配的字符串集合轉換為一個類似于Aho-Corasick算法的樹狀有限狀態自動機。匹配時，采取自后向前的方法，并借用BM算法的壞字符跳轉和好前綴跳轉技術。改進的AC-BM算法借助BMH算法思想，取消了原AC-BM算法的好前綴跳轉，并對壞字符跳轉部分的計算進行優化。新算法修改了skip的計算方法，不再保留每個節點的好前綴跳轉參數及壞字符跳轉參數，因此匹配只與當前匹配字符有關，而與當前節點無關，可以實現大小寫正文的識別。
關 鍵 詞 算法; 字符串匹配; 內容分析; 入侵檢測

Abstract ACBM is a Boyer-Moore like algorithm applied to a set of keywords held in an Aho-Corassick like keyword tree that overlays common prefixes of the keywords. The algorithm takes the best characteristics of both the Boyer-Moore and Aho-Corasick. Based on the idea of Boyer-Moore-Horspool, we make an improvement to AC-BM algorithm. In the improved version, the Good Prefix Shift is not performed, the Bad Character Shift function is improved, the Goto procedure is also modified which do not keep the parameters of Good Prefix Shift and Bad Character Shift.
Key words algorithm; string matching; content analysis; intrusion detection
字符串匹配是指在文本Textt=t1t2…tn中檢索子串Patp=p1p2…pm的所有出現。字符串匹配可分為單字符串匹配和字符串集合匹配兩種。單字符串匹配算法最著名的是KMP(Knuth-Morris-Pratt)算法和BM(Boyer-Moore)算法。KMP算法實現了無回溯匹配，字符串中的每個字符只匹配一次，時間復雜度為O(n+m)[1]；BM算法采用跳躍方式，匹配時跳過不需匹配的字符，最優情況下的時間復雜度為O(n/m)，平均情況下也大大優于KMP算法[2]；文獻[3]取掉BM算法的好后綴試探(Good Suffix Heuristic)，形成BMH(Boyer-Moore-Horspool)算法，實驗證明BMH算法性能在自然語言環境下比原始BM算法還要好。
字符串集合匹配是從文本Text中一次查找多個字符串P1，P2，…，Pm的所有出現，最經典的是AC(Aho and Corasick)算法。該算法將待匹配的多個字符串轉換為樹狀有限狀態自動機，然后進行掃描匹配，最優情況和平均情況的時間復雜度都為O(n)[4]；文獻[5]提出了一種類似于AC和BM的算法，即Aho-Corasick_Boyer-Moore(AC_BM)混合算法。該算法根據包過濾的規則前綴共同信息較多的特點，采取自后向前的搜索方法，因此在速度方面具有較高的優越性[6]。
本文對AC-BM算法提出改進，并根據BMH算法的思想，取消好前綴跳轉(Good Prefix Shift)，測試結果表明，該算法在數據包過濾、內容分析與審計等應用中，優于AC-BM算法。
1 AC-BM算法描述
AC-BM算法將待匹配的字符串集合轉換為一個類似于Aho-Corasick算法的樹狀有限狀態自動機，但構建時不是基于字符串的后綴而是前綴。匹配時，采取自后向前的方法，并借用BM算法的壞字符跳轉(BadCharacter Shift)和好前綴跳轉(Good Prefix Shift)技術。
壞字符跳轉即當字符串樹中的字符與被匹配內容x失配時，將字符串樹跳轉到下一個x的出現位置，如果x的字符串樹不存在，則將字符串樹向左移動字符串樹的最小字符串長度。好前綴跳轉即當字符串樹中的字符與被匹配內容x失配時，將字符串樹跳轉到字符串樹中一個與被測正文部分等同的位置。這個等同部分可以是字符串樹中某字符串的子串(子串跳轉)，也可以是一個字符串的后綴(后綴跳轉)。
例如，設有規則ethernetmovesme，ethernetisking，ethernetisdead和ethernetforever，要檢查的數據包內容為nothingtoworryaboutinthis。首先，構造字符串有限狀態自動機，如圖1a。匹配從字符r開始,顯然r與e不匹配，由于字符串樹中下一個r出現在深度5的位置，字符串樹的最小字符串長度為14，根據壞字符跳轉，字符串樹可以安全向左移動5個字符，如圖1b。