單模式串匹配算法中BM（Boyer-Moore）算法算是很難理解的算法了，不過(guò)性能高效，據(jù)說(shuō)比KMP算法性能提升3到4倍，suricata里面的單模式匹配就是用這種算法，所以有必要學(xué)習(xí)下，再把suricata的這部分代碼過(guò)一下還是不錯(cuò)的。

一、BM算法原理

BM算法是1975年發(fā)明的,它是一種后匹配算法，我們普通的字符串匹配算法是從左向右的，BM算法是從右向做的，即先判斷模式串最后一個(gè)字符是否匹配，最后判斷模式串第一個(gè)字符是否匹配。

原來(lái)我們?cè)贐F算法中，如果模式串和主串不匹配，則將主串或模式串后移一位繼續(xù)匹配，BM算法根據(jù)模式串的特定規(guī)律，將后移一位的步子邁的更大一些，后移幾位。 來(lái)看個(gè)圖簡(jiǎn)單說(shuō)明下，圖來(lái)自《數(shù)據(jù)結(jié)構(gòu)與算法之美》課程：

但是如果我們仔細(xì)觀察，c字符在abd中不存在，那么abd可以直接移動(dòng)到主串中c字符的后面再繼續(xù)匹配：

這樣移動(dòng)的步數(shù)變大了，匹配起來(lái)肯定更快了。

BM算法根據(jù)模式串的特定規(guī)律， 這里面的特定規(guī)律有兩種，一種是好后綴規(guī)則，一種是壞字符規(guī)則，初次看到這種規(guī)則的介紹后，心里嘀咕著這性能會(huì)好嗎，后面才發(fā)現(xiàn)經(jīng)典的BM算法做了不少優(yōu)化，所以性能高。 下面分別介紹下好后綴規(guī)則（good suffix shift）和壞字符規(guī)則（bad character rule）。

1.1 BM壞字符規(guī)則

首先在BM算法里面何謂好壞那，匹配上的，我們稱為好，匹配不上的叫壞。 按照剛才說(shuō)的，BM算法是倒著匹配字符串的，我們?cè)诘怪ヅ渥址倪^(guò)程中，當(dāng)我們發(fā)現(xiàn)某個(gè)字符沒(méi)法匹配的時(shí)候，我們把主串中這個(gè)沒(méi)法匹配的字符稱為壞字符。

我們發(fā)現(xiàn)在模式串中，字符c是不存在的，所以可以直接將模式字符串向后滑動(dòng)3位繼續(xù)匹配。

滑動(dòng)后，我們繼續(xù)匹配，發(fā)現(xiàn)主串中的字符a和模式串的d不匹配，這時(shí)候的情況和上一種不一樣，因?yàn)橹鞔械膲淖址鸻在模式串中存在，則后移動(dòng)2位，讓主串和模式串中的a對(duì)齊繼續(xù)匹配。 那么每次后移多少位那，我們假設(shè)把匹配不到的壞字符的位置記作si，如果壞字符在模式串中存在，則壞字符在模式串中的位置記作xi，那么模式串后移為si-xi；如果壞字符在模式串中不存在，xi就為-1。 上兩個(gè)圖中，第一個(gè)圖：si = 2，xi = -1 所以后移si-xi = 2+1 =3；第二個(gè)圖：si = 2，xi= 0所以后移的位置為si-xi=2。 說(shuō)明下如果壞字符在模式串中存在多個(gè)，那么應(yīng)該選擇最后一個(gè)匹配壞字符的位置作為xi，這樣xi移動(dòng)的步子就小，就不會(huì)遺漏應(yīng)該匹配的情況。

單純利用壞字符規(guī)則是有問(wèn)題的，因?yàn)閟i可以為0，xi可能大于0，這樣相減為負(fù)數(shù)，為此BM算法還增加了好后綴規(guī)則。

1.2 好后綴規(guī)則

模式串和主串匹配的部分叫做好后綴，如下圖：

如上圖，我們把匹配的部分bc 叫好后綴，記作{u}。我們拿它在模式串中查找，如果找到另一個(gè)跟{u}匹配的子串{u'},那么我們就將模式串滑動(dòng)到子串{u'}與主串中{u}對(duì)齊的位置。

如果在模式串中找不到好后綴，那么直接將模式串滑動(dòng)到主串中{u}后面，因?yàn)榍懊媸菦](méi)有好后綴的{u}的。

但是上面的后移的位數(shù)是錯(cuò)誤的，這里面有個(gè)規(guī)則，就是主串中{u}和模式串有重合，模式串移動(dòng)前綴與主串中{u}第一次重合的部分，這個(gè)從直觀上來(lái)說(shuō)也是比較好理解的。

好后綴規(guī)則3

用個(gè)示意圖標(biāo)識(shí)：

說(shuō)明，某個(gè)字符串s的后綴子串，就是最后一個(gè)字符和s對(duì)齊的子串，比如abc的后綴子串有c和bc。ab就不是，ab的最后一個(gè)字符不對(duì)齊；前綴子串，是開(kāi)頭字符跟s對(duì)齊的子串，比如字符串a(chǎn)bc的前綴子串有a和ab。我們需要從好后綴的后綴子串中，找一個(gè)最長(zhǎng)的且跟模式串的前綴子串匹配的，假設(shè)是{v},然后將模式串移動(dòng)到如圖位置：

。

總結(jié)下，好后綴有兩種移動(dòng)方法： 1）如果好后綴子串{u}在模式串中存在{u*}完全匹配，則移動(dòng)模式串，將最近的u*和主串對(duì)齊。 2）如果好后綴子串{u}在模式串中不存在，如果{u}的后綴子串有和模式串中的前綴子串匹配的{v‘} 則移動(dòng)模式串和主串中的相應(yīng)位置重合。 3）如果后綴子串{u}在模式串中不存在，且{u}的后綴子串在模式串中前綴子串沒(méi)有匹配的，則將模式串移動(dòng)到匹配的好后綴子串后面即可。

二、算法實(shí)現(xiàn)

通過(guò)原理我們知道壞字符規(guī)則和好后綴規(guī)則都涉及到查找問(wèn)題，如果查找性能不是很好，BM算法很難有好的性能，所以在工程實(shí)踐上，BM算法還是有不少技巧的。

我們?cè)谟?jì)算壞字符規(guī)則移動(dòng)的位數(shù)的時(shí)候，需要通過(guò)si-xi來(lái)計(jì)算，si一般可以直接得到，xi怎么計(jì)算，xi為壞字符在模式串中的位置，如果一個(gè)個(gè)比對(duì)，性能肯定跟不上，假設(shè)字符集不是很大，我們可以用一個(gè)256數(shù)組，來(lái)記錄每個(gè)字符在模式串中的位置，數(shù)組下標(biāo)可以直接對(duì)應(yīng)字符的ASCII碼值，數(shù)組的值為字符在模式串中的位置：

說(shuō)明下： 1）bc數(shù)組就是我們通過(guò)遍歷模式串得到的數(shù)組。 2）模式串里面有2個(gè)a，最終bc[97] = 3 標(biāo)識(shí)壞字符a在模式串中的位置應(yīng)該為3，這是因?yàn)閴淖址谀Ｊ酱腥绻卸鄠€(gè)匹配，只能用后面一個(gè)，這樣步字小一點(diǎn)。 97即為a的ascii值。

private static final int SIZE = 256; // 全局變量或成員變量

private void generateBC(char[] b, int m, int[] bc) {
  for (int i = 0; i < SIZE; ++i) {
    bc[i] = -1; // 初始化 bc
  }
  for (int i = 0; i < m; ++i) {
    int ascii = (int)b[i]; // 計(jì)算 b[i] 的 ASCII 值
    bc[ascii] = i;
  }
}

代碼比較簡(jiǎn)單，先不考慮好字符規(guī)則，只用壞字符規(guī)則，這里面存在著移動(dòng)位置為負(fù)數(shù)的問(wèn)題，寫下BM算法的代碼：

public int bm(char[] a, int n, char[] b, int m) {
  int[] bc = new int[SIZE]; // 記錄模式串中每個(gè)字符最后出現(xiàn)的位置
  generateBC(b, m, bc); // 構(gòu)建壞字符哈希表
  int i = 0; // i 表示主串與模式串對(duì)齊的第一個(gè)字符
  while (i <= n - m) {
    int j;
    for (j = m - 1; j >= 0; --j) { // 模式串從后往前匹配
      if (a[i+j] != b[j]) break; // 壞字符對(duì)應(yīng)模式串中的下標(biāo)是 j
    }
    if (j < 0) {
      return i; // 匹配成功，返回主串與模式串第一個(gè)匹配的字符的位置
    }
    // 這里等同于將模式串往后滑動(dòng) j-bc[(int)a[i+j]] 位
    i = i + (j - bc[(int)a[i+j]]); 
  }
  return -1;
}

好后綴規(guī)則的要求：

• 在模式串中查找跟好后綴匹配的另一個(gè)子串，如果查找到按照規(guī)則走，查找不到。
• 在好后綴的子串中，查找最長(zhǎng)的，能夠跟模式串前綴子串匹配的后綴子串。

字符串的后綴子串，因?yàn)樽址Y(jié)尾字符是固定的，只要存儲(chǔ)長(zhǎng)度就可以推出后綴子串， 如下圖：

后綴子串b 值為1，標(biāo)識(shí)后綴子串，長(zhǎng)度為1，我們就知道從后向前一個(gè)字節(jié)，依次類推。

現(xiàn)在我們引入關(guān)鍵的變量數(shù)組suffix數(shù)組，下標(biāo)k標(biāo)志后綴子串的長(zhǎng)度，值為在模式串中除了好后綴子串在模式串中的匹配之前的匹配的后綴子串的位置：

同樣為了避免模式串滑動(dòng)過(guò)頭，如果模式串中有多個(gè)子串跟后綴子串{u}匹配，那么suffix數(shù)組存的是模式串中最靠后的子串起始位置。

這樣還不夠，查找跟好后綴匹配的另一個(gè)子串，還要在好后綴的后綴子串中，查找最長(zhǎng)的能夠跟模式串的前綴子串匹配的后綴子串。所以我們需要另一個(gè)boolean的prefix數(shù)組，來(lái)記錄模式串（也是好后綴的）的后綴子串是否能夠匹配模式串的前綴子串。

說(shuō)明：

• 圖中后綴子串b，和模式字符串的前綴子串不匹配，因?yàn)槠ヅ涞脑挼谝蛔址仨毷莄。
• 圖中只有cab這個(gè)后綴子串才和模式串的前綴子串相互匹配。
• 其他的類似。 suffix 和prefix數(shù)組的計(jì)算過(guò)程如下：

// b 表示模式串，m 表示長(zhǎng)度，suffix，prefix 數(shù)組事先申請(qǐng)好了
private void generateGS(char[] b, int m, int[] suffix, boolean[] prefix) {
  for (int i = 0; i < m; ++i) { // 初始化
    suffix[i] = -1;
    prefix[i] = false;
  }
  for (int i = 0; i < m - 1; ++i) { // b[0, i]
    int j = i;
    int k = 0; // 公共后綴子串長(zhǎng)度
    while (j >= 0 && b[j] == b[m-1-k]) { // 與 b[0, m-1] 求公共后綴子串
      --j;
      ++k;
      suffix[k] = j+1; //j+1 表示公共后綴子串在 b[0, i] 中的起始下標(biāo)
    }
    i
    if (j == -1) prefix[k] = true; // 如果公共后綴子串也是模式串的前綴子串
  }
}

真實(shí)環(huán)境中，我們?nèi)绾胃鶕?jù)好后綴和壞字符的規(guī)則移動(dòng)那。假設(shè)好后綴的長(zhǎng)度是k。我們先拿到好后綴，在suffix數(shù)組中查找其匹配的子串，如果suffix[k]不等于-1 ，我們就將模式串向后移動(dòng)j-suffix[k] +1 位（j標(biāo)識(shí)壞字符串對(duì)應(yīng)的模式串中字符的下標(biāo)）。

如果suffix[k] = -1 ,標(biāo)識(shí)模式串中不存在另一個(gè)跟好后綴子串片段，可以用下面規(guī)則來(lái)處理： 好后綴的后綴子串b[r,m-1]（其中，r取值從j+2到m-1）的長(zhǎng)度k = m-r，如果prefix[k]= true， 標(biāo)識(shí)長(zhǎng)度為k的后綴子串，有可以匹配的前綴子串，我們可以把模式串后移r位。

如果兩條規(guī)則都沒(méi)有找到可以匹配的好后綴及其后綴子串的匹配的前綴子串，將整個(gè)模式串后移m位：

最終JAVA版本的完整代碼：

// a,b 表示主串和模式串；n，m 表示主串和模式串的長(zhǎng)度。
public int bm(char[] a, int n, char[] b, int m) {
  int[] bc = new int[SIZE]; // 記錄模式串中每個(gè)字符最后出現(xiàn)的位置
  generateBC(b, m, bc); // 構(gòu)建壞字符哈希表
  int[] suffix = new int[m];
  boolean[] prefix = new boolean[m];
  generateGS(b, m, suffix, prefix);
  int i = 0; // j 表示主串與模式串匹配的第一個(gè)字符
  while (i <= n - m) {
    int j;
    for (j = m - 1; j >= 0; --j) { // 模式串從后往前匹配
      if (a[i+j] != b[j]) break; // 壞字符對(duì)應(yīng)模式串中的下標(biāo)是 j
    }
    if (j < 0) {
      return i; // 匹配成功，返回主串與模式串第一個(gè)匹配的字符的位置
    }
    int x = j - bc[(int)a[i+j]];
    int y = 0;
    if (j < m-1) { // 如果有好后綴的話
      y = moveByGS(j, m, suffix, prefix);
    }
    i = i + Math.max(x, y);
  }
  return -1;
}

// j 表示壞字符對(duì)應(yīng)的模式串中的字符下標(biāo) ; m 表示模式串長(zhǎng)度
private int moveByGS(int j, int m, int[] suffix, boolean[] prefix) {
  int k = m - 1 - j; // 好后綴長(zhǎng)度
  if (suffix[k] != -1) return j - suffix[k] +1;
  for (int r = j+2; r <= m-1; ++r) {
    if (prefix[m-r] == true) {
      return r;
    }
  }
  return m;
}

代碼實(shí)例

void preBmBc(char *x, int m, int bmBc[]) {
   int i;
 
   for (i = 0; i < ASIZE; ++i)
      bmBc[i] = m;
   for (i = 0; i < m - 1; ++i)
      bmBc[x[i]] = m - i - 1;
}
 
 
void suffixes(char *x, int m, int *suff) {
   int f, g, i;
 
   suff[m - 1] = m;
   g = m - 1;
   for (i = m - 2; i >= 0; --i) {
      if (i > g && suff[i + m - 1 - f] < i - g)
         suff[i] = suff[i + m - 1 - f];
      else {
         if (i < g)
            g = i;
         f = i;
         while (g >= 0 && x[g] == x[g + m - 1 - f])
            --g;
         suff[i] = f - g;
      }
   }
}
 
void preBmGs(char *x, int m, int bmGs[]) {
   int i, j, suff[XSIZE];
 
   suffixes(x, m, suff);
 
   for (i = 0; i < m; ++i)
      bmGs[i] = m;
   j = 0;
   for (i = m - 1; i >= 0; --i)
      if (suff[i] == i + 1)
         for (; j < m - 1 - i; ++j)
            if (bmGs[j] == m)
               bmGs[j] = m - 1 - i;
   for (i = 0; i <= m - 2; ++i)
      bmGs[m - 1 - suff[i]] = m - 1 - i;
}
 
 
void BM(char *x, int m, char *y, int n) {
   int i, j, bmGs[XSIZE], bmBc[ASIZE];
 
   /* Preprocessing */
   preBmGs(x, m, bmGs);
   preBmBc(x, m, bmBc);
 
   /* Searching */
   j = 0;
   while (j <= n - m) {
      for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i);
      if (i < 0) {
         OUTPUT(j);
         j += bmGs[0];
      }
      else
         j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
   }
}

三、性能分析

BM算法，還需要額外的三個(gè)數(shù)組，其中bc數(shù)組的大小和字符集有關(guān)系，suffix數(shù)組和prefix數(shù)組大小和模式串大小m有關(guān)，如果我們要處理字符集很大，則bc數(shù)組對(duì)內(nèi)存占用大，可以只使用好后綴規(guī)則，不使用壞字符規(guī)則。