【重学数据结构与算法(JS)】字符串匹配算法(三)——BM算法
文章的一开头，还是要强调下字符串匹配的思路：
将模式串和主串进行比较从前往后比较从后往前比较匹配时，比较主串和模式串的下一个位置失配时,在模式串中寻找一个合适的位置如果找到，从这个位置开始与主串当前失配位置进行比较如果未找到，从模式串的头部与主串失配位置的下一个位置进行比较在主串中找到一个合适的位置，重新与模式串进行比较前面的 BF 和 KMP 算法，都是属于规规矩矩从前向后的操作，后者仅在寻找模式串的合适位置上进行了优化，而 BM 算法的操作就显得骚了很多，它的优化点在于：
主串中合适的位置算法介绍与分析关于算法的介绍和分析，网上有很多解释，这里推荐一下阮一峰的字符串匹配的Boyer-Moore算法，很清楚的讲解了整个优化的思路，可以先看完理解了再往下看，因为下面主要介绍一下坏字符规则和好后缀规则需要的数据结构的手工求法以及代码实现。
运用坏字符规则，在算法里主要体现在生成一张散列表，表的key值是字符集里每个字符的ASCII码值，value值是模式串中该字符的位置，举个栗子：
QQ20200119-202854.png假设字符串的字符集不是很大，用长度为256的数组来存储，并且初值赋值为-1。数组的下标对应字符的 ASCII 码值，数组中存储这个字符在模式串中出现的位置。这里要特别说明一点，如果坏字符在模式串里多处出现，选择最靠后的那个，因为这样不会让模式串滑动过多，导致本来可能匹配的情况被滑动略过。
好后缀规则体现在如何求出 suffix 和 prefix 两个数组以及移动规则。
key值表示的是后缀子串的长度，value值表示的是在模式串中跟好后缀 S 相匹配的最后一个子串 S' 的首字母在模式串中的key值，如下图：
同样的，key值表示的是后缀子串的长度，而value值表示的是模式串中，是否有和该长度下后缀子串相同的前缀子串，是的话为 true，否则为 false，如下图：
移动规则总结如下：
在模式串中寻找跟好后缀 S 相匹配的最后一个子串 S'如果找到，将模式串移动到使得 S' 和主串对齐的位置如果找不到，再寻找模式串的前缀子串中是否有和 好后缀 S 的后缀子串匹配的位置，滑动模式串以对齐。如果仍然找不到，则将模式串移动至主串与模式串末尾对齐的下一个位置下图分别对应三种情况：
QQ20200119-215102.pngQQ20200119-220640.pngQQ20200119-221219.png代码实现整体逻辑框架参考字符串匹配的思路
仍然需要进行主串和模式串的字符对比，所以需要两个指针 i ，j 分别指向主串和模式串，记录位置需要一个循环来重复进行匹配操作，此时思考终止条件：i 指向主串每次匹配的合适位置，从前往后扫描；j 指向模式串的尾部，从后往前扫描。考虑极端情况：主串和模式串对比完，仍然无法匹配。此时，i 的位置一定小于等于 主串长度 n 与模式串长度 m 的差值。具体可看下图。每次模式串从后往前与主串进行匹配，这也需要一个内层循环来驱动指针j如果匹配，只需要继续移动匹配位置即可如果失配，分别根据坏字符规则和好后缀规则计算出 i 需要移动的位置，选择两个值当中最大的，重新计算 i 的值，重复进行匹配。QQ20200120-202236.png根据以上分析可以写出整个的逻辑框架代码：
carbon.png框架写好后，接下来就是完善三个辅助函数即可
求坏字符散列表这个就没有什么可以多说的了，只要参考上面分析的，一步一步写出代即可：
carbon的副本.png求好后缀记录数组suffix 和 prefix拿下标从 0 到 i 的子串（i 可以是 0 到 m-2）与整个模式串，求公共后缀子串。如果公共后缀子串的长度是 k，那就记录 suffix[k]=j（j 表示公共后缀子串的起始下标）。如果 j 等于 0，也就是说，公共后缀子串也是模式串的前缀子串，就记录 prefix[k]=true。可以自己动下手，模拟下代码的运行，尤其注意中k值的运用，很巧妙。
根据上面此步的算法分析，也可以写出：
carbon的副本3.png总结总的来说，BM算法另辟蹊径，通过从后往前的匹配的思路，加上坏字符规则和好后缀规则来优化移动的步数，从而提高算法的匹配效率。
“字符串匹配算法”是“重学数据结构与算法”系列笔记：
字符串匹配算法(一)——BF算法字符串匹配算法(二)——KMP算法字符串匹配算法(三)——BM算法字符串匹配算法(四)——Sunday算法单模式串匹配算法中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数组对内存占用大，可以只使用好后缀规则，不使用坏字符规则。
下一篇：unibit-＂
发表评论