内核中Boyer-Moore (BM)算法简单注释
一、shift生成
这个算法之前大致看过一下，在grep中再次遇到了该算法，大致想了下它的具体实现，发现shift数组的计算并没有像KMP中那样的迭代过程，之后就在网络上搜索了下这个算法的描述，主要是看shift的生成方法，具体思想描述有不少图片甚至视频展示，这里就不详细说明了。关于shift的生成有不少伪代码，加上文字注释，看起来相当费解，刚好想到内核中有关于该算法的一个实现，所以就看了这个算法在内核中的实现。
总体来说，它分两种情况，一种是自右向左匹配过程中，第一个字符就匹配失败，此时不能从pattern中获得任何有用的信息，只能根据输入字符串(Text不是pattern)的当前位置字符c，确定该字符在pattern中从右向左第一个出现的位置，和这个位置对齐即可，这种情况下的移位在内核中称为bad_shift；另一种是pattern中有一个或者一个以上的字符匹配成功，此时可以利用完整的pattern结构来计算出移位信息，这个移位值使用goo_shift表示。
二、代码注释
只是为了便于自己之后再翻阅，随手一个笔记：
static unsigned int bm_find(struct ts_config *conf, struct ts_state *state)
{
struct ts_bm *bm = ts_config_priv(conf);
unsigned int i, text_len, consumed = state->offset;
const u8 *text;
int shift = bm->patlen, bs;
for (;;) {//这一层循环是读入一个block的大小
text_len = conf->get_next_block(consumed, &text, conf, state);
if (unlikely(text_len == 0))
break;
while (shift < text_len) {
DEBUGP("Searching in position %d (%c)
",
shift, text[shift]);
for (i = 0; i < bm->patlen; i++) //从右向左匹配，其中i表示距离pattern最后端的距离
if (text[shift-i] != bm->pattern[bm->patlen-1-i])
goto next;
/* London calling... */
DEBUGP("found!
");
return consumed += (shift-(bm->patlen-1));
next: bs = bm->bad_shift[text[shift-i]];
/* Now jumping to... */在该操作中，shift向后移动，shift指向输入text中尝试和pattern结尾自右向左匹配的起始位置。
shift = max_t(int, shift-i+bs, shift+bm->good_shift[i]);
}
consumed += text_len;
}
return UINT_MAX;
}
static int subpattern(u8 *pattern, int i, int j, int g)
{
int x = i+g-1, y = j+g-1, ret = 0;
x表示i开始字符串的结尾位置，y表示j开始字符串结尾位置，从右向左开始比较两个字符串
while(pattern[x--] == pattern[y--]) {
if (y < 0) {如果y<0说明前面已经没有空间，直接返回成功。在该条件下返回，对应pattern:aabaa，(可以以输入文本:bcbaabaa)，入参i=2，j=-1，g=3，x=2，y=-1这种情况。
ret = 1;
break;
}
if (--g == 0) {//g==0表示说找到一个完整的相同匹配，此时需要进一步比较前一个字符是否相等，如果前一个字符相等，则不能作为候选移动项，原因比较明显，两者完全相等，第一个后缀没有匹配成功，第二个由于和第一个完全相等，也不可能匹配成功。对应输入参数pattern:abcdbcd，i=4,j=1,g=3的情况。
ret = pattern[i-1] != pattern[j-1];
break;
}
}
return ret;
}
static void compute_prefix_tbl(struct ts_bm *bm)
{
int i, j, g;
for (i = 0; i < ASIZE; i++)
bm->bad_shift[i] = bm->patlen;
for (i = 0; i < bm->patlen - 1; i++)
bm->bad_shift[bm->pattern[i]] = bm->patlen - 1 - i;
/* Compute the good shift array, used to match reocurrences
* of a subpattern */
bm->good_shift[0] = 1;
for (i = 1; i < bm->patlen; i++)
bm->good_shift[i] = bm->patlen;
for (i = bm->patlen-1, g = 1; i > 0; g++, i--) {
for (j = i-1; j >= 1-g ; j--)这里对于前缀的搜索使用的是最为直观原始的方法，至少是一种我可以看明白的方法。其中i表示后缀suffix在pattern中下标，g表示从i到pattern结束位置之间的字符串长度，用C语言描述两个变量的关系为i+g=strlen(pattern)。j从i-1开始，从大到小(也就是对应字符串从右向左)一直递减到1-g，subpattern函数比较从j开始长度为g和从i开始长度为g的两个字符串从右向左比较是否满足subpattern条件。这里满足subpattern分两种情况，一种是两个字符串完全相等并且前一个字符不等；另一中情况是两个字符串从右向左只有部分字符串完全相等。
if (subpattern(bm->pattern, i, j, g)) {
bm->good_shift[g] = bm->patlen-j-g;//这里的j+g前面pattern的结束位置，从逻辑上看，这个位置需要和pattern结束位置对齐，所以这个移动位置就是bm->patlen-(j+g) = bm->patlen-j-g。如果bm->good_shift[g]=s，表示说从右向左匹配第g个匹配成功但是第g+1匹配失败时，string向后移动的距离。
break;//这个break比较关键，当寻找到一个匹配之后就跳出循环，也就是从右向左第一个满足subpattern的字符串就立即退出。
}
}
}