一、簡(jiǎn)介

此文介紹另一款更高效的字符串匹配算法，據(jù)稱較 KMP 算法而言，效率提高了3~5倍。

該算法由 Bob Boyer 和J Strother Moore 共同創(chuàng)建，故稱為 Boyer-Moore 字符串搜索算法，簡(jiǎn)稱 BM 算法。

我們?cè)谖谋疚臋n編輯的時(shí)候，常用的搜索功能（Ctrl + F），底層算法其實(shí)就是該 BM 算法。

二、名詞定義

以下摘自 wikipedia

• 被檢索的字符，也就是原文，稱為 text，用符號(hào) T 表示

• 檢索的字符串，也就是你需要搜索的字符串，稱為模式串，也稱為 pattern，用符號(hào) P 表示

• **P **的長(zhǎng)度記為 n

• **T **的長(zhǎng)度記為 m

• S[i] 為字符串 S 從1開(kāi)始計(jì)數(shù)的第 i 個(gè)字符

• S[i..j] 為字符串 S 的一個(gè)子串，始于i，終于j

• S 的前綴定義為 S[1..i]，其中 i 小于S 的長(zhǎng)度

• S 的后綴定義為 S[i..n]，其中n 為 S 的長(zhǎng)度

• k 表示 字符串P 的最后一位在 T 中的位置

• 當(dāng)發(fā)生匹配時(shí)，P 在 T 中的位置記為 T[(k-n+1)..k]

• 壞字符：T 和 P 中不匹配的字符（下文的案例中會(huì)詳細(xì)介紹）

• 好后綴：T 和 P 中相匹配的后綴（下文的案例中會(huì)詳細(xì)介紹）

三、原理簡(jiǎn)析

下面以圖示的方式，來(lái)簡(jiǎn)單闡述 BM 算法的匹配步驟。

首先，相較于樸素的算法，樸素算法是從 P 的首字符開(kāi)始匹配，直至出現(xiàn)不一致，然后再將 P 后移一定的位數(shù)。而 BM 算法的變通之處主要出現(xiàn)在兩點(diǎn)上：

① BM 算法從 P 的末字符開(kāi)始，依次往前進(jìn)行匹配，直至出現(xiàn)不一致；

② 此時(shí) P 需要右移，那么右移多少位呢？該位數(shù)由兩個(gè)子算法共同構(gòu)成，即 壞字符算法 和 好后綴算法，兩者分別進(jìn)行計(jì)算右移的位數(shù)，誰(shuí)算得的右移位數(shù)多，最終 P 右移的位數(shù)便會(huì)采用。

其實(shí)，壞字符和好后綴計(jì)算的右移位數(shù)的計(jì)算，都是查詢相應(yīng)的表而得到的，而這兩張表，就是 BM 的核心，即，該算法需要對(duì) P 進(jìn)行預(yù)處理，從而得出這兩張表。

四、簡(jiǎn)明圖示案例

BM 算法核心：找到一個(gè)后綴，讓已匹配過(guò)的后綴與P中從后往前最近的一個(gè)相同的子串對(duì)齊。

案例一：T為 0123456789 ， P為 MOORE

常規(guī)的匹配是先將0和M開(kāi)始匹配，不一樣，然后后移一位，再將1和M進(jìn)行匹配，依次類推，總共需要匹配10次，或者先進(jìn)一點(diǎn)，需要匹配6次，

而我們的 BM 算法，如果利用壞字符規(guī)則，則只需要匹配兩次：

第一次直接將4和E進(jìn)行匹配，出現(xiàn)不一致，此時(shí)我們需要將P后移，此時(shí)的4即為壞字符，那么后移多少位呢？此處根據(jù)核心：找到一個(gè)后綴，讓已匹配過(guò)的后綴與P中從后往前最近的一個(gè)相同的子串對(duì)齊，而此處，由于已匹配過(guò)的后綴是4，但是這個(gè)4并沒(méi)有出現(xiàn)在P中，所以將整個(gè)P往后移，直至P的首字符M位于4的后面，即將P往后移動(dòng)5個(gè)字符，也就是往后移P的長(zhǎng)度個(gè)字符。

另外，壞字符移動(dòng)規(guī)則公式為：后移位數(shù) = 壞字符位數(shù) – 壞字符在P中上次出現(xiàn)的位置

而此處：后移位數(shù) = 5 – 0 = 5，所以后移5位

第二次匹配的話，同理。所以，最后僅僅匹配了2次便查找完畢了，效率很高。

上述案例的運(yùn)行模式可以見(jiàn)下圖：

案例一配圖

案例二：T為 HERE IS A SIMPLE EXAMPLE ， P為 EXAMPLE

這個(gè)案例取自 BM 算法的創(chuàng)始人之一 Moore 教授自己言傳身教的例子。

先來(lái)說(shuō)說(shuō)什么是好后綴以及好后綴的一些移動(dòng)規(guī)則：

T 和 P 進(jìn)行匹配的時(shí)候，從P 的尾部開(kāi)始，匹配出的相同的字符串（包括單個(gè)字符）即為好后綴，

如 ABCDAB 和 BACD，首次匹配時(shí)，首字符對(duì)齊，從尾開(kāi)始匹配，發(fā)現(xiàn)有相同的字符串 “CD”，此時(shí)的好后綴有 “CD”和“D”，

知道了好后綴的定義，那么根據(jù)好后綴計(jì)算而得的右移位數(shù)的計(jì)算方式呢？ 右移位數(shù) = 好后綴的位置 – 好后綴在模式串P中上一次出現(xiàn)的位置。

此處需要注意三點(diǎn)：

① 好后綴的位置，以好后綴的最后一個(gè)字符為準(zhǔn)，即假設(shè)“BACD”的 CD 是好后綴，則好后綴的位置以“D”為準(zhǔn)，即4（從1開(kāi)始計(jì)算）；

② 如果好后綴在模式串中只出現(xiàn)過(guò)一次，比如：假設(shè)“BACD”的 CD 是好后綴，而 CD 僅出現(xiàn)了一次，則上一次出現(xiàn)的位置記做 0（即未出現(xiàn)過(guò)）；

③ 如果好后綴有多個(gè)，計(jì)算上次出現(xiàn)位置時(shí)，此時(shí)除了最長(zhǎng)的那個(gè)好后綴，其余的好后綴上次出現(xiàn)的位置必須是在頭部（即起始位置）。比如：假設(shè)“DCDBACD”的好后綴為 ACD，同樣，好后綴還有 CD，D，總共三個(gè)好后綴，我們依次來(lái)計(jì)算上次出現(xiàn)的位置，“ACD”僅出現(xiàn)一次，為0，當(dāng)沒(méi)有其它有效的好后綴的時(shí)候，便用這個(gè)；“CD”上次出現(xiàn)位置不在頭部，不計(jì)算；“D”這個(gè)字符正好和頭部相同，故“D”的上次出現(xiàn)位置為1，所以好后綴在模式串P中上一次出現(xiàn)的位置為1。

說(shuō)完了規(guī)則，那么我們正式看案例，見(jiàn)下圖：

案例二配圖

原理講明白了，那么我們就該搞清楚其中最為核心的 《壞字符規(guī)則表》和《好后綴規(guī)則表》 的生成原理了。

五、代碼實(shí)現(xiàn)

public static void boyerMoore(String pattern, String text) {
    int m = pattern.length();
    int n = text.length();
    Map<String, Integer> bmBc = new HashMap<>();
    int[] bmGs = new int[m];

    //初始化
    preBmBc(pattern, m, bmBc);
    preBmGs(pattern, m, bmGs);

    //開(kāi)始匹配
    int j = 0;
    int i;
    int count = 0;
    while (j <= n - m) {
        for (i = m - 1; i >= 0 && pattern.charAt(i) == text.charAt(i + j); i--) {
            //用于計(jì)數(shù)
            count++;
        }
        if (i < 0) {
            System.out.println("one position is:" + j);
            j += bmGs[0];
        } else {
            j += Math.max(bmGs[i], getBmBc(String.valueOf(text.charAt(i + j)), bmBc, m) - m + 1 + i);
        }
    }
    System.out.println("count:" + count);
}

/**
 * 壞字符初始化
 */
private static void preBmBc(String pattern, int patLength, Map<String, Integer> bmBc) {
    System.out.println("bmbc start process...");
    for (int i = patLength - 2; i >= 0; i--) {
        if (!bmBc.containsKey(String.valueOf(pattern.charAt(i)))) {
            bmBc.put(String.valueOf(pattern.charAt(i)), patLength - i - 1);
        }
    }
}

/**
 * 好后綴初始化
 */
private static void preBmGs(String pattern, int patLength, int[] bmGs) {
    int i, j;
    int[] suffix = new int[patLength];
    suffix(pattern, patLength, suffix);
    //模式串中沒(méi)有子串匹配上好后綴，也找不到一個(gè)最大前綴
    for (i = 0; i < patLength; i++) {
        bmGs[i] = patLength;
    }

    //模式串中沒(méi)有子串匹配上好后綴，但找到一個(gè)最大前綴
    j = 0;
    for (i = patLength - 1; i >= 0; i--) {
        if (suffix[i] == i + 1) {
            for (; j < patLength - 1 - i; j++) {
                if (bmGs[j] == patLength) {
                    bmGs[j] = patLength - 1 - i;
                }
            }
        }
    }

    //模式串中有子串匹配上好后綴
    for (i = 0; i < patLength - 1; i++) {
        bmGs[patLength - 1 - suffix[i]] = patLength - 1 - i;
    }
    System.out.print("bmGs:");
    for (i = 0; i < patLength; i++) {
        System.out.print(bmGs[i] + ",");
    }
    System.out.println();
}

private static void suffix(String pattern, int patLength, int[] suffix) {
    suffix[patLength - 1] = patLength;
    int q;
    for (int i = patLength - 2; i >= 0; i--) {
        q = i;
        while (q >= 0 && pattern.charAt(q) == pattern.charAt(patLength - 1 - i + q)) {
            q--;
        }
        suffix[i] = i - q;
    }
}

private static int getBmBc(String c, Map<String, Integer> bmBc, int m) {
    //如果在規(guī)則中則返回相應(yīng)的值，否則返回pattern的長(zhǎng)度
    return bmBc.getOrDefault(c, m);
}

六、資料

1、源碼地址：傳送門

2、有一篇文章可以參考，很不錯(cuò)，傳送門

原文地址：http://www.jetchen.cn/字符串匹配算法（二）BM/