深度报文检测基础之BM算法

摘要

BM（Boyer-Moore）算法是单模式匹配的字符串搜索算法，相对经典的KMP字符串匹配算法，效率更好。在模式串长度大的时候效率更高。算法需要对模式串进行预处理，处理过后，在搜索过程中就可以最大减少字符比较次数，以此提高效率。BM算法主要三个特点：从模式串最右开始进行匹配；坏字符表；好后缀表。基本思路就是从右往左进行字符匹配，遇到不匹配的字符后从坏字符表和好后缀表找一个最大的右移值，将模式串右移继续匹配。

1 坏字符

右移位数 = 坏字符出现的位置 – 坏字符在模式串中上一次出现的位置

如果字符在模式串中没有出现，则认为上一次出现的位置为-1。-1意思是啥呢？就是右移之后模式串首部与坏字符出现的后一个字符对齐。

对于模式串EXAMPLE，计算字母P的右移位数 ： P的位置为5，上一次出现的位置是-1（没有出现），则右移位数为：5- （-1）= 6，对于模式串中最后出现的 。

i	1	2	3	4	5	6
Pat[i]	E	X	A	M	P	L	E	-pat[i]
BmBC[i]	1-> 6	2	3	4	5	6	6	7

代码如下：

1	void preBmBC(char *pat, int m, int BmBC[])
2	{
3	int i;
4	for (i = 0; i < ASIZE; ++i)
5	BmBC[i] = m;
6	for (i = 0; i <= m - 1; ++i)
7	BmBC[pat[i]] = m - i - 1;
8	return;
9	}

2 好后缀

在匹配失败时，为了利用已经匹配的内容，可以尝试从模式串中查找是否有子串与已匹配完成的内容一致。存在的话将模式串右移对齐，继续从模式串最右开始匹配。

好后缀表的计算方法：

右移位数 = 好后缀出现的位置 – 好后缀在模式串中上一次出现的位置

要注意得是（摘自阮一峰的博客）：

1）"好后缀"的位置以最后一个字符为准。假定"ABCDEF"的"EF"是好后缀，则它的位置以"F"为准，即5（从0开始计算）。

2）如果"好后缀"在搜索词中只出现一次，则它的上一次出现位置为 -1。比如，"EF"在"ABCDEF"之中只出现一次，则它的上一次出现位置为-1（即未出现）。

3）如果"好后缀"有多个，则除了最长的那个"好后缀"，其他"好后缀"的上一次出现位置必须在头部。比如，假定"BABCDAB"的"好后缀"是"DAB"、"AB"、"B"，请问这时"好后缀"的上一次出现位置是什么？回答是，此时采用的好后缀是"B"，它的上一次出现位置是头部，即第0位。这个规则也可以这样表达：如果最长的那个"好后缀"只出现一次，则可以把搜索词改写成如下形式进行位置计算"(DA)BABCDAB"，即虚拟加入最前面的"DA"。

计算好后缀表需要先计算后缀数组：

void suffixes(char *pat, int m, int *suff) {    suff[m - 1] = m;    for (i = m - 2；i >= 0；--i){       q = i;       while (q >= 0 && pat[q] == pat[m - 1 - i + q])          --q;       suff[i] = i - q;    } }

有了后缀数组后，就可以借助后缀数组来计算好后缀表了。

void preBmGS(char *pat, int m, int BmGS[]) {    int i, j, suff[XSIZE];    suffixes(pat, 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; }

i	1	2	3	4	5	6
Pat[i]	E	X	A	M	P	X	A
Suff[i]	2	7
BmGS[i]	7	7	7	7	4	7	1

3 搜索过程

对于模式串EXAMPLE，从模式串尾部开始匹配，如果发现在字符P处发现不匹配，目标串中与P对齐的是字母X，则称X为坏字符，已匹配完成的部分叫好后缀。在遇到不匹配的情况下，从坏字符表和好后缀表中找出较大的值进行右移。进行下一轮的匹配。

void BmPoc(char *pat, intm, char *s, intn) {    int j, i, BmGS[XSIZE], BmBC[ASIZE];    preBmGs(pat, m, BmGS);    preBmBc(pat, m, BmBC);    i = 0;    while (i <= n - m) {       for (j = m - 1; j >= 0 && pat[j] == s[j + i]; --j);       if (j < 0) {          OUTPUT(i);          i += BmGS[0];       }       else          i += MAX(BmGS[j], BmBC[s[j + i]] - m + 1 + j);    } }

4 BMH算法

BMH（Boyer-Moore-Horspool）算法是对BM算法的改进算法。经统计分析，在字符串搜索过程中，遇到坏字符的概率要远远大于好后缀的情况，所以在实际使用时，只使用坏字符表也有很好的效率。

代码如下：

int bmhProc(char *s, int n, char *pat, int m) {    int i = 0;    //计算坏字符表    preBmBC();    while (i <= n - m)    {       // 从模式串尾部开始匹配       if (s[i + m - 1] == pat[m - 1] && 0 == strcmp(s+i, pat))       {          // 匹配成功          return i;       }       i = i + BmBC[s[i + m - 1]];    }    return -1; }