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

gmd20的个人空间

// 编程和生活

 
 
 

日志

 
 

字符串匹配的Boyer-Moore algorithm和高效小巧的 Sunday algorithm  

2011-07-21 14:24:51|  分类: 程序设计 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

BM 算法最坏的情况可能比较字符的次数没有KMP算法好,但他最好的时间复杂度可以达到O(n/m) 要比KMP好,在字符集比较大的应用场合一般情况下好像是KMP性能的3到5倍? 说是是这个BM已经是字符匹配算法性能比较的基准了,算比较的实现了吧,很多文本编辑器的“查找”功能都是使用的这个。


他算法从字符串的末尾向前面开始比较:

abcdaddddddddddddddddd 
abcde
    ^
比如像上面这个字符串,先比较最后一个字符e 和 a,然后不匹配了,怎么去调整指针呢?

这个算法定义了两种规则

第一种叫做 “坏字符规则”

就是不匹配了,然后从 s 串的这个不匹配的字符a去找在 p模式串中的a最后一个位置,然后然后对齐两个比较就可以了。
所以下一步对齐就是

abcdaddddddddddddddddd 
    abcde
    ^
 
这个很容易理解吧,如果这个字符都没有出现过,那直接跳过整个字符串了,
   
abcdaddddddddddddddddd 
bbcde 
    ^
失配的字符a没有在 bbcde 出现过 所有下一次比较就是

abcdaddddddddddddddddd 
     bbcde 
     ^

预先计算模式串的“坏字符规则”数组是很简单的吧,假设他为 F[n]


那么对bbcde   这个串有
F[‘b'] =1   b 出现了两次,保存最后面那个位置
F[‘c'] =2
F[‘d'] =3
F[‘e'] =4
F[‘f'] = -1   字母f没有在bbcde 里面出现过,定义为 -1

大家都知道这个数组怎么计算的了吧!

void prepare_badcharacter_heuristic(const char *str, size_t size, int result[ALPHABET_SIZE])
{
        size_t i;
 
        for (i = 0; i < ALPHABET_SIZE; i++)
                result[i] = -1;
 
        for (i = 0; i < size; i++)
                result[(size_t) str[i]] = i;
}


则是下面这种情况用到。

第二种规则" 最佳后缀" 数组

bbbbadaaa
adadeda
     ^^
    ^
   
    这次查找的时候,a 和 d都匹配了,比较到 'a' 和 ‘e’的时候失配了。这时怎么办呢,如果按照前面的“坏字符规则”,,那个数组里面保存的a 出现的最后一个位置  adadeda里面最后一个出现的a还在 e的后面啊,如果按照前面的规则,那么这样移动指针,指针后退移动了
       
  bbbbadaaa
adadeda
      ^
     
这个指针为负的往后退的用法明显不给力阿,所以这时需要第二个规则 "最佳后缀" 数组

bbbbadaaaaaaaaaaaaa
adadeda
     ^^
    ^
   
这个比较失败后,应该去查找那个已经完全匹配的字串da是不是 在前面出现过了,然后对齐指针,就是这样
  
bbbbadaaaaaaaaaaaaa
    adadeda
     ^^
                
调整后再继续开始比较。 值得注意的是,这次比较里面,da匹配的部分是不是就重复比较了呢,上一次已经比较过了的,可能这就是BM算法子啊坏的情况下比KMP比较次数多的原因吧。


怎么把这个信息计算和保存到一个数组里面,其实是和KMP的跳转数组的计算一样的原理的了,就是计算字符串自身的最大匹配的前缀和后缀。可以参考一下我前面KMP算法里面理解,如果那个理解了,这个应该也是很容易理解的。

还有一种情况需要注意一下,比如 这个bab这个匹配了,但这个在abbab的前面没有出现了,但bab的子串ab 出现了,所以就是把这个子串ab对齐,有点类似 KMP算法里面的全匹配串搜索失败后继续尝试第二个最长的匹配串。
aabababacba
abbab                        
   abbab           
 
整个算法参考文章1里面说的比较清楚吧,如果你理解了KMP里面的跳转数据的计算,那理解这第二个规则 "好的后缀" 也就比较容易了,第一个规则就更简单了。 参考1 和wiki上面的参考2里面有提供有这个算法的实现了,可以去看一下,很容易理解的吧。


===============================
另外很多人觉的某种应用场合(模式串比较短,字符集比较大)BM算法规则二实现比较复杂而且用处不大,他们就省略了这个规则二,再改进了一下规则一,说是获得了比BM更好的性能,感兴趣的可以自己看一下参考文档 3和4,原理和实现非常简单的。

比如一个叫做 D.M. Sunday的人提出的Sunday algorithm(Quick Search algorithm)算法(D.M. Sunday: A Very Fast Substring Search Algorithm. Communications of the ACM, 33, 8, 132-142 (1990))是这样的,


abcabdaacba        s【m】
bcaab              p 【n】
      bcaab           调整后
^    ^^   

算法是这样工作的,可以按照任何顺序比较两个字符串(那个位置出现概率小,更容易引起失配,算法效果就越好阿),比如从第一个字符开始往后比较,   s[0] = 'a' != p[0] ='b'

那 么算法采用类似BM算法中的第一个“坏字符规则”,查找s串中p长度的后面一个字符,因为不管怎么移动指针,这个字符最后都要落在p里面的,现在就可以看 他是否在 p出现,然后用调整他们对齐的办法来移动指针。比如 s[5] = 'd' 不再 “bcaab” 中出现,那么可以调整指针让 p串对齐到
d的下一个开始的地方。

abcabcaacba        
bcaab            
^    ^
如果是上图,那么s串最后一个字符的下一个是c ,p串中的c 的最后一个出现位置是2,所以调整后是这样的

abcabcaacba        
    bcaab 
     ^
    
真个算法是不是非常简单呢,参考文章3 和4都给出了代码

比如3中给出的代码:

Preprocessing

The occurrence function occ required for the bad-character heuristics is computed in the same way as in the Boyer-Moore algorithm.

Given a pattern p, the following function sundayInitocc computes the occurrence function; it is identical to the function bmInitocc.

void sundayInitocc()
{
    int j;
    char a;

    for (a=0; a<alphabetsize; a++)
        occ[a]=-1;

    for (j=0; j<m; j++)
    {
        a=p[j];
        occ[a]=j;
    }
}

 
Searching algorithm

Using a function matchesAt that compares the pattern with the text window in a certain manner depending on the implementation, the searching algorithm looks as follows:

void sundaySearch()
{
    int i=0;
    while (i<=n-m)
    {
        if (matchesAt(i)) report(i);
        i+=m;
        if (i<n) i-=occ[t[i]];
    }
}

After statement i+=m, it is necessary to check if the value of i is at most n-1, since subsequently t[i] is accessed.




参考文档
1. Boyer-Moore algorithm   http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/bmen.htm 我把他转载到这个空间了
                        http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/bmen.htm
2. Boyer–Moore string search algorithm http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm

3. Sunday algorithm  http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/sundayen.htm

4. Quick Search algorithm http://www-igm.univ-mlv.fr/~lecroq/string/node19.html#SECTION00190

5. http://www-igm.univ-mlv.fr/~lecroq/string/   这个网页列出了各种各样的字符串的匹配算法,并且分析算法时间复杂度等比较,还给出了各种算法实现代码,非常全面。

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

历史上的今天

评论

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

页脚

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