Boyer-Moore算法的原理

写在前面

参考资料

• [1] Rabbit Hole的博客：算法复习笔记 —— Boyer-Moore算法

• [2] 苯苯吹雪的博客：Boyer-Moore高质量实现代码详解与算法详解

实现说明

• 本文使用到了C++17中字符串视图std::string_view进行编写。不熟悉的读者可以将其替换成const std::string &，效果是一样的。

概述

Boyer-Moore算法（简称BM算法）是一个优秀的字符串匹配算法，它能够高效地完成从主串中找到模式串出现位置的任务。

在C语言标准库中，有一个专门的函数strstr是用来干字符串匹配这活的。看看strstr的声明：char *strstr(const char *haystack, const char *needle);。其中haystack指的是主串，而needle指的是模式串。A needle in the haystack，大海捞针，可以说是十分形象地描述了字符串匹配这一任务本身的特点，以及它的难度了。

BM算法有一个显著的特点：别的算法都是从模式串的第一个字符往后比较，而BM算法却是从模式串的最后一个字符往前比较。这也是为了后续的匹配优化而作出的选择。

Boyer-Moore算法的优化思路

如果我们不管任何信息，直接硬匹配，那将是一个怎样的光景呢？我们给出一个无优化版的BM算法执行流程。

可以看到，如上图所示，每当出现失配（匹配失败）时，我们仅仅只把模式串后移1位，然后继续比对。可以很容易看出，如果不进行优化，该算法的复杂度应当是O(\text{len}(\text{haystack}))\times O(\text{len}(\text{needle}))。

因此，只是寻求失配本身所带来的经验也是不够的。如果存在一定的局部匹配，也应该借鉴KMP算法的思路——利用好局部匹配所带给我们的信息，从而获得最大幅度的滑动。[1]

BM算法在发生失配时的优化思路主要有两个：坏字符规则与好后缀规则。其中，坏字符指的是匹配失败时主串中失配的那个字符，而好后缀指的是匹配时匹配成功的那一部分后缀。如下图所示。具体而言，我们需要如KMP算法一般，为两种优化策略分别提前制作表格，以便在失配时获得更大的移动距离，从而加速算法。

坏字符（Bad Character）规则

坏字符指的是主串与模式串从后向前匹配时，主串中遇到的第一个失配字符（可以参考前面的图）。我们可以利用这个失配字符的信息来增加本次失配后模式串向后移动的距离。

从直觉上来说：如果主串中的失配的那个字符不存在于模式串中，那么我们就不必继续匹配这个字符了。这是因为模式串中的任意一个字符都不可能匹配上那个坏字符。因此将模式串整体向后移动到该坏字符之后即可。如下图所示。

而当主串中失配的那个字符存在于模式串中，那么我们可以将模式串移动到与那个失配字符相匹配之处。如下图所示。

具体而言，我们可以记录模式串中每个字符的出现位置，将其记录在一个表中，称作bc表。bc表的一个实现如下：

std::vector<long>
bc_table(std::string_view needle, long charset_size=128) {
    std::vector<long> bc(charset_size);
    int n = needle.size();
    for (long i = 0; i < charset_size; ++i) bc[i] = -1;
    for (long i = 0; i < n - 1; ++i) bc[needle[i]] = i;
    return bc;
}

当主串中出现了失配的字符c后，我们就可以在表中查找到坏字符在模式串中出现的位置，然后将模式串移动对应的距离即可。注意到：我们在构建bc表时，选用的是字符最后一次出现的位置。这是要防止模式串移动的距离过长，导致错过成功匹配的问题。

在字符集较大时（比如说汉语字符集相对于拉丁字母集而言），坏字符优化就显得非常有用了。这是因为主串中的坏字符存在于模式串中的概率变低了，这样一来，模式串可以更加频繁地大跨度移动，增加了算法运行的效率。

好后缀（Good Suffix）规则

如果BC表中对齐的位置在当前位置的右边时（如下图），并不需要回退模式串重新匹配（因为前面的位置已经被排除），此时可以简单将模式串前进一步。然而，如果这种情况大量出现，匹配的效率会大大降低。

也许我们可以移动到前方的坏字符处（如下图标“？”处）？前面给出的bc_table算法并没有考虑到这一点。如果修改算法使其能移动到“？”处，也会增加算法的时间/空间复杂性。

因此，在上面这种情况下，好后缀的规则就有用武之处了。当发生失配时，模式串可能与主串在某一段后缀上已经匹配成功了。如果模式串的后缀出现在模式串的前部，那么我们就可以将模式串向后移动，直到模式串前部的对应部分与主串的对应部分重合。这么讲可能有些抽象，我们可以看看模式串"123pq123"与主串"123qp123pq123"的匹配过程。

可以看到，在初始匹配时发生了失配。其中坏字符为'p'，而好后缀为"123"。注意到，模式串的前部也有一个"123"，因此我们可以将模式串前部的"123"向后拉，直到让其与主串刚刚匹配上的"123"对齐。

好后缀规则表格的具体计算过程主要包括计算ms表，然后通过ms表计算gs表。其中gs表是我们最终在进行匹配时直接需要的。

ms表的计算

所谓ms表，全称应该是max-suffix表，即最大后缀表。ms表与模式串的长度相同，其中ms[i]代表模式串的子串needle[0..i]（包含下标i处字符）与整个模式串needle的最大相同后缀长度。我们可以给出"123pq123"的ms表，如###所示。可以看到。ms[2]=3，这是因为needle[0..2] == "123"，与模式串共有长度为3的后缀 "123"而ms[7]=8，这是因为模式串与模式串本身相等，其最长的相同后缀就是模式串本身。ms表的很多项均为0，这是因为对应的子串与整个模式串没有共有的后缀。

[1]与[2]提供了两种计算ms表的算法。[1]算法更高效，而[2]算法更好理解。现将它们都贴上：

// Algorithm in [1]
std::vector<long>
ms_table1(std::string_view needle) {
    long n = needle.size();
    long upper = n - 1, lower = n - 1;

    std::vector<long> ms(n);
    ms[n - 1] = n;

    for (long i = upper - 1; i >= 0; --i) {
        if ((i > lower) && (i - lower >= ms[n - 1 - upper + i])) {
            ms[i] = ms[n - 1 - upper + i];
        }
        else {
            upper = i;
            lower = std::min(upper, lower);
            while (lower >= 0 && needle[lower] == needle[n-1-upper+lower]) lower--;
            ms[i] = upper - lower;
        }
    }

    return st;
}

// Algorithm in [2]
std::vector<long>
ms_table2(std::string_view needle)
{
    long n = needle.size();
    long upper = n - 1, lower = n - 1;

    std::vector<long> ms(n);
    ms[n - 1] = n;

    for (i = n - 2; i >= 0; --i) {
        q = i;
        while (q >= 0 && needle[q] == needle[n - 1 - i + q]) --q;
        ms[i] = i - q;
    }
}

关于方法1的说明：在循环中的else分支实质上就是在寻找(lower, upper]这一区间，这个区间满足这样一个性质：ms[i] = upper - lower，即模式串的子串needle[0..upper]与整个模式串needle具有最长的相同后缀needle[lower+1..upper]。

而if分支则利用所找到的较长后缀去计算较短的后缀。在计算ms[lower+1..upper]之间的值时，可以利用已经匹配好的后缀进行查找。如果i到lower的长度短于ms[n-1-upper+i]，那么needle[0..n-1-upper+i]的最长后缀一定等于needle[0..i]的。这是因为此时needle[0..n-1-upper+i]的最大后缀落在已匹配区间内，可以保证needle[0..n-1-upper+i]和needle[0..i]的最大后缀的长度相同；反之，若此时needle[0..n-1-upper+i]的最大后缀落在已匹配区间外，则无法保证这一点。

gs表的计算

gs表是在进行匹配时直接用到的表，其可以通过ms表简单计算而成。在计算gs表前，我们首先回忆一下利用好后缀思想进行优化的思想：由于模式串的前部的子串可能与后面已经成功匹配的部分相等，那么我们可以将模式串前面与已匹配串相等的部分拉到前面来，达到模式串在失配后向后移动多个位置的效果。

让我们仔细分析我们将模式串利用好后缀往后”拉“的各种情况，总共有三种情况，模式串向后移动的距离依次递增[2]。

1. 模式串中有子串匹配上好后缀。

   

2. 模式串中没有子串匹配上好后缀，但找到一个最大前缀。

   

3. 模式串中既没有子串匹配上好后缀，又找不到一个最大前缀。

   

为了防止错过完全匹配的情况，我们在三种情况中选取移动距离最小的情况。上面说到（其实我们也可以自己一眼看出），在移动距离上，情况3>情况2>情况1。因此我们按照情况3、情况2、情况1的顺序填gs表，这样移动距离小的情况就会覆盖移动距离大的情况。

std::vector<long>
gs_table(std::string_view pattern) {
    auto st = ms_table1(pattern);
    long n = pattern.size();
    std::vector<long> gs(n);

    // situation 1: no suffix is found
    for (long i = 0; i < n; ++i) {
        gs[i] = n;
    }

    // situation 2: prefix
    for (long i = 0, j = n - 1; j >= 0; --j) {
        if (st[j] == j + 1) {
            // pattern[0..i] is a matched suffix
            while (i < n - j - 1) {  // i can't be in the suffix
                gs[i++] = n - j - 1; // if i in the suffix, the distance will be n-i-1 not n-j-1
            }
        }
    }

    // situation 3: middle
    for (long i = 0; i < n - 1; ++i) {
        gs[n - 1 - st[i]] = n - i - 1;
    }

    return gs;
}

Boyer-Moore主算法

Boyer-Moore主算法在两种优化策略中进行择优。其最好情况复杂度为O(\text{len}(\text{haystack})/\text{len}(\text{needle}))。在上世纪八九十年代，有人证明了BM算法的复杂度上界为O(\text{len}(\text{haystack}) + \text{len}(\text{needle}))[1]。可见BM算法是一个非常高效的算法。

long
boyer_moore_match(std::string_view haystack, std::string_view needle) {
    auto bc = bc_table(needle);
    auto gs = gs_table(needle);

    long i = 0, m = needle.size(), n = haystack.size();
    while (i <= n - m) {
        long k = m - 1;

        while (haystack[i + k] == needle[k]) {
            if (k-- == 0) {
                break;
            }
        }

        if (k < 0) break;

        i += std::max(gs[k], k - bc[haystack[i + k]]);
    }

    if (i <= n - m) return i;
    return -1; //匹配失败
}