MENU

Boyer-Moore算法

June 4, 2018 • 文章

一:背景

上一篇文章,我介绍了KMP算法

但是,它并不是效率最高的算法,实际采用并不多。各种文本编辑器的"查找"功能(Ctrl+F),大多采用Boyer-Moore算法。Boyer-Moore算法不仅效率高,而且构思巧妙。1977年,德克萨斯大学的Robert S. Boyer教授和J Strother Moore教授发明了这种算法。

二:算法过程

以下摘自阮一峰的字符串匹配的Boyer-Moore算法,并作稍微修改。

(1)

假定字符串为"HERE IS A SIMPLE EXAMPLE",搜索词为"EXAMPLE"。

(2)

首先,"字符串"与"搜索词"头部对齐,从尾部开始比较。

这是一个很聪明的想法,因为如果尾部字符不匹配,那么只要一次比较,就可以知道前7个字符(整体上)肯定不是要找的结果。

我们看到,"S"与"E"不匹配。这时,"S"就被称为"坏字符"(bad character),即不匹配的字符。我们还发现,"S"不包含在搜索词"EXAMPLE"之中,这意味着可以把搜索词直接移到"S"的后一位。

(3)

依然从尾部开始比较,发现"P"与"E"不匹配,所以"P"是"坏字符"。但是,"P"包含在搜索词"EXAMPLE"之中。所以,将搜索词后移两位,两个"P"对齐。

(4)

我们由此总结出"坏字符规则":后移位数 = 坏字符的位置 - 搜索词中的上一次出现位置。

我们约定,如果"坏字符"不包含在搜索词之中,则上一次出现位置为-1。

举个例子,以前面第三步的"P"为例,它作为"坏字符",出现在(相对)搜索词的第6位(从0开始编号),在搜索词中的上一次出现位置为4,所以后移 6 - 4 = 2位。再以前面第二步的"S"为例,它出现在第6位(相对搜索词),上一次出现位置是-1(即未出现),则整个搜索词后移 6 - (-1) = 7位。

(5)

依然从尾部开始比较,"E"与"E"匹配。

(6)

比较前面一位,"LE"与"LE"匹配。

(7)

比较前面一位,"PLE"与"PLE"匹配。

(8)

比较前面一位,"MPLE"与"MPLE"匹配。我们把这种情况称为"好后缀"(good suffix),即所有尾部匹配的字符串。注意,"MPLE"、"PLE"、"LE"、"E"都是好后缀。

为了接下来方便讲解,在这里作一下区分:我们统一称"MPLE"、"PLE"、"LE"、"E"为"好后缀",其中"MPLE"为"最长好后缀","PLE"、"LE"、"E"统一称为"真好后缀"。

(9)

比较前一位,发现"I"与"A"不匹配。所以,"I"是"坏字符"。

(10)

根据"坏字符规则",此时搜索词应该后移 2 - (-1)= 3 位。问题是,此时有没有更好的移法?

(11)

我们知道,此时存在"好后缀"。

所以,可以采用"好后缀规则":后移位数 = 好后缀的位置 - 搜索词中的上一次出现位置。

这个规则有三个注意点:

  1. "好后缀"的位置以最后一个字符为准。假定"ABCDEF"的"好后缀"是"EF"、"F",则它的位置以"F"为准,即5(从0开始计算)。
  2. 如果"好后缀"在搜索词中都只出现一次,则它们的上一次出现位置为 -1。比如,ABCDEF"的好后缀是"EF"、"F",但它们在"ABCDEF"之中都只出现一次,则它们的上一次出现位置为-1(即未出现)。
  3. 如果有多个"好后缀"在搜索词中都出现多次,那我们应该选哪个作为上一次出现的位置呢?我们采取的策略是:先查看"最长好后缀"是否也出现多次,如果是,直接选用这个"最长好后缀"作为上一次出现的位置;如果不是,则在"真好后缀"中选取"长度最长且也属于前缀"的那个"好后缀"。

举几个例子来具体说明上述的3个注意点。

  1. 如果"ABCDEF"的"好后缀"是"EF"、"F"。那么"好后缀"的位置是 5(从 0 开始计算,取最后的 "F" 的值),观察发现"好后缀"只出现一次,则它们的上一次出现位置为-1,则后移位数为5-(-1)=6;
  2. 如果"ABEFCDEF"的"好后缀"是"EF"、"F"。那么"好后缀"的位置是7,观察发现这两个"好后缀"都出现多次,则先查看"最长好后缀(EF)"是否出现多次,观察发现出现2次,所以选用"EF"为上一次出现的位置,"EF"上一次出现的位置为3,则后移位数为7-3=4;
  3. 如果"EFABCDEF"的"好后缀"是"CDEF"、"DEF"、"EF"、"F"。那么"好后缀"的位置是7,观察发现有两个"好后缀"出现多次,则先查看"最长好后缀(CDEF)"是否出现多次,观察发现不是,则在"真好后缀(DEF、EF、F)"中选取"长度最长且也属于前缀"的那个"好后缀",是"EF",其上一次出现的位置是1,则后移位数为7-1=6。

回到当前步骤的这个例子。此时,所有的"好后缀"(MPLE、PLE、LE、E)之中,只有"E"在"EXAMPLE"还出现在头部,所以后移 6 - 0 = 6位。

(12)

可以看到,"坏字符规则"只能移3位,"好后缀规则"可以移6位。所以,Boyer-Moore算法的基本思想是,每次后移这两个规则之中的较大值。

更巧妙的是,这两个规则的移动位数,只与搜索词有关,与原字符串无关。因此,可以预先计算生成《坏字符规则表》和《好后缀规则表》。使用时,只要查表比较一下就可以了。

(13)

继续从尾部开始比较,"P"与"E"不匹配,因此"P"是"坏字符"。根据"坏字符规则",后移 6 - 4 = 2位。

(14)

从尾部开始逐位比较,发现全部匹配,于是搜索结束。如果还要继续查找(即找出全部匹配),则根据"好后缀规则",后移 6 - 0 = 6位,即头部的"E"移到尾部的"E"的位置。

三:如何求坏字符表和好后缀表

3.1 坏字符算法(Bad Character)

当出现一个坏字符时, BM算法向右移动搜索词,让搜索词中最靠右的对应字符与坏字符相对,然后继续匹配。坏字符算法有两种情况。

(1)搜索词中有对应的坏字符时,让搜索词中最靠右的对应字符与坏字符相对。

第二个$x$即为移动后的位置。

(2)搜索词中不存在坏字符,那就直接右移整个搜索词长度这么大步数。

第二个$x$即为移动后的位置。

代码实现:

利用哈希空间换时间的思想,使用字符作为下标而不是位置作为下标。这样只需要遍历一遍即可。如果是纯8位字符也只需要256个空间大小,而且对于大数据,可能本身长度就超过了256,所以这样做是值得的(这也是为什么数据越大,BM算法越高效的原因之一)。

#define MAX_CHAR 256

/* 计算坏字符数组 */
void GetBC(string & p, int & m, int bc[])
{
    for (int i = 0; i < MAX_CHAR; i++)
        bc[i] = m;
    for (int i = 0; i < m; i++)
        bc[p[i]] = m - 1 - i;
}

3.2 好后缀算法(Good Suffix)

如果程序匹配了一个"好后缀",那就把前面的"好后缀"移动到当前"好后缀"位置。这样,好后缀算法有三种情况。

(1)搜索词中有子串和"最长好后缀"完全匹配,则将最靠右的那个完全匹配的子串移动到"最长好后缀"的位置继续进行匹配。

第二个$x$即为移动后的位置。

(2)如果不存在和"最长好后缀"完全匹配的子串,则选取长度最长且也属于前缀的那个"真好后缀"。

第二个$x$即为移动后的位置。

(3)如果完全不存在和"好后缀"匹配的子串,则右移整个搜索词。

第二个$x$即为移动后的位置。

代码实现:

#define MAX_LENGTH 1000  // 假定字符串长度不超过1000

/* 计算好后缀数组 */
void GetGS(string & p, int & m, int gs[])
{
    int suff[MAX_LENGTH];
    Suffixes(p, m, suff);

    // 第三种情况
    for (int i = 0; i < m; i++)
        gs[i] = m;

    // 第二种情况
    int j = 0;
    for (int i = m - 2; i >= 0; i--)
    {
        if (suff[i] == i + 1)
            for (; j < m - 1 - i; j++)
                gs[j] = m - 1 - i;
    }
  
    // 第一种情况
    for (int i = 0; i <= m - 2; i++)
        gs[m - 1 - suff[i]] = m - 1 - i;
}

看到这段代码,你可能会有很多的疑问,接下来我一步一步地讲解。

疑问 1:Suffixes(p, m, suff) 的作用

假定搜索词为p,长度为m,则数组suff[i]定义为:p[0...i]与p的最长公共后缀的长度。举个例子:

i0123456
p[i]ELEMELE
suff[i]1030107

那该怎么去求解它呢?

如上图,串p的长度为m,i是当前正准备计算suff[]值的那个位置。再设置两个变量,f和g。g代表以f为起始位置的字符匹配成功的最左边界,即"g = 最后一个成功匹配位置 - 1"。

当i处于f和g之间并且suff[m - 1 - (f - i)] < i - g,根据suff[f],我们可以推断出suff[i] = suff[m - 1 - (f - i)],图中椭圆的长度即为suff[m - 1 - (f - i)]

/* 计算后缀数组 */
void Suffixes(string & p, int & m, int suff[])
{
    int f;
    int g = m - 1; // 这里 g 必须要大于 m - 2,因为必须保证 i 等于 m - 2 的时候执行 else 语句
    suff[m - 1] = m;
    for (int i = m - 2; i >= 0; i--)
    {
        if (i > g && suff[m - 1 - f + i] < i - g)
            suff[i] = suff[m - 1 - f + i];
        else
        {
            if (i < g)
                g = i;
            f = i;
            while (g >= 0 && p[g] == p[m - 1 - f + g])
                g--;
            suff[i] = f - g;
        }
    }
}

疑问 2:第二种情况的代码怎么理解

// 第二种情况
int j = 0;
for (int i = m - 2; i >= 0; i--)
{
    if (suff[i] == i + 1)
        for (; j < m - 1 - i; j++)
            gs[j] = m - 1 - i;
}

第二种情况下,即如果不存在和"最长好后缀"完全匹配的子串,则选取长度最长且也属于前缀的那个"真好后缀"。代码为何这么写?

对于代码if (suff[i] == i + 1),如上图,两个椭圆的长度都是i + 1,其所表示的字符都对应相等。正如下面浅黑色字所述,若有if (suff[i] == i + 1),因为下标0前面没有字符,故[0, (m-1-i)-1]这部分的都只能找到"真好后缀"。

但如果是下面的情况呢?

假设[i, m-1]是"最长好后缀",但在整个串中只能找到"真好后缀"可以匹配,假设图中的两个椭圆互相匹配。那我们不是可以把区间[k, s]移到区间[j, m-1]的位置么?事实并非这么简单,我们观察k-1j-1这两个位置的字符,它们是不等的,所以这样的移动毫无意义,因此第二种情况,只需利用if (suff[i] == i + 1)就可以找到所有的部分后缀匹配。

疑问3:代码的顺序问题

// 第三种情况
for (int i = 0; i < m; i++)
    gs[i] = m;

// 第二种情况
int j = 0;
for (int i = m - 2; i >= 0; i--)
{
    if (suff[i] == i + 1)
        for (; j < m - 1 - i; j++)
            gs[j] = m - 1 - i;
}

// 第一种情况
for (int i = 0; i <= m - 2; i++)
    gs[m - 1 - suff[i]] = m - 1 - i;

首先要明确我们的目标:获得最精准的gs[]。最精准也就是尽可能小,因为如果值稍大的话,搜索词在跳转的时候就可能遗漏一个完全匹配。

for循环中的运行顺序三种情况代码的顺序之所以按如上代码那样安排,都是为了获得最精准的gs[]。下面我就从这两个方面解释。

  • for循环中的运行顺序

    • 第三种情况,i从0到m。这很简单,不用解释;
    • 第二种情况,i从m-2到0。若$i_1<i_2$,则有$m-1-i_1>m-1-i_2$,因此需要从后往前算;
    • 第一种情况,i从0到m-2。若$suff[i_1]==suff[i_2]$,其中$i_1<i_2$,则有$m-1-i_1>m-1-i_2$。
  • 三种情况代码的顺序

    • 第三种情况放在第一个位置,这很好理解;
    • 第二种情况和第一种情况,我们可以举个同时满足这两个情况的例子。假设搜索词为a....ba......ba, 读者自己手算一遍就懂了。

不知道读者有没有发现,第一和第二种情况的代码都没有i = m - 1。考虑第二种情况的代码,我们把i = m - 1代进去计算,发现程序会直接跳过。再看第一种情况的代码,我们把i = m - 1代进去计算,发现m - 1 - suff[i]为负,此时下标会溢出。

四:完整代码

#include <iostream>
#include <string>
#include <algorithm>

#define MAX_CHAR 256
#define MAX_LENGTH 1000

using namespace std;

/* 计算坏字符数组 */
void GetBC(string & p, int & m, int bc[])
{
    for (int i = 0; i < MAX_CHAR; i++)
        bc[i] = m;
    for (int i = 0; i < m; i++)
        bc[p[i]] = m - 1 - i;
}

/* 计算后缀数组 */
void Suffixes(string & p, int & m, int suff[])
{
    int f;
    int g = m - 1; // 这里 g 必须要大于 m - 2,因为必须保证 i 等于 m - 2 的时候执行 else 语句
    suff[m - 1] = m;
    for (int i = m - 2; i >= 0; i--)
    {
        if (i > g && suff[m - 1 - f + i] < i - g)
            suff[i] = suff[m - 1 - f + i];
        else
        {
            if (i < g)
                g = i;
            f = i;
            while (g >= 0 && p[g] == p[m - 1 - f + g])
                g--;
            suff[i] = f - g;
        }
    }
}

/* 计算好后缀数组 */
void GetGS(string & p, int & m, int gs[])
{
    int suff[MAX_LENGTH];
    Suffixes(p, m, suff);

    // 第三种情况
    for (int i = 0; i < m; i++)
        gs[i] = m;

    // 第二种情况
    int j = 0;
    for (int i = m - 2; i >= 0; i--)
    {
        if (suff[i] == i + 1)
            for (; j < m - 1 - i; j++)
                gs[j] = m - 1 - i;
    }

    // 第一种情况
    for (int i = 0; i <= m - 2; i++)
        gs[m - 1 - suff[i]] = m - 1 - i;
}

void BM(string & s, int & n, string & p, int & m)
{
    int bc[MAX_LENGTH];
    int gs[MAX_LENGTH];
    GetBC(p, m, bc);
    GetGS(p, m, gs);

    int j = 0, i;
    while (j <= n - m)
    {
        for (i = m - 1; i >= 0 && p[i] == s[i + j]; i--)
            ;
        if (i < 0)
        {
            cout << "在下标 " << j << " 位置找到匹配\n";
            j += gs[0];
        }
        else
            j += max(bc[s[i + j]] - m + 1 + i, gs[i]);
    }

    // PS: 匹配失败不作处理
}

int main()
{
    string s, p;
    int n, m;
  
    while (cin >> s >> p)
    {
        n = s.size();
        m = p.size();
        BM(s, n, p, m);
        cout << endl;
    }
  
    return 0;
}

数据测试如下:

this#is#a#simple#example
example
在下标 17 位置找到匹配

abcdef
xyz

aaaa
a
在下标 0 位置找到匹配
在下标 1 位置找到匹配
在下标 2 位置找到匹配
在下标 3 位置找到匹配
Archives QR Code Tip
QR Code for this page
Tipping QR Code