算法字符串

字符串精确匹配的BM算法

字数统计: 2.7k字   |   阅读时长: 11分
, , ,

摘要: BM算法原理与代码模板

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 KMP算法与代码模板 中，我们介绍了字符串精确匹配的 KMP 算法，这应该也是名声最大的算法，它是一种预处理+响应查询的思想，通过巧妙设计的预处理信息，避免扫描指针的回退，使得在最坏情况下也有线性的时间复杂度。

事实上，在实用场景中，字符串的精确匹配的暴力算法就很有效，原因在于如果输入数据分布是均匀的，暴力算法在平均情况下的时间复杂度依然是线性的，这一点以后我们可以推导一下。只是说如果考虑一些极端数据，暴力算法会出现“每次匹配都是往前走很长才发现匹配失败，再回退很多进行下一轮匹配”这种情况，会使得暴力算法的的时间复杂度恶化到平方级。

KMP 算法这种精巧的设计，解决的就是这些上述这种极端数据，从而使得最坏情况时间复杂度降低为线性级。然而实用场景中这类极端数据很少，最坏情况的提升感知并不明显，反而是预处理过程带来的额外开销感知很强烈，所以我们会发现一些语言的库里直接就是用暴力法实现的字符串匹配，而不是用看起来好像更好的 KMP 算法。

当然 KMP 算法也不是没有价值的，除了理论价值之外，它的预处理过程产出的中间结果，可以用来解决很多其他字符串上的问题，前面的文章中我们介绍过一些例题。此外预处理+响应查询的框架也很经典，在这个框架下，设计不同的中间信息，可以提出另外的算法，比如 BM 算法，本文我们来看 BM 算法。

BM 算法

BM 算法也是一种先预处理再响应查询的思路。巧的是，BM 算法也是在 1977 年提出的，与 Knuth、Morris、Pratt 提出 KMP 算法的年份一样。作者为 Boyer 和 Moore，论文名称是《A Fast string searching algorithms》，可以通过下面的链接下载。

《A Fast string searching algorithms》

BM 算法通过预处理文本字符串，创建一个坏字符表（bad character table）和一个好后缀表（good suffix table），在搜索过程中利用这些表来跳过不可能包含模式串的子串，从而提高搜索效率。

如下图，p 从左向右移动，固定 p 之后字符的比较从右向左。当出现失配时，用两个规则共同得出 p 向右偏移的量。两个规则分别是坏字符偏移，好后缀偏移。

假设目前 p 已经固定，正在对比 s[i..i+m-1] 和 p[0..m-1]。对比到 s[i+j] 和 p[j] 出现失配 s[i+j] != p[j]。

此时有 s[i+j+1..i+m-1] = p[j+1..m-1]。 记 a = p[j], b = s[i+j], u = p[j+1..m-1]，u 称为好后缀，b 称为坏字符。

下面分析当前情况下的好后缀偏移和坏字符偏移。

规则1. 好后缀偏移

  • 情况1: 在 p 中 u 再次出现，记为 u’，且 u’ 左侧是一个不同于 a 的字符 c 时，则将从右往左出现的第一个 u’ 与 s[i+j+1..i+m-1] 对齐，实现该对齐需要的偏移量存储在预处理数组 bmgs[j]。

  • 情况2: 在 p 中 u 没有再次出现，或者再次出现的 u 左侧都是 a，那么将 s[i+j+1..i+m-1] 中的最长后缀 v 与 p 中的 v 对齐，实现该对齐需要的偏移量也存储在预处理数组 bmgs[j]。

为了实现好后缀规则，需要定义一个数组 suffix，其中suffix[j] = s 表示以 j 为右边界，与模式串后缀匹配的最大长度。即满足 p[j-s..j] == P[m-1-s..m-1] 的最大长度 s。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void get_suff(const string& p, vector<int>& suffix)
{
    int m = p.size();
    suffix[m - 1] = m;
    int k;
    for(int j = m - 2; j >= 0; --j)
    {
        k = j;
        // k = j - s;
        while(k >= 0 && p[k] == p[m - 1 - j + k])
            --k;
        suffix[j] = j - k;
    }
}

若一个字符同时符合上述两种情况，那么我们选取最小的bmgs[j]。

比如当模式传中既有子串可以匹配上好后串，又有前缀可以匹配好后串的后串，那么此时我们应该按照前者来移动模式串，也就是bmgs[j]较小的那种情况。故而每次修改bmgs[j]都应该使其变小。

因此代码中 1,2,3 的顺序是必要的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<int> get_bmgs(const string& p)
{
    int m = p.size();
    vector<int> bmgs(m, 0);
    vector<int> suffix(m, 0);
    get_suff(p, suffix); // suffix[j] := 以 j 为结尾的子串匹配好后缀的最长匹配长度
    // 1. 没有好后缀 没有公共前缀
    for(int j = 0; j < m; ++j)
        bmgs[j] = m;
    // 2. 没有好后缀 有公共前缀 调用 suffix 但是要右移一位 类似KMP里的next数组
    int j = 0;
    for(int i = m - 1; i >= 0; --i)
        if(suffix[i] == i + 1)
            for(; j < m - 1 - i; ++j)
                if(bmgs[j] == m) //保证每个位置不会重复修改
                    bmgs[j] = m - 1 - i;
    // 3. 有好后缀 有公共前缀
    for(int i = 0; i < m - 1; ++i)
        bmgs[m - 1 - suffix[i]] = m - 1 - i; //移动距离
    return bmgs;
}

规则2. 坏字符偏移

  • 情况1: 在 p[0..m-2] 中，将从右到左 b 首次出现的位置与 s[i+j] 对齐，实现该对齐需要的偏移量存储在预处理数组 bmbc[b] 中。

  • 情况2: 在 p 中没有 b，则将 p[0] 与 s[i+j+1] 对齐，实现该对齐的偏移量也存储在预处理数组 bmbc[b] 中。

1
2
3
4
5
6
7
8
9
10
11
12
13
void get_bmbc(const string& s, const string& p, unordered_map<char, int>& bmbc)
{
    int m = p.size();
    for(const char& ch: s)
        if(bmbc.find(ch) == bmbc.end())
            bmbc[ch] = m;
    for(int j = 1; j < m; ++j)
    {
        if(bmbc[p[m - 1 - j]] != m)
            continue;
        bmbc[p[m - 1 - j]] = j;
    }
}

预处理好 bmbc 和 bmgs 之后就可以开始匹配过程了。

出现失配 s[i+j] != p[j] 后，p 向右的偏移量是 max(bmgs[i], bmbc[b] - m + i + 1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int bm_match(const string& s, const string& p, unordered_map<char, int>& bmbc, const vector<int>& bmgs)
{
    int n = s.size(), m = p.size();
    int i = 0;
    while (i <= n - m)
    {
        int j = m - 1;
        while(j >= 0 && p[j] == s[i + j])
            --j;
        if(j < 0)
        {
            return i;
            // i += bmgs[0]; // 找到完整匹配后仍继续往后找下一个完整匹配
        }
        else
           i += max(bmgs[j], bmbc[s[i + j]] - m + 1 + j);
    }
    return -1;
}

根据以上讨论，可以将 bmgs 和 bmbc 写出完整定义：

bmbc 表的容量是 s 中元素种类数。

  • 条件1：对于每个 $j < k < m，s \geq k$ 或者 $p[k-s] = p[k]$。
  • 条件2：若 $s < j$，则 $p[j - s] \neq p[j]$。

条件1用于计算p的某个后缀出去自身外的从最优侧开始出现出现时对应的偏移量(包含了前面讨论的两种情况)；条件2确保计算到 p 的第 j 个位置。

例子

以 p = GCAGAGAG 为例, s = “GCATCGCAGAGAGTATACAGTACG”, s 中的元素集合为 A, G, T, C

j 0 1 2 3 4 5 6 7
p[j] G C A G A G A G
bmgs[j] 7 7 7 2 7 4 7 1
b A C G T
bmbc[b] 1 6 2 8

代码(C++，模板)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
class Solution {
public:
    int strStr(string haystack, string needle) {
        if(needle.empty()) return 0;
        unordered_map<char, int> bmbc;
        get_bmbc(haystack, needle, bmbc);
        vector<int> bmgs = get_bmgs(needle);
        return bm_match(haystack, needle, bmbc, bmgs);
    }

    int bm_match(const string& s, const string& p, unordered_map<char, int>& bmbc, const vector<int>& bmgs)
    {
        int n = s.size(), m = p.size();
        int i = 0;
        while (i <= n - m)
        {
            int j = m - 1;
            while(j >= 0 && p[j] == s[i + j])
                --j;
            if(j < 0)
            {
                return i;
                // i += bmgs[0]; // 找到完整匹配后仍继续往后找下一个完整匹配
            }
            else
               i += max(bmgs[j], bmbc[s[i + j]] - m + 1 + j);
        }
        return -1;
    }

    void get_bmbc(const string& s, const string& p, unordered_map<char, int>& bmbc)
    {
        int m = p.size();
        for(const char& ch: s)
            if(bmbc.find(ch) == bmbc.end())
                bmbc[ch] = m;
        for(int j = 1; j < m; ++j)
        {
            if(bmbc[p[m - 1 - j]] != m)
                continue;
            bmbc[p[m - 1 - j]] = j;
        }
    }

    vector<int> get_bmgs(const string& p)
    {
        // 若一个字符同时符合上述两种情况，那么我们选取最小的bmGs[j]。
        // 比如当模式传中既有子串可以匹配上好后串，又有前缀可以匹配好后串的后串，
        // 那么此时我们应该按照前者来移动模式串，也就是bmGs[j]较小的那种情况。
        // 故而每次修改bmGs[j]都应该使其变小
        // 因此代码中 1,2,3 的顺序是必要的
        int m = p.size();
        vector<int> bmgs(m, 0);
        vector<int> suffix(m, 0);
        get_suff(p, suffix); // suffix[j] := 以 j 为结尾的子串匹配好后缀的最长匹配长度
        // 1. 没有好后缀 没有公共前缀
        for(int j = 0; j < m; ++j)
            bmgs[j] = m;
        // 2. 没有好后缀 有公共前缀 调用 suffix 但是要右移一位 类似KMP里的next数组
        int j = 0;
        for(int i = m - 1; i >= 0; --i)
            if(suffix[i] == i + 1)
                for(; j < m - 1 - i; ++j)
                    if(bmgs[j] == m) //保证每个位置不会重复修改
                        bmgs[j] = m - 1 - i;
        // 3. 有好后缀 有公共前缀
        for(int i = 0; i < m - 1; ++i)
            bmgs[m - 1 - suffix[i]] = m - 1 - i; //移动距离
        return bmgs;
    }

    void get_suff(const string& p, vector<int>& suffix)
    {
        // 为了实现好后缀规则，需要定义一个数组suffix，其中suffix[j] = s 表示以 j 为右边界，
        // 与模式串后缀匹配的最大长度，
        // 即满足p[j-s..j] == P[m-1-s..m-1] 的最大长度 s。
        int m = p.size();
        suffix[m - 1] = m;
        int k;
        for(int j = m - 2; j >= 0; --j)
        {
            k = j;
            // k = j - s;
            while(k >= 0 && p[k] == p[m - 1 - j + k])
                --k;
            suffix[j] = j - k;
        }
    }
};
Share