进击算法:字符串匹配的 BM 算法

进击算法:字符串匹配的 BM 算法

BM 算法介绍

各种文本编辑器的 "查找" 功能(Ctrl+F),大多采用 Boyer-Moore 算法。

Boyer-Moore 算法不仅效率高,而且构思巧妙,容易理解。1977 年,德克萨斯大学的 Robert S. Boyer 教授和 J Strother Moore 教授发明了这种算法。

下面我根据书籍 Algorithms on Strings, Trees, and Sequences 的第2章 Chapter 2 - Exact Matching: Classical Comparison-Based Methods 来介绍 BM 算法。

好后缀

假设匹配过程中发现x[i]=a 和 y[i+j] = b 不同,此时当前匹配的信息有:

x[i+1 .. m-1]=y[i+j+1 .. j+m-1]=u x[i] != y[i+j]

此时我们假设能找到u在x中的最右出现位置,则可以直接将x向右滑动shift距离。

but,如果我们没在x中找到u,则我们尝试去找到y[i+j+1 .. j+m-1]的最长后缀v,同时v也是x的前缀。

总结下上面两种情况:

  • u可以完整的再次出现在x中
  • u的后缀是x的前缀

坏字符

我们找到 y[i+j]=b 在x中最右出现的位置,如果没找到直接左对齐y[i+j+1]:

我们可以发现,坏字符的情况中,有可能shift是负数。

移动

我们可以根据上面的 好后缀和坏字符分别计算出 shift(好后缀) 和 shift(坏字符) ,我们最后真正移动的shift则是 max(shift(好后缀),shift(坏字符))。

算法实现

下面我们来分别计算 shift(好后缀) 和 shift(坏字符)。

先来求shift(坏字符),具体算法如下:

上面图中第一个说明是尾部不匹配的时候,我们查找字符a在pattern中的位置,假设是i,则Pattern shift的距离是 n-i

第二是是说如果失配发生在pattern中第j个位置,此时字符a在pattern中的位置为i,此时shift为j-i,此时意味着$i<j$,如果$i>=j$的话,此时我们只能取shift=1,下面我们来计算

// 整个下标从1开始
void PreBmBc(char *pattern, int n, int bmBc[])
{
    int i;
 
    for(i = 0; i < 256; i++)
    {
        bmBc[i] = 0;
    }
 
    for(i = 1; i <=n ; i++)
    {
        bmBc[pattern[i]] = i;
    }
}

下面我们来看好后缀怎么算计:

先看上图,我们定义L(i)为最大的小于n的位置,满足 P[i..n] 是 P[1..L(i)] 的后缀。 接着我们定义 L'(i),其含义如上图,我们在L(i)的基础上,定义P[i-1] != P[L'(i)-n+i-1]。

举个例子:

接着我们定义$N_j(P),N_j(P)$为P[1..j]和P[1..n]最长公共后缀。

我们来看下定义P[1..j],假设存在 i 满足L‘(i)=j,即P[i..n]是同后缀,并且P[i-1]!=P[j-n+i-1]也不同,即$N_j(P)=|P[i..n]| = n-i+1$,此时L'(i)=j,于是我们就有了下面的算法:

for i=1 to n, do L'(i) = 0
for j=1 to n-1, do 
    i = n - Nj(P) + 1
    L'(i) = j

上面算法中我们是假设已经知道了Nj(P)了,然后通过Nj来计算出L'(i),那我们怎么计算Nj呢?

// 后缀长度
void SuffixLength(const char *pattern, int n, int N[]) {
    for (int j = 1; j < n; j++) {
        int i;
        for (i = 0; pattern[n - i] == pattern[j - i] && i <= j; i++) {
        }
        N[j] = i;
    }
    N[n] = n;
}

计算完Nj,下面计算L':

void CalL(const char* pattern, int n, int L[], const int N[]){
    for (int i=1;i<=n;i++){
        L[i] = 0; // L[1] 是没意义的,这里也初始化为0
    }
    for (int j=1;j<n;j++){ // N[n] 是没有意义的,或者说 N[n] 一定为 n
        if (N[j]>0){
            int i = n - N[j] + 1;
            L[i] = j;
        }
    }
}

下面我们看另一种情况,当我们找不到后缀的时候,即L'(i)=0,我们可以退而求其次,求前缀,看下图:

我们定义 l'(i) 是P[i..n]的最长后缀同时也是P[1..n]的前缀,如果不存在这样子的前缀,则l'[i] = 0,此时的含义是说,此时shift=n,为什么移动最大呢?因为我们先去找Patten中是否存在P[i..n],因为如果要匹配,则pattern中必须要存在P[1..L'(i)],但是不幸的是没找到,这个时候我们可以直接先shift i-1,然后在慢慢右移,直到 l'(i),这个过程如下图:

下面就是怎么去计算l'(i)了。

我们如果假设l'(i)存在,即l'(i) = j>0,那么此时Nj(P) = j,并且此时 j 肯定小于等于 |P[i..n]| = n - i + 1,有了这么个洞见以后,我们再来看怎么计算l'(i).

假设N[j] == j, j<=n-i+1 => i<=n-j+1,此时j越大,i越小,因此我们就可以这么做了:

for j=1 to n-1:
    if Nj == j:
        for i from 1 to n-j+1
            l'(i) = j

代码如下:

void Call(const char* pattern, int n, int l[], const int N[]){
    for (int i=1;i<=n;i++){
        l[i] = 0; // l[1]其实没有意义,
    }
    for(int j=1;j<n;j++){
        if (N[j] == j){
            for (int i=1;i<=n-j+1;i++){
                l[i] = j;
            }
        }
    }
    l[1] = 0;
}

现在我们来看下怎么根据L'(i)和l'(i)来计算shift的距离:当P[i-1] != T[k] 的时候,如果 L'(i) > 0,则移动 n - L'(i),否则移动 n - l'(i),此处需要注意一个特殊情况,即 i=n 的时候,我们需要移动 1 位。

代码如下:

void PreBmGs(const char *pattern, int n, int bmGs[]) {
    // const char* p = pattern - 1; // 让下标从1开始
    vector N(0,n+1);
    vector L(0,n+1);
    vector l(0,n+1);
    SuffixLength(pattern, n, N.data());
    CalL(pattern,n,L.data(),N.data());
    Call(pattern,n,l.data(),N.data());

    for (int i=1;i<n;i++){
        if (L[i]>0){
            bmGs[i] = n - L[i];
        }else {
            bmGs[i] = n - l[i];
        }
    }
    bmGs[n] = 1; // special case
}

好了,现在一切就绪,我们开始整个搜索过程了,完整的搜索代码见github地址

另外一个完整搜索过程的图示可以看search examples

你的鼓励是我继续写下去的动力,期待我们共同进步。

这个时代,每个人都是超级个体!关注我,一起成长!

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏我杨某人的青春满是悔恨

Swift API 设计指南(下)

一般来说,默认参数比方法族(method families)更可取,因为它减轻了 API 使用者的认知负担。

732
来自专栏落影的专栏

程序员进阶之算法练习(二十五)

前言 算法题是锻炼思维的好工具,在解决问题的层面考察思考能力。 正文 1. Compote 题目链接 题目大意: 给出a、b、c三种材料,可以1:2:4组成...

3839
来自专栏数据结构与算法

P3818 小A和uim之大逃离 II

题目背景 话说上回……还是参见 https://www.luogu.org/problem/show?pid=1373 吧 小a和uim再次来到雨林中探险。突然...

3097
来自专栏ACM小冰成长之路

51Nod-1645-中位数变换

ACM模版 描述 ? 题解 这个题很明显是找规律的问题,直接暴力肯定会超时……虽然我也是暴力也两发才反应过来……平时做题总是抱着侥幸心理,比赛时却总是胆小如鼠…...

2117
来自专栏owent

不知道是哪一年的腾讯马拉松题目 照片评级 解题报告

结果就一不小心看到了这个充满回忆的ACM模式竞赛,还有咱腾讯的,就忍不住看了一下。

631
来自专栏AI科技大本营的专栏

送书 | 跟我一起学《流畅的Python》

本文引自图灵新书《流畅的Python》的第一章——Python数据模型。本书由奋战在Python开发一线近20年的Luciano Ramalho执笔,Victo...

3974
来自专栏追不上乌龟的兔子

[多少懂点位运算]找出唯一的数字

大家都知道现代计算机的底层是以二进制为基础的,计算机所有的操作最后都归结到了简单的二进制位运算上:与,或,非和异或。

2535
来自专栏数据结构与算法

群论入门

这东西一时半会儿写不完。。。 群 定义集合 ,*为集合G上的二元运算 当集合G在运算*之下满足一下性质时,我们称集合G在运算*之下是一个群,简称G是群 封闭性...

3545
来自专栏码云1024

c++ 虚继承

3337
来自专栏移动端开发

快速排序OC、Swift版源码

前言: 你要问我学学算法在工作当中有什么用,说实话,当达不到那个地步的时候,可能我们不能直接的感觉到它的用处!你就抱着这样一个心态,当一些APP中涉及到算法...

2208

扫码关注云+社区

领取腾讯云代金券