BM算法  Boyer-Moore高质量实现代码详解与算法详解

时间:2022-09-13 11:33:58

Boyer-Moore高质量实现代码详解与算法详解

鉴于我见到对算法本身分析非常透彻的文章以及实现的非常精巧的文章,所以就转载了,本文的贡献在于将两者结合起来,方便大家了解代码实现!

算法详解转自:http://www.searchtb.com/2011/07/%E5%AD%97%E7%AC%A6%E4%B8%B2%E5%8C%B9%E9%85%8D%E9%82%A3%E4%BA%9B%E4%BA%8B%EF%BC%88%E4%B8%80%EF%BC%89.html

C语言代码实现转自:

http://www-igm.univ-mlv.fr/~lecroq/string/node14.html

另外,网站http://www.cs.utexas.edu/users/moore/best-ideas/string-searching/fstrpos-example.html有个关于BM算法的详细例子,看看挺好的。

BM算法的论文在这儿http://www.cs.utexas.edu/users/moore/publications/fstrpos.pdf

BM算法

后缀匹配,是指模式串的比较从右到左,模式串的移动也是从左到右的匹配过程,经典的BM算法其实是对后缀蛮力匹配算法的改进。所以还是先从最简单的后缀蛮力匹配算法开始。下面直接给出伪代码,注意这一行代码:j++;BM算法所做的唯一的事情就是改进了这行代码,即模式串不是每次移动一步,而是根据已经匹配的后缀信息,从而移动更多的距离。

 j = ;

 while (j <= strlen(T) - strlen(P)) {

    for (i = strlen(P) - ; i >=  && P[i] ==T[i + j]; --i)

    if (i < )

       match;

    else

       j++;

 }

  

为了实现更快移动模式串,BM算法定义了两个规则,好后缀规则和坏字符规则,如下图可以清晰的看出他们的含义。利用好后缀和坏字符可以大大加快模式串的移动距离,不是简单的++j,而是j+=max (shift(好后缀), shift(坏字符))

BM算法  Boyer-Moore高质量实现代码详解与算法详解

先来看如何根据坏字符来移动模式串,shift(坏字符)分为两种情况:

  • 坏字符没出现在模式串中,这时可以把模式串移动到坏字符的下一个字符,继续比较,如下图:

BM算法  Boyer-Moore高质量实现代码详解与算法详解

  • 坏字符出现在模式串中,这时可以把模式串第一个出现的坏字符和母串的坏字符对齐,当然,这样可能造成模式串倒退移动,如下图:

BM算法  Boyer-Moore高质量实现代码详解与算法详解

此处配的图是不准确的,因为显然加粗的那个b并不是”最靠右的”b。而且也与下面给出的代码冲突!我看了论文,论文的意思是最右边的。当然了,尽管一时大意图配错了,论述还是没有问题的,我们可以把图改正一下,把圈圈中的b改为字母f就好了。接下来的图就不再更改了,大家心里有数就好。

为了用代码来描述上述的两种情况,设计一个数组bmBc['k'],表示坏字符‘k’在模式串中出现的位置距离模式串末尾的最大长度,那么当遇到坏字符的时候,模式串可以移动距离为: shift(坏字符) = bmBc[T[i]]-(m-1-i)。如下图:

BM算法  Boyer-Moore高质量实现代码详解与算法详解

数组bmBc的创建非常简单,直接贴出代码如下:

 void preBmBc(char *x, int m, int bmBc[]) {

    int i;

    for (i = ; i < ASIZE; ++i)

       bmBc[i] = m;

    for (i = ; i < m - ; ++i)

       bmBc[x[i]] = m - i - ;

 }

代码分析:

  • ASIZE是指字符种类个数,为了方便起见,就直接把ASCII表中的256个字符全表示了,哈哈,这样就不会漏掉哪个字符了。
  • 第一个for循环处理上述的第一种情况,这种情况比较容易理解就不多提了。

   第二个for循环,bmBc[x[i]]中x[i]表示模式串中的第i个字符。

   bmBc[x[i]] = m - i - 1;也就是计算x[i]这个字符到串尾部的距离。

  • 为什么第二个for循环中,i从小到大的顺序计算呢?哈哈,技巧就在这儿了,原因在于就可以在同一字符多次出现的时候以最靠右的那个字符到尾部距离为最终的距离。当然了,如果没在模式串中出现的字符,其距离就是m了。

再来看如何根据好后缀规则移动模式串,shift(好后缀)分为三种情况:

  • 模式串中有子串匹配上好后缀,此时移动模式串,让该子串和好后缀对齐即可,如果超过一个子串匹配上好后缀,则选择最靠左边的子串对齐。

BM算法  Boyer-Moore高质量实现代码详解与算法详解

  • 模式串中没有子串匹配上后后缀,此时需要寻找模式串的一个最长前缀,并让该前缀等于好后缀的后缀,寻找到该前缀后,让该前缀和好后缀对齐即可。

BM算法  Boyer-Moore高质量实现代码详解与算法详解

  • 模式串中没有子串匹配上后后缀,并且在模式串中找不到最长前缀,让该前缀等于好后缀的后缀。此时,直接移动模式到好后缀的下一个字符。

BM算法  Boyer-Moore高质量实现代码详解与算法详解

为了实现好后缀规则,需要定义一个数组suffix[],其中suffix[i] = s 表示以i为边界,与模式串后缀匹配的最大长度,如下图所示,用公式可以描述:满足P[i-s, i] == P[m-s, m]的最大长度s。

BM算法  Boyer-Moore高质量实现代码详解与算法详解

构建suffix数组的代码如下:

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

注解:这一部分代码乏善可陈,都是常规代码,这里就不多说了。

有了suffix数组,就可以定义bmGs[]数组,bmGs[i] 表示遇到好后缀时,模式串应该移动的距离,其中i表示好后缀前面一个字符的位置(也就是坏字符的位置),构建bmGs数组分为三种情况,分别对应上述的移动模式串的三种情况

  • 模式串中有子串匹配上好后缀

BM算法  Boyer-Moore高质量实现代码详解与算法详解

  • 模式串中没有子串匹配上好后缀,但找到一个最大前缀

BM算法  Boyer-Moore高质量实现代码详解与算法详解

  • 模式串中没有子串匹配上好后缀,但找不到一个最大前缀

BM算法  Boyer-Moore高质量实现代码详解与算法详解

构建bmGs数组的代码如下:

 void preBmGs(char *x, int m, int bmGs[]) {
int i, j, suff[XSIZE];
suffixes(x, m, suff);
for (i = ; i < m; ++i)
bmGs[i] = m;
j = ;
for (i = m - ; i >= ; --i)
if (suff[i] == i + )
for (; j < m - - i; ++j)
if (bmGs[j] == m)
bmGs[j] = m - - i;
for (i = ; i <= m - ; ++i)
bmGs[m - - suff[i]] = m - - i;
}

注解:

这一部分代码挺有讲究,写的很巧妙,这里谈谈我的理解。讲解代码时候是分为三种情况来说明的,其实第二种和第三种可以合并,因为第三种情况相当于与好后缀匹配的最长前缀长度为0。

由于我们的目的是获得精确的bmGs[i],故而若一个字符同时符合上述三种情况中的几种,那么我们选取最小的bmGs[i]。比如当模式传中既有子串可以匹配上好后串,又有前缀可以匹配好后串的后串,那么此时我们应该按照前者来移动模式串,也就是bmGs[i]较小的那种情况。故而每次修改bmGs[i]都应该使其变小,记住这一点,很重要!

而在这三种情况中第三种情况获得的bmGs[i]值大于第二种大于第一种。故而写代码的时候我们先计算第三种情况,再计算第二种情况,再计算第一种情况。为什么呢,因为对于同一个位置的多次修改只会使得bmGs[i]越来越小。

  • 代码4-5行对应了第三种情况,7-11行对于第二种情况,12-13对应第三种情况。
  • 第三种情况比较简单直接赋值m,这里就不多提了。
  • 第二种情况有点意思,咱们细细的来品味一下。

   1. 为什么从后往前,也就是i从大到小?     

    原因在于如果i,j(i>j)位置同时满足第二种情况,那么m-1-i<m-1-j,而第十行代码保证了每个位置最多只能被修改一次,故而应该赋值为m-1-i,这也说明了为什么要     从后往前计算。

   2. 第8行代码的意思是找到了合适的位置,为什么这么说呢?

    因为根据suff的定义,我们知道

    x[i+1-suff[i]…i]==x[m-1-siff[i]…m-1],而suff[i]==i+1,我们知道x[i+1-suff[i]…i]=x[0,i],也就是前缀,满足第二种情况。

3. 第9-11行就是在对满足第二种情况下的赋值了。第十行确保了每个位置最多只能被修改一次。

  • 第12-13行就是处理第一种情况了。为什么顺序从前到后呢,也就是i从小到大?

   原因在于如果suff[i]==suff[j],i<j,那么m-1-i>m-1-j,我们应该取后者作为bmGs[m - 1 - suff[i]]的值。

再来重写一遍BM算法:

 void BM(char *x, int m, char *y, int n) {
int i, j, bmGs[XSIZE], bmBc[ASIZE]; /* Preprocessing */
preBmGs(x, m, bmGs);
preBmBc(x, m, bmBc); /* Searching */
j = ;
while (j <= n - m) {
for (i = m - ; i >= && x[i] == y[i + j]; --i);
if (i < ) {
OUTPUT(j);
j += bmGs[];
}
else
j += MAX(bmGs[i], bmBc[y[i + j]] - m + + i);
}
}

BM算法  Boyer-Moore高质量实现代码详解与算法详解的更多相关文章

  1. Effective Python之编写高质量Python代码的59个有效方法

                                                         这个周末断断续续的阅读完了<Effective Python之编写高质量Python代码 ...

  2. 深入理解JavaScript系列(1):编写高质量JavaScript代码的基本要点

    深入理解JavaScript系列(1):编写高质量JavaScript代码的基本要点 2011-12-28 23:00 by 汤姆大叔, 139489 阅读, 119 评论, 收藏, 编辑 才华横溢的 ...

  3. 编写高质量JS代码的68个有效方法(八)

    [20141227]编写高质量JS代码的68个有效方法(八) *:first-child { margin-top: 0 !important; } body>*:last-child { ma ...

  4. 编写高质量JS代码的68个有效方法(七)

    [20141220]编写高质量JS代码的68个有效方法(七) *:first-child { margin-top: 0 !important; } body>*:last-child { ma ...

  5. 编写高质量JS代码的68个有效方法(六)

    [20141213]编写高质量JS代码的68个有效方法(六) *:first-child { margin-top: 0 !important; } body>*:last-child { ma ...

  6. 编写高质量JS代码的68个有效方法(四)

    [20141129]编写高质量JS代码的68个有效方法(四) *:first-child { margin-top: 0 !important; } body>*:last-child { ma ...

  7. 编写高质量JS代码的68个有效方法(三)

    [20141030]编写高质量JS代码的68个有效方法(三) *:first-child { margin-top: 0 !important; } body>*:last-child { ma ...

  8. 编写高质量JS代码的68个有效方法(二)

    [20141011]编写高质量JS代码的68个有效方法(二) *:first-child { margin-top: 0 !important; } body>*:last-child { ma ...

  9. JavaScript手札:《编写高质量JS代码的68个有效方法》(一)(1~5)

    编写高质量JS代码的68个有效方法(一) *:first-child { margin-top: 0 !important; } body>*:last-child { margin-botto ...

随机推荐

  1. Servlet访问第一次500,刷新后404的解决办法

    第一次运行错误:HTTP Status 500 -  --------------------------------------------type Exception reportmessage  ...

  2. android 内存泄漏分析技巧

    java虚拟机执行一般都有一个内存界限,超过这个界限,就会报outofmemory.这个时候一般都是存在内存泄漏.解决内存泄漏问题,窃以为分为两个步骤:分析应用程序是否真的有内存泄漏,找到内存泄漏的地 ...

  3. Postgresql standby(备机只读)环境搭建

    下载PostgreSQL源码包,放在任意目录 设置/etc/sysctl.conf,增加以下内容 kernel.shmmni= 4096 kernel.sem =501000 6412800000 5 ...

  4. MongoDB之整库备份还原单表collection备份还原

    MongoDB之整库备份还原单表collection备份还原 cd D:\MongoDB\bin 1整库备份: mongodump -h dbhost -d dbname -o dbdirectory ...

  5. 【AtCoder010】B - Boxes(差分)

    AtCoder Grand Contest 010 B题 题目链接 题意 n个盒子,第i个盒子有ai个石头. 重复这个步骤:选一个盒子i,每次从第i+j个盒子中移走j个石头,j从1到n,第n+k个盒子 ...

  6. 今天的任务--git练习

    克隆远程仓库项目 从版本控制中选择git 填写地址和本地目录,test测试成功后点击clone 克隆完成回到主界面,点击open打开刚才克隆的项目 git操作 添加文件py1.html 打开命令行 新 ...

  7. Python mongoDB读取

    class db_class(): def __init__(self): mongo_DB='test1' self.mongo_TABEL='test' client=pymongo.MongoC ...

  8. Newifi2&lpar;D1&rpar; 刷入pb-boot和breed的记录

    今天要给一个newifi d1刷系统时发现居然还是原厂的uboot, 使用uboot刷入rom时会进行校验拦截第三方的rom. 之前有刷过这个设备的, 但是已经完全记不清怎么处理的了. 查了一下, 这 ...

  9. URAL-1039 Anniversary Party---树形DP入门题

    题目链接: https://cn.vjudge.net/problem/URAL-1039 题目大意: 开一个party,每个员工都有一个欢乐值,只有是上司和下属不同时存在时才能欢乐,问怎样安排能有最 ...

  10. tf-idf sklearn

    第一步:语料转化为词袋向量 step 1. 声明一个向量化工具vectorizer: 本文使用的是CountVectorizer,默认情况下,CountVectorizer仅统计长度超过两个字符的词, ...