BM模式匹配算法原理

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

2、160; 下面，來詳細介紹一下壞字符規(guī)則 和好后綴規(guī)則 。     首先，詮釋一下壞字符和好后綴的概念。   請看下圖：     圖中，第一個不匹配的字符（紅色部分）為壞字符，已匹配部分（綠色）為好后綴。    1）壞字符規(guī)則（Bad Character）：          在BM算法從右向左掃描的過程中，若發(fā)現某個字符x不匹配，則按如下兩種情況討論： &

3、#160;             i. 如果字符x在模式P中沒有出現，那么從字符x開始的m個文本顯然不可能與P匹配成功，直接全部跳過該區(qū)域即可。               ii. 如果x在模式P中出現，則以該字符進行對齊。         用數學公式表示，

4、設Skip(x)為P右移的距離，m為模式串P的長度，max(x)為字符x在P中最右位置。                     例1：          下圖紅色部分，發(fā)生了一次不匹配。           

5、          計算移動距離Skip(c) = 5 - 3 = 2，則P向右移動2位。        移動后如下圖：                       2）好后綴規(guī)則（Good Suffix）：  

6、0;       若發(fā)現某個字符不匹配的同時，已有部分字符匹配成功，則按如下兩種情況討論：              i. 如果在P中位置t處已匹配部分P'在P中的某位置t'也出現，且位置t'的前一個字符與位置t的前一個字符不相同，則將P右移使t'對應t方才的所在的位置。         

7、;     ii. 如果在P中任何位置已匹配部分P'都沒有再出現，則找到與P'的后綴P''相同的P的最長前綴x，向右移動P，使x對應方才P''后綴所在的位置。          用數學公式表示，設Shift(j)為P右移的距離，m為模式串P的長度，j 為當前所匹配的字符位置，s為t'與t的距離（以上情況i）或者x與P''的距離（以上情況ii）。     &

8、#160;            以上過程有點抽象，所以我們繼續(xù)圖解。         例2：           下圖中，已匹配部分cab（綠色）在P中再沒出現。            &

9、#160;     再看下圖，其后綴T'（藍色）與P中前綴P'（紅色）匹配，則將P'移動到T'的位置。                  移動后如下圖：                 &

10、#160;  自此，兩個規(guī)則講解完畢。     在BM算法匹配的過程中，取SKip(x)與Shift(j)中的較大者作為跳躍的距離。     BM算法預處理時間復雜度為O（m+s），空間復雜度為O(s)，s是與P, T相關的有限字符集長度，搜索階段時間復雜度為O(m·n)。最好情況下的時間復雜度為O(n/m)，最壞情況下時間復雜度為O(m·n)。(二)所謂精確字符串匹配問題，是在文本 T 中找到所有與查詢 P 精確匹配的子串。而 BM 算法可以非常有效地解決這個問題，讓時間復

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

12、60; 如圖：   T：     a b c b a d f t a t e   P：     c b a x a d   P：         c b a x a d      用 R(x) 表示字符 x 在 P 中出現的最右位置，此例中 R(b)=2。   可以看出使用從右到左掃描和壞字符規(guī)則可以跳過 T 中的很多

13、位置不去檢查，從而使時間復雜度低于線性。   好后綴規(guī)則是，從右到左的掃描過程中，發(fā)現 Ti 與 Pj 不同，檢查一下相同的部分 t 是否在 P 中的其他位置 t' 出現，a) 如果 t 與 t' 的前一個字母不相同，就將 P 向右移，使 t' 與 T 中的 t 對齊。b) 如果 t' 沒有出現，則找到與 t 的后綴相同的 P 的最長前綴 x，向右移動P ，使 x 與 T 中 t 的后綴相對應。   如圖a)：   N： &

14、#160;                    1                       N：    1 2 3 4 5 6 7 8 9 0

15、1 2 3 4 5 6 7 8        T：    a b c b a d f t b c f a q v t b c e.   P：    c b c a b c e a b c    P：                 

16、; c b c a b c e a b c f       可見，并不是將 P 向右移讓 P5 與 T9 對齊，而是讓 P2 與 T9 對齊，因為 P1 與 P8 不相同。用 L(i) 表示 t' 的最大位置，此例中， L(9)= 3。   如圖b)：   N：                  &#

17、160;   1                       N：    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 t b&#

18、160;c f a q v t b c e.   P：    b c c a b c e t b c    P：                    b c c a b c e t b c        &#

19、160;                   可見，當 P 向左找不到 “tbc”時，就找到 “tbc”的最長與 P 的前綴匹配的后綴，并將 P 向右移。用 l(i) 表示這個最長后綴的長度，這個例子中 i=8。    整個算法是這樣的：預處理   輸入查詢字符串 P，   計算 P 中每個位置的 L(i) 和 l(i)，并計算 R(i)。查詢 &

20、#160; k:=n; / n 是 T 中字符的總數   while k<=m do     begin     i :=n; / i 表示 P 中字符的位置     h :=k; / h 表示 T 中字符的位置     while i>0 and P(i)=T(i) do        begin   &

21、#160;      i:=i-1;          h:=h-1;       end;     if i=0 then       begin         輸出 T 的這個位置上的字符串；  

22、;       k:= k+n-l(2);       end     else        移動 P(增加 k)，k 取 好后綴規(guī)則和壞字符規(guī)則決定的最大值     end;             預處理

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

24、規(guī)則右移模式串P，     P右移的距離可以通過delta1函數計算出來。delta1函數的定義如下:      delta1(x) = - m; x<>Pj (1 <= j <= m)，即x在P中未出現                  |      &

25、#160;          - m - maxk|Pk = x, 1 <= k <= m; 其它情況  2) 好后綴規(guī)則(Good Suffix)     該規(guī)則將KMP算法和BM算法的思想結合起來，在不丟失真解的前提下確定一個新的移動距離delta2，     該函數與樣本P有關。     P中的某一子串Pj-s+1.m-s與已比較部分Pj+1.m相同，可讓P右

26、移s位。     delta2的定義如下：     delta2（j）= s|Pj+1.m=Pj-s+1.m-s)&&(PjPj-s)(j>s) 在匹配過程中，取delta1和delta2中的大者。 BM算法的最壞時間復雜度為O(m*n)， 但實際比較次數只有文本串長度的20%30%。* BM字符串匹配算法 從snort2.2的mstring.c中整理而來 *#include <stdio.h>#include <s

27、tring.h>*   生成skip數組，即delta1數組 *int *make_skip(char *ptrn, int plen)int *skip = (int *)malloc(256 * sizeof(int);int *sptr = skip + 256;if (skip = NULL)   fprintf(stderr, "malloc failed!");  while (sptr- != skip)   *sptr = plen + 1;  

28、;while (plen != 0)   skip(unsigned char)*ptrn+ = plen-;  return skip;*  生成shift數組，即delta2數組*int *make_shift(char *ptrn, int plen)int *shift = (int *)malloc(plen * sizeof(int);int *sptr = shift + plen - 1;char *pptr = ptrn + plen - 1;char c;if (shift = NULL)   fprin

29、tf(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;&

30、#160;   p3 = p1;       while (p3 >= ptrn && *p3- = *p2- && p2 >=pptr);   while (p3 >= ptrn && p2 >= pptr);     *sptr = shift + plen - sptr + p2 - p3;     pptr-;return shift;*   搜索函數 *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_