字符串匹配算法 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}第一次重合的部分，这个从直观上来说也是比较好理解的。
用个示意图标识：
说明，某个字符串 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 码值，数组的值为字符在模式串中的位置：
xi 映射数组
说明下：1）bc 数组就是我们通过遍历模式串得到的数组。2）模式串里面有 2 个 a，最终 bc[97] = 3 标识坏字符 a 在模式串中的位置应该为 3，这是因为坏字符在模式串中如果有多个匹配，只能用后面一个，这样步字小一点。97 即为 a 的 ascii 值。
代码比较简单，先不考虑好字符规则，只用坏字符规则，这里面存在着移动位置为负数的问题，写下 BM 算法的代码：
好后缀规则的要求：
在模式串中查找跟好后缀匹配的另一个子串，如果查找到按照规则走，查找不到。
在好后缀的子串中，查找最长的，能够跟模式串前缀子串匹配的后缀子串。
字符串的后缀子串，因为字符串结尾字符是固定的，只要存储长度就可以推出后缀子串，如下图：
字符串后缀子串
后缀子串 b 值为 1，标识后缀子串，长度为 1，我们就知道从后向前一个字节，依次类推。
现在我们引入关键的变量数组 suffix 数组，下标 k 标志后缀子串的长度，值为在模式串中除了好后缀子串在模式串中的匹配之前的匹配的后缀子串的位置：
后缀子串数组
同样为了避免模式串滑动过头，如果模式串中有多个子串跟后缀子串{u}匹配，那么 suffix 数组存的是模式串中最靠后的子串起始位置。
这样还不够，查找跟好后缀匹配的另一个子串，还要在好后缀的后缀子串中，查找最长的能够跟模式串的前缀子串匹配的后缀子串。所以我们需要另一个 boolean 的 prefix 数组，来记录模式串（也是好后缀的）的后缀子串是否能够匹配模式串的前缀子串。
后缀子串和前缀子串是否匹配
说明：
图中后缀子串 b，和模式字符串的前缀子串不匹配，因为匹配的话第一字符必须是 c。
图中只有 cab 这个后缀子串才和模式串的前缀子串相互匹配。
其他的类似。
suffix 和 prefix 数组的计算过程如下：
真实环境中，我们如何根据好后缀和坏字符的规则移动那。假设好后缀的长度是 k。我们先拿到好后缀，在 suffix 数组中查找其匹配的子串，如果 suffix[k]不等于-1 ，我们就将模式串向后移动 j-suffix[k] +1 位（j 标识坏字符串对应的模式串中字符的下标）。
滑动规则 1
如果 suffix[k] = -1 ,标识模式串中不存在另一个跟好后缀子串片段，可以用下面规则来处理：好后缀的后缀子串 b[r,m-1]（其中，r 取值从 j+2 到 m-1）的长度 k = m-r，如果 prefix[k]= true，标识长度为 k 的后缀子串，有可以匹配的前缀子串，我们可以把模式串后移 r 位。
规则 2
如果两条规则都没有找到可以匹配的好后缀及其后缀子串的匹配的前缀子串，将整个模式串后移 m 位：
滑动三
最终 java 版本的完整代码：
代码实例
三、性能分析
BM 算法，还需要额外的三个数组，其中 bc 数组的大小和字符集有关系，suffix 数组和 prefix 数组大小和模式串大小 m 有关，如果我们要处理字符集很大，则 bc 数组对内存占用大，可以只使用好后缀规则，不使用坏字符规则。
还未添加个人签名 2021-11-23 加入
还未添加个人简介
评论