【模式匹配】更快的Boyer-Moore算法

1. 引言

前一篇中介紹了字符串KMP算法，其利用失配時已匹配的字符信息，以確定下一次匹配時模式串的起始位置。本文所要介紹的Boyer-Moore算法是一種比KMP更快的字符串匹配算法，它到底是怎么快的呢？且聽下面分解。

不同于KMP從 左右至右 與主串字符做比較，Boyer-Moore算法是從模式串的尾字符開始 從右至左 做比較，接下來討論的一些遞推式都與這個特性有關。

思想

首先，我們一般化匹配失敗的情況，設主串 \(y\) 、模式串 \(x\) 的失配位置為 i+j 與 i ，且主串、模式串的長度各為 \(n\) 與 \(m\) ，如下圖：

已匹配上的字符結構：

\[ y[i+j+1 \dots j+m-1] = x[i+1 \dots m-1] \]

失配后下一次匹配時，模式串的指針應移動到哪個位置呢（主串的指針依然在失配位置）？從上圖中看出，我們可以利用兩方面的信息：

1. 已經匹配上的字符結構，
2. 主串失配位置的字符

前一篇中所介紹的KMP只利用第一條信息，而Boyer-Moore算法則是已匹配、失配信息都利用到了，故主串的指針移動更為高效。同時，根據這兩方面信息（已匹配、失配信息），在Boyer-Moore算法引申出來兩條移動規則：好后綴移動（good-suffix shift）與壞字符移動（bad-character shift）。

實例

Moore教授在 這里 給出BM算法一個實例，比如主串= HERE IS A SIMPLE EXAMPLE ，模式串= EXAMPLE 。第一次匹配如下圖：

在第一次匹配中，模式串在尾字符發生失配，而主串的失配字符為 S ，且 S 不屬于模式串的字符；因此下一次匹配時模式串指針應向右移動 7 位（壞字符移動）。第二次匹配如下圖：

第二次匹配也是在模式串尾字符發生失配，但不同的是主串的失配字符為 P 屬于模式串的字符；因此下一次匹配時模式串的 P （從右開始第一次出現）應對齊于主串的失配字符 P （壞字符移動）。第三次匹配如下圖：

在第三次匹配中，模式串的后綴 MPLE 完全匹配上主串，主串的失配字符為 I ，不屬于模式串的字符；那么下一次匹配是模式串指針應怎么移動呢（是壞字符移動，還是好后綴移動？）？BM算法采取的辦法：移動步數= \(\max\{壞字符移動步數,\ 好后綴移動步數\}\) 。（具體移動步數的計算會在下面給出），這里是按好后綴移動；第四次匹配如下圖：

第四次匹配的情況與第二次類似，應按壞字符移動，第五次匹配（模式串與主串完全匹配）如下圖：

2. BM算法詳述

好后綴移動

因已匹配上的字符結構正好為模式串的后綴，故名之為 好后綴 。好后綴移動一般分為兩種情況：

1. 移動后，模式串有子串能 完全匹配 上好后綴；
2. 移動后，模式串只有能 部分匹配 上好后綴的子串

我們用數組 bmGs[i] 表示模式串的失配位置為 i 時好后綴移動的步數。第一類情況如下圖：

第二類情況如下圖：

接下來的問題是應如何計算 bmGs[i] 呢？我們引入 suff 函數，其定義如下：

\[ suff[i]=\max \{k:\ x[i-k+1\dots i]=x[m-k\dots m-1\},1\le m \]

表示了模式串中末字符為 x[i] 的子串能匹配模式串后綴的 最大長度 。其中， suff[i]=m 。

對于第一類情況，令 i+1=m-suff[a] ，則 x[i+1..m-1]=x[m-suff[a]..m-1] ；根據 suff 函數的定義，有 x[m-suff[a]..m-1]=x[a-suff[a]-1..a] ；則 x[i+1..m-1]=x[a-suff[a]-1..a] ，即可得到 bmGs[i]=bmGs[m-suff[a]-1]=m-1-a 。

對于第二類情況，由字符的部分匹配可得 x[0..m-1-bmGs[i]]=x[bmGs[i]..m-1] ，即 suff[m-1-bmGs[i]]=m-bmGs[i] 。令 m-bmGs[i]=a ，有 suff[a-1]=a 。因為是部分匹配，故 bmGs[i] = m-a > i+1 ，則 i < m-a-1 。綜上，當 i < m-a-1 且 suff[a-1]=a 時， bmGs[i]=m-a 。

有可能上述兩種情況都沒能被匹配上，則 bmGs[i]=m 。綜合上述三類情況， bmGs 數組計算的實現代碼（參看[2]）：

void preBmGs(char *x, int m, int bmGs[]) {
   int i, j, suff[XSIZE];

   suffixes(x, m, suff);

   // case 3, default value
   for (i = 0; i < m; ++i)
      bmGs[i] = m;
   j = 0;
   // case 2
   for (i = m - 1; i >= 0; --i)
      if (suff[i] == i + 1)
         for (; j < m - 1 - i; ++j)
            if (bmGs[j] == m)
               bmGs[j] = m - 1 - i;
   // case 1
   for (i = 0; i <= m - 2; ++i)
      bmGs[m - 1 - suff[i]] = m - 1 - i;
}

壞字符移動

壞字符移動是根據主串失配位置的字符 y[i+j] 而進行的移動。同樣地，我們用數組 bmBc[c] 表示主串失配位置字符為 c 時壞字符移動的步數。壞字符移動一般分為兩種情況：

1. 模式串 x[0..i-1] 有字符 y[i+j] 且第一次出現，如下圖：

   

2. 整個模式串都不包含該字符串，如下圖：

   

據此，可以將 bmBc[c] 定義如下：

\[ bmBc[c]=\min \{i: 1\le i < m \ and \ x[m-1-i]=c \} \]

表示距模式串末字符最近的 c 字符；若 c 字符未出現在模式串中，則 bmBc[c]=m 。C實現代碼：

void preBmBc(char *x, int m, int bmBc[]) {
   int i;

   for (i = 0; i < ASIZE; ++i)
      bmBc[i] = m;
   for (i = 0; i < m - 1; ++i)
      bmBc[x[i]] = m - i - 1;
}

suff函數計算

bmGs[i] 的計算依賴于 suff 函數；如何更為高效的計算 suff 函數成為了接下來需要考慮的問題。符號標記的定義如下：

• i 表示當前位置；
• f 記錄上一輪匹配的起始位置；
• g 記錄上一輪匹配的失配位置。

這里所說的 匹配 指的是與模式串后綴的匹配。同樣地，一般化匹配過程，如下圖：

當 g < i < f 則必有 x[i]=x[m-1-(f-i)]=x[m-1-f+i] ；

• 若 suff[m-1-f+i] < i-g ，則 suff[i]=suff[m-1-f+i] ；
• 否則， suff[i] 與 suff[m-1-f+i] 沒有關系，要根據定義進行計算。

C實現代碼：

void suffixes(char *x, int m, int *suff) {
   int f, g, i;

   suff[m - 1] = m;
   g = m - 1;
   for (i = m - 2; i >= 0; --i) {
      if (i > g && suff[i + m - 1 - f] < i - g)
         suff[i] = suff[i + m - 1 - f];
      else {
         if (i < g)
            g = i;
         f = i;
         while (g >= 0 && x[g] == x[g + m - 1 - f])
            --g;
         suff[i] = f - g;
      }
   }
}

復雜度分析

3. 參考資料