那些经典算法：字符串匹配算法BM算法

单模式串匹配算法中BM（Boyer-Moore）算法算是很难理解的算法了，不过性能高效，据说比KMP算法性能提升3到4倍，suricata里面的单模式匹配就是用这种算法，所以有必要学习下，再把suricata的这部分代码过一下还是不错的。

一、BM算法原理

BM算法是1975年发明的,它是一种后匹配算法，我们普通的字符串匹配算法是从左向右的，BM算法是从右向做的，即先判断模式串最后一个字符是否匹配，最后判断模式串第一个字符是否匹配。

原来我们在BF算法中，如果模式串和主串不匹配，则将主串或模式串后移一位继续匹配，BM算法根据模式串的特定规律，将后移一位的步子迈的更大一些，后移几位。 来看个图简单说明下，图来自《数据结构与算法之美》课程：

但是如果我们仔细观察，c字符在abd中不存在，那么abd可以直接移动到主串中c字符的后面再继续匹配：

这样移动的步数变大了，匹配起来肯定更快了。

BM算法根据模式串的特定规律， 这里面的特定规律有两种，一种是好后缀规则，一种是坏字符规则，初次看到这种规则的介绍后，心里嘀咕着这性能会好吗，后面才发现经典的BM算法做了不少优化，所以性能高。 下面分别介绍下好后缀规则（good suffix shift）和坏字符规则（bad character rule）。

1.1 BM坏字符规则

首先在BM算法里面何谓好坏那，匹配上的，我们称为好，匹配不上的叫坏。 按照刚才说的，BM算法是倒着匹配字符串的，我们在倒着匹配字符串的过程中，当我们发现某个字符没法匹配的时候，我们把主串中这个没法匹配的字符称为坏字符。

我们发现在模式串中，字符c是不存在的，所以可以直接将模式字符串向后滑动3位继续匹配。

滑动后，我们继续匹配，发现主串中的字符a和模式串的d不匹配，这时候的情况和上一种不一样，因为主串中的坏字符a在模式串中存在，则后移动2位，让主串和模式串中的a对齐继续匹配。 那么每次后移多少位那，我们假设把匹配不到的坏字符的位置记作si，如果坏字符在模式串中存在，则坏字符在模式串中的位置记作xi，那么模式串后移为si-xi；如果坏字符在模式串中不存在，xi就为-1。 上两个图中，第一个图：si = 2，xi = -1 所以后移si-xi = 2+1 =3；第二个图：si = 2，xi= 0所以后移的位置为si-xi=2。 说明下如果坏字符在模式串中存在多个，那么应该选择最后一个匹配坏字符的位置作为xi，这样xi移动的步子就小，就不会遗漏应该匹配的情况。

单纯利用坏字符规则是有问题的，因为si可以为0，xi可能大于0，这样相减为负数，为此BM算法还增加了好后缀规则。

1.2 好后缀规则

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

如上图，我们把匹配的部分bc 叫好后缀，记作{u}。我们拿它在模式串中查找，如果找到另一个跟{u}匹配的子串{u'},那么我们就将模式串滑动到子串{u'}与主串中{u}对齐的位置。

如果在模式串中找不到好后缀，那么直接将模式串滑动到主串中{u}后面，因为前面是没有好后缀的{u}的。

但是上面的后移的位数是错误的，这里面有个规则，就是主串中{u}和模式串有重合，模式串移动前缀与主串中{u}第一次重合的部分，这个从直观上来说也是比较好理解的。

好后缀规则3

用个示意图标识：

说明，某个字符串s的后缀子串，就是最后一个字符和s对齐的子串，比如abc的后缀子串有c和bc。ab就不是，ab的最后一个字符不对齐；前缀子串，是开头字符跟s对齐的子串，比如字符串abc的前缀子串有a和ab。我们需要从好后缀的后缀子串中，找一个最长的且跟模式串的前缀子串匹配的，假设是{v},然后将模式串移动到如图位置：

。

总结下，好后缀有两种移动方法： 1）如果好后缀子串{u}在模式串中存在{u*}完全匹配，则移动模式串，将最近的u*和主串对齐。 2）如果好后缀子串{u}在模式串中不存在，如果{u}的后缀子串有和模式串中的前缀子串匹配的{v'} 则移动模式串和主串中的相应位置重合。 3）如果后缀子串{u}在模式串中不存在，且{u}的后缀子串在模式串中前缀子串没有匹配的，则将模式串移动到匹配的好后缀子串后面即可。

二、算法实现

通过原理我们知道坏字符规则和好后缀规则都涉及到查找问题，如果查找性能不是很好，BM算法很难有好的性能，所以在工程实践上，BM算法还是有不少技巧的。

我们在计算坏字符规则移动的位数的时候，需要通过si-xi来计算，si一般可以直接得到，xi怎么计算，xi为坏字符在模式串中的位置，如果一个个比对，性能肯定跟不上，假设字符集不是很大，我们可以用一个256数组，来记录每个字符在模式串中的位置，数组下标可以直接对应字符的ASCII码值，数组的值为字符在模式串中的位置：

说明下： 1）bc数组就是我们通过遍历模式串得到的数组。 2）模式串里面有2个a，最终bc[97] = 3 标识坏字符a在模式串中的位置应该为3，这是因为坏字符在模式串中如果有多个匹配，只能用后面一个，这样步字小一点。 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]; // 计算 b[i] 的 ASCII 值 bc[ascii] = i; }}

代码比较简单，先不考虑好字符规则，只用坏字符规则，这里面存在着移动位置为负数的问题，写下BM算法的代码：

public int bm(char[] a, int n, char[] b, int m) {  int[] bc = new int[SIZE]; // 记录模式串中每个字符最后出现的位置  generateBC(b, m, bc); // 构建坏字符哈希表  int i = 0; // i 表示主串与模式串对齐的第一个字符  while (i <= n - m) {    int j;    for (j = m - 1; j >= 0; --j) { // 模式串从后往前匹配      if (a[i+j] != b[j]) break; // 坏字符对应模式串中的下标是 j    }    if (j < 0) {      return i; // 匹配成功，返回主串与模式串第一个匹配的字符的位置    }    // 这里等同于将模式串往后滑动 j-bc[(int)a[i+j]] 位    i = i + (j - bc[(int)a[i+j]]);   }  return -1;}

好后缀规则的要求：

• 在模式串中查找跟好后缀匹配的另一个子串，如果查找到按照规则走，查找不到。
• 在好后缀的子串中，查找最长的，能够跟模式串前缀子串匹配的后缀子串。

字符串的后缀子串，因为字符串结尾字符是固定的，只要存储长度就可以推出后缀子串， 如下图：

后缀子串b 值为1，标识后缀子串，长度为1，我们就知道从后向前一个字节，依次类推。

现在我们引入关键的变量数组suffix数组，下标k标志后缀子串的长度，值为在模式串中除了好后缀子串在模式串中的匹配之前的匹配的后缀子串的位置：

同样为了避免模式串滑动过头，如果模式串中有多个子串跟后缀子串{u}匹配，那么suffix数组存的是模式串中最靠后的子串起始位置。

这样还不够，查找跟好后缀匹配的另一个子串，还要在好后缀的后缀子串中，查找最长的能够跟模式串的前缀子串匹配的后缀子串。所以我们需要另一个boolean的prefix数组，来记录模式串（也是好后缀的）的后缀子串是否能够匹配模式串的前缀子串。

说明：

• 图中后缀子串b，和模式字符串的前缀子串不匹配，因为匹配的话第一字符必须是c。
• 图中只有cab这个后缀子串才和模式串的前缀子串相互匹配。
• 其他的类似。 suffix 和prefix数组的计算过程如下：

// b 表示模式串，m 表示长度，suffix，prefix 数组事先申请好了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; // 公共后缀子串长度 while (j >= 0 && b[j] == b[m-1-k]) { // 与 b[0, m-1] 求公共后缀子串 --j; ++k; suffix[k] = j+1; //j+1 表示公共后缀子串在 b[0, i] 中的起始下标 } i if (j == -1) prefix[k] = true; // 如果公共后缀子串也是模式串的前缀子串 }}

真实环境中，我们如何根据好后缀和坏字符的规则移动那。假设好后缀的长度是k。我们先拿到好后缀，在suffix数组中查找其匹配的子串，如果suffix[k]不等于-1 ，我们就将模式串向后移动j-suffix[k] +1 位（j标识坏字符串对应的模式串中字符的下标）。

如果suffix[k] = -1 ,标识模式串中不存在另一个跟好后缀子串片段，可以用下面规则来处理： 好后缀的后缀子串b[r,m-1]（其中，r取值从j+2到m-1）的长度k = m-r，如果prefix[k]= true， 标识长度为k的后缀子串，有可以匹配的前缀子串，我们可以把模式串后移r位。

如果两条规则都没有找到可以匹配的好后缀及其后缀子串的匹配的前缀子串，将整个模式串后移m位：

最终java版本的完整代码：

// a,b 表示主串和模式串；n，m 表示主串和模式串的长度。public int bm(char[] a, int n, char[] b, int m) {  int[] bc = new int[SIZE]; // 记录模式串中每个字符最后出现的位置  generateBC(b, m, bc); // 构建坏字符哈希表  int[] suffix = new int[m];  boolean[] prefix = new boolean[m];  generateGS(b, m, suffix, prefix);  int i = 0; // j 表示主串与模式串匹配的第一个字符  while (i <= n - m) {    int j;    for (j = m - 1; j >= 0; --j) { // 模式串从后往前匹配      if (a[i+j] != b[j]) break; // 坏字符对应模式串中的下标是 j    }    if (j < 0) {      return i; // 匹配成功，返回主串与模式串第一个匹配的字符的位置    }    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 表示坏字符对应的模式串中的字符下标 ; m 表示模式串长度private int moveByGS(int j, int m, int[] suffix, boolean[] prefix) {  int k = m - 1 - j; // 好后缀长度  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;}

代码实例

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算法，还需要额外的三个数组，其中bc数组的大小和字符集有关系，suffix数组和prefix数组大小和模式串大小m有关，如果我们要处理字符集很大，则bc数组对内存占用大，可以只使用好后缀规则，不使用坏字符规则。