BM算法总结
- 格式：doc
- 大小：49.00 KB
- 文档页数：3
BM算法（全称Boyer-Moore Algorithm）是一种精确字符串匹配算法（只是一个启发式的字符串搜索算法）。BM算法不同于KMP算法，采用从右向左比较的方法，同时引入了两种启发式Jump规则，即Bad-Character和Good-Suffix，来决定模板向右移动的步长。
BM算法的基本流程:
文本串T（待匹配的字符串，长度n），模式串为P（用于去匹配的字符串模板，长度设为m）。首先将T与P进行左对齐，然后进行从右向左比较（此时不移动模板和文本的相对位置，仅仅比较对齐位置上面是否相同，方向是右向左）。若是某趟比较不匹配时，BM算法就采用两条启发式规则，即前面提到的Bad-Character和Good-Suffix，来计算模式串P向右移动的步长，直到整个匹配过程的结束。
1）Bad-character
BM 算法在上图中从右向左匹配中第一个字符就出现不一致的情况，此时需要采
用两种情况来处理：
a) 如果T 中不匹配字符E 在模式P 中没有出现，那么我们很容易就能理解为E
开始的m 长度的字符串不可能匹配到P（直观，无需解释），我们可以直接
把P 跳过E，匹配后面的内容。
b) 如果E 在模式P 中未进行匹配的字段中出现了，则以该字符E 进行对齐。
BM算法实现
2）Good Suffix
若发现某个字符不匹配的同时，已有部分字符匹配成功，则按如下两种情况进行:
a) 如果在P中位置t处已经匹配部分P’在P中某位置t’也出现，且位置t’的前一个字符与位置t的前一个字符不相同，则将P右移使t’对应t所在的位置。
b) 如果P中任何位置已经匹配部分P’没有再出现，则找到与P’的后缀P’’相同的P的最长前缀x，向右移动P，使x对应刚才P’’后缀所在位置
下面两个链接解释的很好：
/sealyao/archive/2009/09/18/4568167.aspx
http://www-igm.univ-mlv.fr/~lecroq/string/node14.html#SECTION00140
void preBmBc(char *x, int m, int bmBc[]) //坏字符表预处理,x就是上文中的模式串P
{
int i; //注意：bmBc数组的下标是字符，而不是数字
for (i = 0; i < ASIZE; ++i) //初始将所有ASIZE＝256个字符都赋初值为模式串的长度m，
bmBc[i] = m; //也就是说模式串中没出现的字符，相应的移动距离都为m
for (i = 0; i < m - 1; ++i)
bmBc[x[i]] = m - i - 1;
}
Suffixes[]数组的计算方法。常规的方法如下：很裸很暴力。这种方法比下面那种容易理解。
void suffixes(char *P, int m, int *suff)｛
Suff[m-1]=m；
for（i=m-2；i>=0；--i）
{g=i；
while（g>=0&&P[g]==P[m-1-i+g]）
--g；
Suff[i]=i-g；
}
｝ Suffixes[]数组计算方法二
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;
}
}
}
例：
bmBc and bmGs tables used by Boyer-Moore algorithm
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;
图1
for (i = 0; i <= m - 2; ++i)
bmGs[m - 1 - suff[i]] = m - 1 - i;
}
图2
void BM(char *x, int m, char *y, int n) {
int i, j, bmGs[XSIZE], bmBc[ASIZE];//XSIZE为模式串的长度，ASIZE为字母表的长度256
/* 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];//匹配到一个相同的串后，向后移动m位，
//继续匹配文本串后续的串
}
else
j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
}
}
