BM模式匹配算法原理

1、BM模式匹配算法原理（圖解） 修改瀏覽權限 | 刪除 首先，先簡單說明一下有關BM算法的一些基本概念。BM算法是一種精確字符串匹配算法（區(qū)別于模糊匹配）。BM算法采用從右向左比較 的方法，同時應用到了兩種啟發(fā)式規(guī)則，即壞字符規(guī)則 和好后綴規(guī)則 ，來決定向右跳躍的距離。BM算法的基本流程: 設文本串T，模式串為P。首先將T與P進行左對齊，然后進行從右向左比較 ，如下圖所示: 若是某趟比較不匹配時，BM算法就采用兩條啟發(fā)式規(guī)則，即壞字符規(guī)則 和好后綴規(guī)則 ，來計算模式串向右移動的距離，直到整個匹配過程的結束。 下面，來詳細介紹一下壞字符規(guī)則 和好后綴規(guī)則 。 首先，詮釋一下壞字符和好后綴的概念。

2、請看下圖： 圖中，第一個不匹配的字符（紅色部分）為壞字符，已匹配部分（綠色）為好后綴。 1）壞字符規(guī)則（Bad Character）： 在BM算法從右向左掃描的過程中，若發(fā)現(xiàn)某個字符x不匹配，則按如下兩種情況討論： i. 如果字符x在模式P中沒有出現(xiàn)，那么從字符x開始的m個文本顯然不可能與P匹配成功，直接全部跳過該區(qū)域即可。 ii. 如果x在模式P中出現(xiàn)，則以該字符進行對齊。 用數(shù)學公式表示，設Skip(x)為P右移的距離，m為模式串P的長度，max(x)為字符x在P中最右位置。 例1： 下圖紅色部分，發(fā)生了一次不匹配。 計算移動距離Skip(c) = 5 - 3 = 2，則P向右移動2位。

3、移動后如下圖： 2）好后綴規(guī)則（Good Suffix）： 若發(fā)現(xiàn)某個字符不匹配的同時，已有部分字符匹配成功，則按如下兩種情況討論： i. 如果在P中位置t處已匹配部分P在P中的某位置t也出現(xiàn)，且位置t的前一個字符與位置t的前一個字符不相同，則將P右移使t對應t方才的所在的位置。 ii. 如果在P中任何位置已匹配部分P都沒有再出現(xiàn)，則找到與P的后綴P相同的P的最長前綴x，向右移動P，使x對應方才P后綴所在的位置。 用數(shù)學公式表示，設Shift(j)為P右移的距離，m為模式串P的長度，j 為當前所匹配的字符位置，s為t與t的距離（以上情況i）或者x與P的距離（以上情況ii）。 以上過程有點抽象，

4、所以我們繼續(xù)圖解。例2： 下圖中，已匹配部分cab（綠色）在P中再沒出現(xiàn)。 再看下圖，其后綴T（藍色）與P中前綴P（紅色）匹配，則將P移動到T的位置。 移動后如下圖： 自此，兩個規(guī)則講解完畢。 在BM算法匹配的過程中，取SKip(x)與Shift(j)中的較大者作為跳躍的距離。 BM算法預處理時間復雜度為O（m+s），空間復雜度為O(s)，s是與P, T相關的有限字符集長度，搜索階段時間復雜度為O(mn)。最好情況下的時間復雜度為O(n/m)，最壞情況下時間復雜度為O(mn)。(二)所謂精確字符串匹配問題，是在文本 T 中找到所有與查詢P 精確匹配的子串。而 BM 算法可以非常有效地解決這個問

5、題，讓時間復雜度降到低于線形的水平。 BM 算法主要用了三種巧妙而有效的方法，即從右到左掃描，壞字符規(guī)則和好后綴規(guī)則。 從右到左掃描的意思是從最后一個字符開始向前匹配，而不是習慣上的從開頭向后匹配。 壞字符規(guī)則是，從右到左的掃描過程中，發(fā)現(xiàn) Ti 與 Pj 不同，如果P 中存在一個字符 Pk 與 Ti 相同，且 ki 那么就將直接將 P 向右移使 Pk 與 Ti 對齊，然后再從右到左進行匹配。如果 P 中不存在任何與 Ti 相同的字符，則直接將 P 的第一個字符與 Ti 的下一個字符對齊，再從右到左進行比較。 如圖： T： a b c b a d f t a t e P： c b a x a

6、d P： c b a x a d 用 R(x) 表示字符 x 在 P 中出現(xiàn)的最右位置，此例中 R(b)=2。 可以看出使用從右到左掃描和壞字符規(guī)則可以跳過 T 中的很多位置不去檢查，從而使時間復雜度低于線性。 好后綴規(guī)則是，從右到左的掃描過程中，發(fā)現(xiàn) Ti 與 Pj 不同，檢查一下相同的部分t 是否在 P 中的其他位置 t 出現(xiàn)，a) 如果 t 與 t 的前一個字母不相同，就將 P 向右移，使t 與 T 中的 t 對齊。b) 如果t 沒有出現(xiàn)，則找到與t 的后綴相同的 P 的最長前綴 x，向右移動P ，使x 與 T 中t 的后綴相對應。 如圖a)：N： 1N： 1 2 3 4 5 6 7 8

7、 9 0 1 2 3 4 5 6 7 8 T： a b c b a d f tbcf a q v t b c e. P： c b c a b c e a b c P：c bc a b c e a b c f 可見，并不是將 P 向右移讓 P5 與 T9 對齊，而是讓 P2 與 T9 對齊，因為 P1 與 P8 不相同。用 L(i) 表示 t 的最大位置，此例中， L(9)= 3。 如圖b)：N： 1N： 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 T： a b c b a d f tbcf a q v t b c e. P：bc c a b c et b c P：

8、bc c a b c et b c 可見，當 P 向左找不到 “tbc”時，就找到 “tbc”的最長與 P 的前綴匹配的后綴，并將 P 向右移。用l(i) 表示這個最長后綴的長度，這個例子中 i=8。 整個算法是這樣的：預處理 輸入查詢字符串 P， 計算 P 中每個位置的 L(i) 和 l(i)，并計算 R(i)。查詢 k:=n; / n 是 T 中字符的總數(shù) while k0 and P(i)=T(i) do begin i:=i-1; h:=h-1; end; if i=0 then begin 輸出 T 的這個位置上的字符串； k:= k+n-l(2);end else 移動 P(增加

9、k)，k 取 好后綴規(guī)則和壞字符規(guī)則決定的最大值 end; 預處理階段可以根據(jù)上一篇文章提到的 Zbox 方法進行處理，時間復雜度為線性。 整個算法的時間復雜度最壞的情況是 O(m)，m 是 T 的長度。(三)BM算法的基本思想是從右向左進行比較。開始時仍是P(Pattern)的最左邊與S(String)的最左邊對齊，但首先進行Pm與Tm的比較。當某趟比較中出現(xiàn)不匹配時，BM算法采用兩條啟發(fā)性規(guī)則計算模式串右移的距離，即壞字符規(guī)則和好后綴規(guī)則。 1) 壞字符規(guī)則（Bad Character） P中的某個字符與T中的某個字符不相同時使用壞字符規(guī)則右移模式串P， P右移的距離可以通過delta1函

10、數(shù)計算出來。delta1函數(shù)的定義如下: delta1(x) = - m; xPj (1 = j = m)，即x在P中未出現(xiàn) | - m - maxk|Pk = x, 1 = k s)在匹配過程中，取delta1和delta2中的大者。BM算法的最壞時間復雜度為O(m*n)，但實際比較次數(shù)只有文本串長度的20%30%。*BM字符串匹配算法從snort2.2的mstring.c中整理而來*#include #include * 生成skip數(shù)組，即delta1數(shù)組*int *make_skip(char *ptrn, int plen)int *skip = (int *)malloc(256

11、* sizeof(int);int *sptr = skip + 256;if (skip = NULL) fprintf(stderr, malloc failed!);while (sptr- != skip) *sptr = plen + 1;while (plen != 0) skip(unsigned char)*ptrn+ = plen-;return skip;* 生成shift數(shù)組，即delta2數(shù)組*int *make_shift(char *ptrn, int plen)int *shift = (int *)malloc(plen * sizeof(int);int *s

12、ptr = shift + plen - 1;char *pptr = ptrn + plen - 1;char c;if (shift = NULL) fprintf(stderr, malloc failed!);c = ptrnplen - 1;*sptr = 1;while (sptr - != shift) char *p1 = ptrn + plen - 2, *p2, *p3; do while (p1 = ptrn & *p1- != c); p2 = ptrn + plen - 2; p3 = p1; while (p3 = ptrn & *p3- = *p2- & p2 =

13、pptr); while (p3 = ptrn & p2 = pptr); *sptr = shift + plen - sptr + p2 - p3; pptr-;return shift;* 搜索函數(shù)*int mSearch(char *buf, int blen, char *ptrn, int plen, int *skip, int *shift)int b_idx = plen;if (plen = 0) return 1;while (b_idx = blen) int p_idx = plen, skip_stride, shift_stride; while (buf-b_idx = ptrn-p_idx) if (b_idx shift_stride) ? skip_stride : shift_stride;return 0;int main()char str100 = faecabcxxdefeabcxxxabcdwaw;char pattern10 = abcxxxabc;int *skip, *shift, i;skip = make_skip(pattern, strlen(pattern);shift = make_shift(pattern, strl