BM模式匹配算法原理

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

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

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

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

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

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

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

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

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

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

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

13、位置不去檢查，從而使時(shí)間復(fù)雜度低于線性。   好后綴規(guī)則是，從右到左的掃描過(guò)程中，發(fā)現(xiàn) Ti 與 Pj 不同，檢查一下相同的部分 t 是否在 P 中的其他位置 t' 出現(xiàn)，a) 如果 t 與 t' 的前一個(gè)字母不相同，就將 P 向右移，使 t' 與 T 中的 t 對(duì)齊。b) 如果 t' 沒(méi)有出現(xiàn)，則找到與 t 的后綴相同的 P 的最長(zhǎng)前綴 x，向右移動(dòng)P ，使 x 與 T 中 t 的后綴相對(duì)應(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       可見(jiàn)，并不是將 P 向右移讓 P5 與 T9 對(duì)齊，而是讓 P2 與 T9 對(duì)齊，因?yàn)?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;                   可見(jiàn)，當(dāng) P 向左找不到 “tbc”時(shí)，就找到 “tbc”的最長(zhǎng)與 P 的前綴匹配的后綴，并將 P 向右移。用 l(i) 表示這個(gè)最長(zhǎng)后綴的長(zhǎng)度，這個(gè)例子中 i=8。    整個(gè)算法是這樣的：預(yù)處理   輸入查詢字符串 P，   計(jì)算 P 中每個(gè)位置的 L(i) 和 l(i)，并計(jì)算 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 的這個(gè)位置上的字符串；  

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

23、階段可以根據(jù)上一篇文章提到的 Zbox 方法進(jìn)行處理，時(shí)間復(fù)雜度為線性。      整個(gè)算法的時(shí)間復(fù)雜度最壞的情況是 O(m)，m 是 T 的長(zhǎng)度。(三)#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)