注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Tsecer的回音岛

Tsecer的博客

 
 
 

日志

 
 

内核中Boyer-Moore (BM)算法简单注释  

2014-08-28 17:17:07|  分类: Linux内核 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
一、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)\n", 
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!\n");
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的字符串就立即退出。
}
}
}

  评论这张
 
阅读(289)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017