BM算法代碼深入剖析

BM（Boyer-Moore）算法：是一種高效的字元串比對算法，性能是相當之高，是KMP的幾倍之多。

術語

在123456abc789中找abc

主串：123456abc789為主串

模式串：abc為字串

BM算法思想

通過增加比對失敗後一次移動的字元數，減少無效的比對次數，進而增加比對效率。

如何在增加移動字元數

BM算法充分利用了模式串的不變特性，和在發生不比對時，已經比對了的字元串及已知的不比對字元串

a	b	c	a	c	a	b	c	b	c
a	b	c	b	c

圖1

這裡引入兩個概念

1、壞字元：圖1紅色字型a就是不比對的壞字元

2、好字尾：圖1的綠色字型bc就是好字尾

BM算法原理

壞字元規則

根據壞字元和模式串，BM算法是如何一次移動多位的，如何增加效率的

我們試着逐漸移動，将模式串向右移動一位

a	b	c	a	c	a	b	c	b	c
a	b	c	b	c

圖2

其他的我們先不考慮，我們分析我們已知的壞字元，與移位後的對應模式串上的b是不比對的，我們繼續右移一位

a	b	c	a	c	a	b	c	b	c
a	b	c	b	c

圖3

移位後主串上壞字元，與移位後的模式串對應位置的字元是比對的。

從上面分析我們可知，在比對出現壞字元時，我們需要右移，而模式串中與目前壞字元位置（即a）可比對的位置，可以自模式串右邊向左邊逐一比較擷取，這樣我們就一次移動到模式串與壞字元比對的位置了。

而逐一向前對比結果是增加了模式串向前移動的字元數，但是還是需要對比O(m)次，性能并沒有提高，而模式串内容是固定的，我們可以把模式串中每個字元在模式串中的位置通過hash表緩存起來，

hash算法：

哈希函數：我們可以直接取字元的ascii碼值

是以将字元的ascii碼值作為數組下标，對應的在模式串中的位置作為值，ascii是一個字元大小，是以申請255大小的數組bc，數組的初始化代碼如下：

private void generateBC() {
        //所有bc初始化為-1
        for (int i = 0; i < bc.length; i++) {
            bc[i] = -1;
        }

        for (int i = 0; i < b.length; i++) {
            // 将字串i處内容的ascii碼值作為緩存下标，其下标作為緩存的值
            int ascii = b[i];
            bc[ascii] = i;
        }
    }

如此上面就不要逐一比較了，直接使用bc[a]=0就能找到最近的比對位置。

BM算法代碼深入剖析

圖4

根據上面的圖壞字元=a，s=2，模式串中對應比對x=bc[a]=0，

向右移動字元數=S-X=2-0=2,

壞字元缺點：

BM算法代碼深入剖析

圖5

如果比對串如上圖，壞字元在模式串中的比對位置在右邊即X=bc[a]=3, 移動字元數=S-X=2-3=-1,

是以要配合好字尾一起使用

好字尾規則：

好字尾的規則比較複雜一些，但基本上和壞字元原理類似。

a	b	c	a	c	b	b	c	b	c
a	b	c	d	b	c

圖6

比對好的（綠色字型）bc是好字尾，記作{u}，拿bc到模式串中查找，如果找到另一個跟{u}比對的字串{u*}，我們就可以将模式串移動到{u*}的起始位置。

BM算法代碼深入剖析

圖7

如圖7：移動字元數=S-GS+1

我們再來看看圖6應該向右移動多少：3-1+1=3,移動後結果為

a	b	c	a	c	b	b	c	b	c
a	b	c	d	b	c

圖8

另一種情形，如果好的字尾在模式串中沒有找到另一個比對字元串，是否就可以直接将模式串滑動到{u}後面，我們來看看下面這種情形

a	b	c	a	c	b	c	d	b	c
c	d	b	c

圖9

上圖9，如果在模式串中沒有找到對應的，直接将模式串啟動到bc之後，将會錯過比對串。

a	b	c	a	c	b	c	d	b	c
c	d	b	c
c	d	b	c	移動到{u}之後
c	d	b	c	錯過的比對處

圖10

上圖就是出現滑動過度情形，是以處理好的字尾的時候，不僅要看完整的字尾，而且要看字尾的子字尾是否存在跟模式串的字首子串比對。

字尾子串及字尾字串字串是否存在比對字首字串的緩存表達：

好字尾與壞字元類似，也是使用了緩存數組，這裡suffix針對不同長度的字尾，在模式串中對應的比對索引，及是否存在比對的字首字串prefix。

c	d	b	c	d	b
字尾子串	長度	suffix	prefix
b	1	2	TRUE
db	2	1	FALSE
cdb	3	TRUE
bcdb	4	-1	FALSE
dbcdb	5	-1	FALSE

模式串字首緩存處理

public void generateGs() {
        // 所有suffix初始化位-1，所有prefix初始化為prefix
        for (int i = 0; i < b.length-1; i++) {
            suffix[i]=-1;
            prefix[i] = false;
        }

        int m = b.length;
        for (int i = 0; i < m-1; i++) {
            int j = i;
            int k = 0;
            //兩端從長度為1對比，每次符合條件重新整理suffix，如此，suffix比對會是最靠近右端
            while (j >= 0 && b[m-1-k] == b[j]) {
                j--;
                k++;
                suffix[k] = j+1;
            }
            if (j == -1) {
                prefix[k] = true;
            }
        }
    }

用cbdcbd這個模式串分析；

i = 0， j=0,k=0
1. b[m-1-k]==b[j] => b[5]==b[0] ? => c==d? 不等, j==-1? 不等，結束
i=1
1. j=1,k=0 b[m-k-1]==b[j] => b[5]==b[1] => d==b?不等，j==-1？不等，結束
i=2
1. j=2,k=0 b[m-k-1]==b[j] => b[5]==b[2] => d==d?等，suffix[1]=j=2
2. j=1,k=1 b[m-k-1]==b[j] => b[4]==b[1] => b==b?等， suffix[2]=j=1
3. j=0,k=2 b[m-k-1]==b[j] => b[3]==b[0] => c==c?等， suffix[3]=j=0
4. j=-1,k=3 => prefix[3]=true
i=3
1. j=3,k=0 => b[5]==b[3] => d==c>不等結束
i=4
1. j=4,k=0 => b[5]==b[4] => d==b,不等結束

從上面代碼分析可看出，該部分代碼是從位置0，逐漸與字尾比對，找到最靠右的與不同長度字尾相同的索引，且如果完全比對，則prefix為true

BM算法代碼實作

public int bm(String str) {
        char[] a = str.toCharArray();
        generateBC();
        generateGs();

        //print();
        int i = 0;
        int n = a.length;
        int m = b.length;
        while (i <= n - m) {
            // 計算壞字元
            int j;
            // 目前對比的是i位開始，與模式串從右自左的對比
            for (j = m-1; j>=0; j--) {
                if (a[i+j] != b[j]) {
                    break;
                }
            }

            // 如果全部比完說明完全比對
            if (j < 0) {
                return i;
            }
            
            int x = j - bc[a[i+j]];
            int y = 0;
            if (j < m-1) {
                y = moveByGS(j, m);
            }
            i += x > y ? x : y;
        }
        return -1;
    }

    /**
     * 計算好字尾
     * @param j
     * @param m
     * @return
     */
    private int moveByGS(int j, int m) {
        // 好字尾長度
        int k = m - j - 1;
        //模式串存在一個好字尾比對的子串，傳回其索引
        if (suffix[k]!=-1) {
            return j-suffix[k]+1;
        }
        
        //如果沒有找到，則看好字尾子字尾在模式串是否有字首字串比對
        //使用j+2的原因是因為j為壞字元，j+1是好字尾的起始位置，j+2是好字尾的第一個子字尾，子字尾的位置不超過m-1
        for (int r = j+2; r <= m-1; r++) {
            if (prefix[m-r]) {
                return r;
            }
        }

        return 0;
    }

使用下面資料模拟運作上面代碼

f	b	c	b	b	c	a	c	b	c	b
c	b	c	b

n=11,m=4

i=0

j=m-1=3,a[i+j]=b[j] => a[3]=b[3] =>b=b?繼續
j=2,a[2]==b[2] => a[2]=b[2]=> c=c?繼續
j=1,b==b繼續
j=0, f!=b
壞字元移動距離x=s-bc[f]=0-(-1)=1
好字尾moveByGS
1. k=m-j-1 => k = 4-0 -1 = 3
2. suffix[3] = -1
3. 子串中不存在與好字尾完全比對的子串{u*}
4. 繼續尋找好字尾的子字尾，模式串中是否存在字首與子字尾比對的
5. r=2， prefix[4-2]=prefix[2]=true，是以傳回2
i+=Max(壞字元右移，好字尾右移)=> MAX(-1, 2)=2,i=2

f	b	c	b	b	c	a	c	b	c	b
c	b	c	b

i=2

j=3,c!=b
壞字元移動距離x=j-bc[a[i+j]]=3-bc[a[5]]=3-bc[c]=3-0=3
j=m-1,不存在好字尾
i += MAX(壞字元右移，好字尾右移）=MAX(3,0)=3, i=5

f	b	c	b	b	c	a	c	b	c	b
c	b	c	b

i=5

j=3, b==b,繼續
j=2, c==c
j=1, a!=b
x = j-bc[a[i+j]=>3-bc[a]=>1-(-1)=2
y=moveByGS,好字尾=cb
1. 好字尾長度=m-j-1=4-1-1=2
2. suffix[2]=0,移動字元數=j-suffix[2]+1=1-0+1=2
i+=MAX(2,2)=2=>i=7

f	b	c	b	b	c	a	c	b	c	b
c	b	c	b

i=7
1. 字元串完全比對

以上是BM算法代碼的單步分析，相信如果前面基本原理沒有太了解，通過代碼的逐漸分析也會對BM算法有着更深一層的了解。

BM算法我們分析的差不多了，從BM算法我們是否可以看出一些程式設計的思想

1、程式中存在大量量不是很大的重複資料查找，我們可是使用hash算法，使O(n)的時間複雜度一下就到了O(1),即熱門資料緩存，

2、合理範圍内資料可選擇好的散清單，減小查詢時間複雜度

BM算法就是充分分析出重複的資料操作，與合理利用已處理過的資訊

BM算法代碼深入剖析

BM算法思想

BM算法原理

模式串字首緩存處理

繼續閱讀

goalng nil interface淺析持續學習

模組化：數學模組化

開源軟體：NoSql資料庫 - 圖資料庫 Neo4j轉載自原文位址：http://www.cnblogs.com/loveis715/p/5277051.html

資料在網絡7層中的傳輸過程

當今世界十大經典算法

字元串功能實作

【算法提高班】貪婪政策

《貪婪的動态規劃》

分治法實作求解最大子數組

UVA 10154:Weights and Measures Weights and Measures

Linux Kernel Development　學習

動态規劃、最小費用流例題 — nyoj_712 探尋寶藏

計算機開路人阿蘭·圖靈

基礎算法之二分查找

poj3249

PAT 1089 Insert or Merge[難]