深度報文檢測基礎之BM演算法

摘要

BM（Boyer-Moore）演算法是單模式匹配的字元串搜索演算法，相對經典的KMP字元串匹配演算法，效率更好。在模式串長度大的時候效率更高。演算法需要對模式串進行預處理，處理過後，在搜索過程中就可以最大減少字元比較次數，以此提高效率。BM演算法主要三個特點：從模式串最右開始進行匹配；壞字元表；好後綴表。基本思路就是從右往左進行字元匹配，遇到不匹配的字元後從壞字元表和好後綴表找一個最大的右移值，將模式串右移繼續匹配。

1 壞字元

如果字元在模式串中沒有出現，則認為上一次出現的位置為-1。-1意思是啥呢？就是右移之後模式串首部與壞字元出現的後一個字元對齊。

右移位數 = 壞字元出現的位置 – 壞字元在模式串中上一次出現的位置

對於模式串EXAMPLE，計算字母P的右移位數 ： P的位置為5，上一次出現的位置是-1（沒有出現），則右移位數為：5 - （-1）= 6，對於模式串中最後出現的 。

代碼如下：

void preBmBC(char *pat, int m, int BmBC[]) { int i; for (i = 0; i < ASIZE; ++i) BmBC[i] = m; for (i = 0; i <= m - 1; ++i) BmBC[pat[i]] = m - i - 1; return;}

2 好後綴

在匹配失敗時，為了利用已經匹配的內容，可以嘗試從模式串中查找是否有子串與已匹配完成的內容一致。存在的話將模式串右移對齊，繼續從模式串最右開始匹配。

好後綴表的計算方法：

右移位數 = 好後綴出現的位置 – 好後綴在模式串中上一次出現的位置

要注意的是（摘自阮一峰的博客）：

1）"好後綴"的位置以最後一個字元為準。假定"ABCDEF"的"EF"是好後綴，則它的位置以"F"為準，即5（從0開始計算）。

2）如果"好後綴"在搜索詞中只出現一次，則它的上一次出現位置為 -1。比如，"EF"在"ABCDEF"之中只出現一次，則它的上一次出現位置為-1（即未出現）。

3）如果"好後綴"有多個，則除了最長的那個"好後綴"，其他"好後綴"的上一次出現位置必須在頭部。比如，假定"BABCDAB"的"好後綴"是"DAB"、"AB"、"B"，請問這時"好後綴"的上一次出現位置是什麼？回答是，此時採用的好後綴是"B"，它的上一次出現位置是頭部，即第0位。這個規則也可以這樣表達：如果最長的那個"好後綴"只出現一次，則可以把搜索詞改寫成如下形式進行位置計算"(DA)BABCDAB"，即虛擬加入最前面的"DA"。

計算好後綴表需要先計算後綴數組：

void suffixes(char *pat, int m, int *suff){ suff[m - 1] = m; for (i = m - 2；i >= 0；--i){ q = i; while (q >= 0 && pat[q] == pat[m - 1 - i + q]) --q; suff[i] = i - q; }}

有了後綴數組後，就可以藉助後綴數組來計算好後綴表了。

void preBmGS(char *pat, int m, int BmGS[]) { int i, j, suff[XSIZE]; suffixes(pat, m, suff); //沒有子串或前綴與好後綴一致 for (i = 0; i < m; ++i) BmGS[i] = m; j = 0; //有前綴與好後綴一致 for (i = m - 1; i >= 0; --i) if (suff[i] == i + 1) for (; j < m - 1 - i; ++j) if (BmGS[j] == m) BmGS[j] = m - 1 - i; //有子串與好後綴一致 for (i = 0; i <= m - 2; ++i) BmGS[m - 1 - suff[i]] = m - 1 - i;}

3 搜索過程

對於模式串EXAMPLE，從模式串尾部開始匹配，如果發現在字元P處發現不匹配，目標串中與P對齊的是字母X，則稱X為壞字元，已匹配完成的部分叫好後綴。在遇到不匹配的情況下，從壞字元表和好後綴表中找出較大的值進行右移。進行下一輪的匹配。

void BmPoc(char *pat, int m, char *s, int n){ int j, i, BmGS[XSIZE], BmBC[ASIZE]; /* Preprocessing */ preBmGs(pat, m, BmGS); preBmBc(pat, m, BmBC); /* Searching */ i = 0; while (i <= n - m) { for (j = m - 1; j >= 0 && pat[j] == s[j + i]; --j); if (j < 0) { OUTPUT(i); i += BmGS[0]; } else i += MAX(BmGS[j], BmBC[s[j + i]] - m + 1 + j); }}

4 BMH演算法

BMH（Boyer-Moore-Horspool）演算法是對BM演算法的改進演算法。經統計分析，在字元串搜索過程中，遇到壞字元的概率要遠遠大於好後綴的情況，所以在實際使用時，只使用壞字元表也有很好的效率。

代碼如下：

int bmhProc(char *s, int n, char *pat, int m){ int i = 0; //計算壞字元表 preBmBC(); while (i <= n - m) { // 從模式串尾部開始匹配 if (s[i + m - 1] == pat[m - 1] && 0 == strcmp(s+i, pat)) { // 匹配成功 return i; } i = i + BmBC[s[i + m - 1]]; } return -1;}

推薦閱讀：