算法-字符串匹配(二)

发表于 分类于 ，
本文字数： 3.5k 阅读时长 ≈ 3 分钟

概述

BM 算法是一种经典地字符串匹配算法，而且实践证明：该算法比 KMP 算法匹配性能快 $3$ ~ $5$ 倍，故而文本编辑器的 “查询” 功能通常基于此算法实现。

在 KMP 算法中，文本串 text 与模式串 pattern 中字符采用从前往后方式进行比较。而在 BM 算法中，文本串 text 与模式串 pattern 中字符采用从后往前方式进行比较，其原因在于：1. 当采用从前往后方式比较时，如果第一个字符匹配失败，则 text 仅能前进一步 (即 i = i + 1)；当采用从后往前方式比较时，如果最后一个字符匹配失败，则 text 可前进 pattern.length() 步 (即 i = i + pattern.length() ) 。故而采用从后往前方式比较可取得更大的前进步数。2. 采用从后往前方式比较，存在多种事实规则以跳过无效匹配。

接下来，我们将首先给出从后往前比较字符以实施匹配字符串的算法，随后在此基础之上介绍 BM 算法。

基础算法

从后往前比较字符以实现字符串匹配算法，其实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int match(String text, String pattern) {

        int i = 0, j;
        for (; i < text.length() - pattern.length(); ) {
            // 尝试匹配pattern与text[i,i+pattern.length()]
            for (j = pattern.length() - 1; j >= 0 && text.charAt(i + j) == pattern.charAt(j); j--);

            // j=-1表明完全匹配成功，退出即可。
            if (j == -1) {
                return i;
            }

            // 移动一步。
            i += 1;
        }

    return -1;
}

BM 算法

BM 算法对基础算法的修改点就在于：基于某些事实规则尽可能多地移动步数 ( 即i += ? )。

BM 算法中，存在两种事实规则 —— 坏字符规则和好后缀规则 (详细内容可参见 字符串匹配的Boyer-Moore算法)。

当 text 与 pattern 中字符匹配失败时，根据两种规则计算移动步数，随后根据二者大者进行移动，然后继续进行匹配。

坏字符表

坏字符表用于实现坏字符规则，它是一个数组 bc[]，其中 bc[i] 具有如下含义：bc[i] 所示字符在 pattern 中最右侧出现位置。

坏字符表实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private int[] genBc(String pattern) {
    // 假定所有字符均为ascii，如果存在其他字符，这里也可使用map加以实现。
    int[] bc = new int[256];
    // 初始化为-1，表示未曾出现。
    Arrays.fill(bc, -1);
    
    // 从前往后，根据字符信息覆盖数组该位置原始信息。
    // 正是如此操作，才可保证所存位置信息均为对应字符的最右侧位置。
    for (int i = 0; i < pattern.length(); i++) {
        bc[pattern.charAt(i)] = i;
    }
    
    return bc;
}

好后缀表

好后缀表用于实现好后缀规则，它由两个数组组成，一个是 suffix[]，其中 suffix[k] 具有如下含义：长度为 $k$ 的后缀在 pattern 中出现时其首字母位置下标，一个是 prefix[]，其中 prefix[k] 具有如下含义：长度为 $k$ 的后缀是否存在一个相同的前缀。

此时重点就在于：如何根据 pattern 求取 suffix[] 和 prefix[]。求取方式十分巧妙：遍历 pattern 的所有真前缀，随后求取真前缀与 pattern 的公共后缀。在求取公共后缀过程中，我们可以动态得到这两个数组。具体参见如下代码：

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
private void genGs(String pattern, int[] suffix, boolean[] prefix) {
    // 初始化。
    Arrays.fill(suffix, -1);
    Arrays.fill(prefix, false);

    // 所有真前缀与pattern匹配
    for (int i = 0; i < pattern.length() - 1; i++) {
        int j = i;
        // k表示已匹配字符串长度
        int k = 0;
        
        // 真前缀与pattern从后往前匹配各个字符。
        while (j >= 0 && pattern.charAt(j) == pattern.charAt(pattern.length() - 1 - j)) {
            // 匹配成功则k++
            k++;
            // 根据suffix定义可设置该值。
            suffix[k] = j;
            --j;
        }

        // j=-1表明真前缀与某个后缀相同，则可设置prefix为true。
        if (j == -1) {
            prefix[k] = true;
        }
    }
}

匹配过程

BM 匹配过程十分简单，就是根据匹配失败位置及两种规则计算移动步数，随后选择大者进行移动即可。具体实现代码如下：

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
private int moveByGs(int[] suffix, boolean[] prefix, int j, int length) {
    // 确定好后缀长度
    int k = length - 1 - j;

    // 如果出现相同后缀，则根据其首字母位置计算步数。
    if (suffix[k] != -1) {
        return j + 1 - suffix[k];
    }

    // 如果存在与好后缀相同的前缀，则根据前缀计算步数。
    for (int r = k - 1; r >= 1; r--) {
        if (prefix[r]) {
            return length - r;
        }
    }

    // 否则，直接设移动步数为length。
    return length;
}

// BM
public int match(String text, String pattern) {
    // 初始化
    int[] bc = genBc(pattern);
    int[] suffix = new int[pattern.length() + 1];
    boolean[] prefix = new boolean[pattern.length() + 1];
    genGs(pattern, suffix, prefix);

    int i = 0, j;
    for (; i <= text.length() - pattern.length(); ) {
        // 尝试匹配pattern与text[i,i+pattern.length()]
        for (j = pattern.length() - 1; j >= 0 && text.charAt(i + j) == pattern.charAt(j); j--);

        // j=-1表明完全匹配成功，退出即可。
        if (j == -1) {
            return i;
        }

        // 基于坏字符规则确定需要移动的步数
        int x = j - bc[text.charAt(i + j)];
        int y = 0;
        // 如果存在好后缀，则基于好后缀规则确定需要移动的步数。
        if (j < pattern.length() - 1) {
            // 基于好后缀计算移动步数比较复杂，故而需要封装为函数。
            y = moveByGs(suffix, prefix, j, pattern.length());
        }

        // 取最大移动步数。
        i += Math.max(x, y);
    }

    return -1;
}

时空复杂度

理论证明：最坏时间复杂度为 $O(text.length + pattern.length)$，最好时间复杂度为 $O(text.length)$，空间复杂度为 $O(pattern.length)$。

与 KMP 比较

简单说明 KMP 与 BM 匹配算法的异同点：

  1. 两种算法均基于某些事实规则以跳跃无效匹配。
  2. 在 KMP 算法中，基于相同前后缀实施跳跃；在 BM 中，基于坏字符规则和好后缀规则实施跳跃，并且好后缀规则中包含了相同前后缀。
  3. 在 KMP 算法中，从前往后匹配 text 与 pattern 中字符；在 BM 算法中，从后往前匹配 text 与 pattern 中字符。
  4. 在 KMP 算法中，主要移动 pattern ；在 BM 算法中，主要移动 text。