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

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

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

4、設(shè)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ā)現(xiàn)某個字符不匹配的同時，已有部分字符匹配成功，則按如下兩種情況討論：              i. 如果在P中位置t處已匹配部分P'在P中的某位置t'也出現(xiàn)，且位置t'的前一個字符與位置t的前一個字符不相同，則將P右移使t'對應(yīng)t方才的所在的位置。         

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

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

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

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

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

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 中出現(xiàn)的最右位置，此例中 R(b)=2。   可以看出使用從右到左掃描和壞字符規(guī)則可以跳過 T 中的很多

13、位置不去檢查，從而使時間復(fù)雜度低于線性。   好后綴規(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 的后綴相對應(yīng)。   如圖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;                   可見，當(dāng) P 向左找不到 “tbc”時，就找到 “tbc”的最長與 P 的前綴匹配的后綴，并將 P 向右移。用 l(i) 表示這個最長后綴的長度，這個例子中 i=8。    整個算法是這樣的：預(yù)處理   輸入查詢字符串 P，   計算 P 中每個位置的 L(i) 和 l(i)，并計算 R(i)。查詢 &

20、#160; k:=n; / n 是 T 中字符的總數(shù)   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;             預(yù)處理

23、階段可以根據(jù)上一篇文章提到的 Zbox 方法進(jìn)行處理，時間復(fù)雜度為線性。      整個算法的時間復(fù)雜度最壞的情況是 O(m)，m 是 T 的長度。(三)#include <stdio.h>#include <string.h>*   生成skip數(shù)組，即delta1數(shù)組 *int *make_skip(char *ptrn, int plen)int *skip = (int *)malloc(256 * sizeof(int);int *sptr = skip + 256;if (ski

24、p = 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 *s

25、hift = (int *)malloc(plen * sizeof(int);int *sptr = 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;   

26、60; do       while (p1 >= ptrn && *p1- != c);       p2 = ptrn + plen - 2;    p3 = p1;       while (p3 >= ptrn && *p3- = *p2- && p2 >=pptr);   while (p3 >=

27、 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)