文字列検索アルゴリズム③ ー Boyer-Moore法

自分の勉強用備忘録を兼ねて自分なりの言葉で色々な文字列検索アルゴリズムについて紹介していこうと思います。
本記事では Boyer-Moore法 について紹介します。

Boyer-Moore法は文字列探索アルゴリズムの一種で、文字列 $S$ と文字列 $T$ について $T$ が $S$ に含まれているか否かを、また含まれている場合はその位置を $O(|S||T|)$ 時間で求めることができます。ただし後述するガリル規則を加えると $O(|S|+|T|)$ 時間で求めることができます。

他の文字列検索アルゴリズムについてもまとめているので、よければご覧ください。

• 文字列検索アルゴリズム① ー Z algorithm
• 文字列検索アルゴリズム② ー KMP法

目次

1. Boyer-Moore法のアイデア
2. アルゴリズム
2.1. Bad Character Heuristic
2.2. Good Suffix Heuristic
2.3. 本処理
2.4. ガリル規則

Boyer-Moore法のアイデア

Boyer-Moore法ではKMPと同様、検索対象の文字列の先頭から順番に検索パターンの文字列と一致するかの確認を無駄な比較を極力飛ばしながら進めます。ただし検索パターンの文字列と一致するかの確認については後ろから比較して一致するかどうかを確認します。
まずは愚直な方法で文字列探索を行う流れを確認します。
$S = \text{“}aababacabcbc\text{”}$ と $T= \text{“}abcbc\text{”}$ を例に取り、 $T$ が $S$ に含まれているかを考えます。

下記アニメーションは $T$ が $S$ に含まれているかを愚直に前から調べたときのアニメーションです。ただし検索パターンの文字列と一致するかの確認については後ろから比較を行っています。このようにして $S[7:12] = T$ より、 $T$ が $S$ に含まれているということが分かります。

このアニメーションのように愚直に調べると、ひとつの $i\left(0 \le i \le |S|-|T|\right)$ に対して $S[i:i+|T|]$ と $T$ が一致するかの確認で最悪 $|T|$ 回の比較が必要になり、このアニメーションにおいては合計で $15$ 回の比較を行っています。

ここで上記のアニメーションの $S[1:6]$ と $T$ の比較に着目してみます。

$S[5] = \text{“}a\text{”} \neq \text{“}c\text{”} = T[4]$ なので $S[1:6]$ と $T$ は一致しないため、上記のアニメーションでは次の $S[2:7]$ と $T$ の比較に進んでいます。

ここで、不一致が生じた $S[5] = \text{“}a\text{”}$ に着目します。次の $S[2:7]$ と $T$ の比較では $S[5]$ と $T[3]$ を比較します。しかし $T[3] = \text{“}b\text{”}$ より、この時点で $S[2:7]$ と $T$ が一致しないことは分かるので、この比較は飛ばしてしまって良いです。同様に $S[3:8]$ と $T$ の比較と$S[4:9]$ と $T$ の比較も飛ばせます。

$S[5:10]$ と $T$ の比較については $S[5]$ と $T[0]$ を比較することになるのですが、 $T[0] = \text{“}a\text{”}$ なのでこの時点では $S[5:10]$ と $T$ が一致するかどうかは分かりません。したがって次の比較はここから始めれば良いです。

次に $S[5:10]$ と $T$ の比較に着目してみます。

$S[5:10]$ と $T$ は一致せず、上記のアニメーションでは次の $S[6:11]$ と $T$ の比較に進んでいます。ここで、一致している $S[8:10] = T[3:5] = \text{“}bc\text{”}$ に着目してみると、次の $S[6:11]$ と $T$ の比較では $S[8:10]$ に対応するのは $T[2:4]$ となり、これらを比較することになるのですが、 $T[2:4] = \text{“}cb\text{”} \neq \text{“}bc\text{”}$ より、一致しないです。

この不一致は $T[3:5] = \text{“}bc\text{”}$ と $T[2:4] = \text{“}cb\text{”}$ が一致しないことを前処理で事前に把握しておけば、比較せずに分かるため $S[6:11]$ と $T$ の比較を飛ばすことができます。
なお $T[3:5] = \text{“}bc\text{”}$ と $T[1:3] = \text{“}bc\text{”}$ は一致するため、 $S[7:12]$ と $T$ は比較が必要です。

同様に比較を飛ばせるところを全て飛ばして文字列探索を行うと以下のアニメーションのような流れになります。

愚直な方法では比較の回数は15回、こちらのアニメーションの手法では10回となっており、愚直な手法よりも少ない比較の回数で文字列探索を行えていることが確認できます。

このように上記のBad Character Heuristic（前者）とGood Suffix Heuristic（後者）の二つの規則に則って比較が不要なところを飛ばしながら文字列探索を行うというのがBoyer-Moore法のアイデアとなります。

アルゴリズム

それぞれの規則について詳細を説明していきます。

Bad Character Heuristic

Bad Character Heuristic は $S[i:i+|T|]$ と $T$ の比較の際に $S[i+j] \neq T[j]$ となった場合、 $T[k] = S[i+j]$ となるような 最大の $k$ を探し、 $S[i+j-k:i+j-k+|T|]$ と $T$ との比較まで飛ばす規則です。

これは前処理で、

$$B[c] := \max_{0 \le k \lt |T|} \left\lbrace k \bigm\vert T[k] = c\right\rbrace$$

をすべての文字 $c$ に対して求めておけば、 $S[i+j] \neq T[j]$ となったタイミングで $i := i+j-B[S[i+j]]$ と更新することで実現できます。なお、 $T[k] = c$ となるような $k$ がない場合は $B[c]=-1$ とすればよいです。また $i+j \lt B[S[i+j]] $ となってしまうとシフト幅が負になって、ループしてしまうため、最低でも $1$ はずらすようにする必要があります。

Bad Character Heuristic のみを実装したコードは以下のようになります。

import collections


def create_bad_calacter_heuristic_table(t):
    table = collections.defaultdict(lambda : -1)
    for k, c in enumerate(t):
        table[c] = k  # T[k] = c となる最大の k を各 c に対して求める
    return table


def boyer_moore_search(s, t):
    bad_calacter_heuristic_table = create_bad_calacter_heuristic_table(t)
    i = 0
    res = []  # S[i:i+|T|] = T となるすべての i を保持する配列
    while i + len(t) <= len(s):
        j = len(t) - 1
        k = i
        while j >= 0 and s[i + j] == t[j]:  # 不一致が生じるか、文字列が一致するまで j をディクリメント
            j -= 1
        if j < 0:  # 検索パターンと一致しているため出力に追加、Bad Character Heuristicが使えないためシフト幅は1
            res.append(i)
            shift = 1
        else:
            shift = max(j - bad_calacter_heuristic_table[s[i + j]], 1)  # 最低でも1はずらす
        i += shift
    return res

Good Suffix Heuristic

Good Suffix Heuristic は $2$ つの規則に分けることができます。 $1$ つ目は前章にあった図のようなケースで、 $S[i:i+|T|]$ と $T$ の比較の際に $S[i+j] \neq T[j]$ となった場合、 $T[k+1:k+|T|-j] = T[j+1:|T|] $ かつ $T[k] \neq T[j]$ となるような $j$ 未満の最大の $k$ を探し、$S[i+j-k:i+j-k+|T|]$ と $T$ との比較まで飛ばす規則です。

$2$ つ目は $S[i:i+|T|]$ と $T$ の比較の際に $S[i+j] \neq T[j]$ となった場合、 $T[0:|T|-k] = T[k:|T|]$ となるような $j+1$ 以上 $|T|$ 以下の最小の $k$ を探し、 $S[i+k:i+k+|T|]$ と $T$ との比較まで飛ばす規則です。

$1$ つ目、 $2$ つ目のどちらの規則についても Bad Character Heuristic と同様に前処理を行い、 $0 \le j \lt |T|$ に対して $S[i+j] \neq T[j]$ となった際の $i$ のシフト幅を求めておけば、規則を実現できます。

便宜上 $1$ つ目の規則によるシフト幅を $G_1$ 、 $2$ つ目の規則によるシフト幅を $G_2$ とします。また $S[i+j] \neq T[j]$ となった際の $i$ のシフト幅をそれぞれ $G_1[j+1]$ 、$G_2[j+1]$ とし、$S[i:i+|T|]$ と $T$ が一致したときのシフト幅をそれぞれ $G_1[0]$ 、$G_2[0]$ とします。
すると、Good Suffix Heuristic 全体のシフト幅 $G[j]$ は $T[k:k+|T|-j] = T[j:|T|] $ かつ $T[k-1] \neq T[j-1]$ となるような $1$ 以上 $j$ 未満の $k$ が存在する場合は、 $G[j] = G_1[j]$ 、存在しない場合は $G[j] = G_2[j]$ と定められます。

$G_1$ と $G_2$ のそれぞれの求め方について述べます。まず $G_1$ についてです。

$G_1[j]$ は先の条件を満たすような $k$ が存在する場合、次の式で与えられます。

$$G_1[j] := j-\max_{1 \le k \lt j} \left\lbrace k \bigm\vert T[k:k+|T|-j] = T[j:|T|] \land T[k-1] \neq T[j-1] \right\rbrace$$

実装の方針としては、 $k$ を $|T|$ から $1$ まで回して、 $T[k:k+|T|-j] = T[j:|T|] \land T[k-1] \neq T[j-1]$ となるようなすべての $j$ $(k \lt j \le |T|)$ に対して、$G_1[j]$ がすでに計算されているならば何もせず、そうでないなら $G_1[j] := j-k$ を代入します。

ここで各 $0 \le k \le |T|$ に対して、
$$f[k] := \min_{k \lt j \le |T|} \left\lbrace j \bigm\vert T[k:k+|T|-j] = T[j:|T|]\right\rbrace$$
が分かっていれば、 $T[k:k+|T|-j] = T[j:|T|]$ を満たすようなすべての $j$ $(k \lt j \le |T|)$ は $f[k], f[f[k]], f[f[f[k]]], ...$ の形で表すことができます。

これは、$T[k:k+|T|-j] = T[j:|T|]$ を満たす最小の $j$ が $f[k]$ であり、 $T[k:k+|T|-j] = T[j:|T|]$ と仮定すると、

$$T[k:k+|T|-j'] = T[j:j+|T|-j'] = T[j':|T|]$$

を満たす $j$ より大きい最小の $j'$ が $f$ の定義より、$f[j]$ であるため、帰納的に言えます。

なので $j \in \left\lbrace f[k], f[f[k]], f[f[f[k]]], ...\right\rbrace$ のうち $T[k-1] \neq T[j-1]$ も満たすような $j$ に対して、 $G_1[j] := j-k$ を代入すれば良いです。
なお実装においては各 $k$ に対して、 $j := f[k]$ で初期化し、 $j := f[j]$ と更新しながら上記を実行するのですが、すべての $\left\lbrace f[k], f[f[k]], f[f[f[k]]], ...\right\rbrace$ を見る必要はなく、 $T[k-1] = T[j-1]$ となったタイミングで終了してよいです。
これは $T[k-1] = T[j-1]$ となった場合、仮にある $j'=f[...[j]]$ $(j' \gt j)$ について $T[k-1] \neq T[j'-1]$ となったとしても、 $T[k-1] = T[j-1] \neq T[j'-1]$ が成り立つため、 $G_1[j'] = j'-j$ がすでに代入されているはずだからです。

$f$ は $T[k:k+|T|]$ の真の接頭辞（proper prefix）と接尾辞（suffix）が最も長く一致するときの接尾辞の開始位置を計算した配列になります。これはKMPの部分マッチテーブルをひっくり返したものであり、実装方法も部分マッチテーブルとほとんど同じなので詳細はこちらの記事の部分マッチテーブルに関する記載を参照してください。なお、便宜上 $f[|T|] = |T|+1$ とします。

$G_1$ を求めるコードは以下のようになります。

f = [0] * (len(t) + 1)
j = len(t) + 1
f[len(t)] = j
for k in reversed(range(1, len(t) + 1)):
    while j <= len(t) and t[k - 1] != t[j - 1]:
        j = f[j]
    f[k - 1] = j - 1
    j -= 1

table = [0] * (len(t) + 1)
# G_1 の計算
for k in reversed(range(1, len(t) + 1)):
    j = f[k]
    while j <= len(t) and t[k - 1] != t[j - 1]:  # 各 k に対して T[k:k+|T|-j] = T[j:|T|] かつ T[k-1] ≠ T[j-1] を満たす j を確認
        if table[j] == 0:  # もし G_1[j] が計算されていないならば、j-k を代入
            table[j] = j - k
        j = f[j]

なお $G_1$ を計算しているところの二重ループについてですが、こちらは変数 $k$ と $j$ に関して、 $f$ の計算における二重ループと全く同じ動きをします。先述の通り $f$ はKMPの部分マッチテーブルとほぼ同じ実装であり、その時間計算量も同じく $O(|T|)$ であるため、$G_1$ に関しても $O(|T|)$ 時間で求めることができます。

続いて $G_2$ についてです。

$G_2[j]$ は次の式で与えられます。$S[i+j] \neq T[j]$ となった場合の $i$ のシフト幅が $G_2[j+1]$ であるため、 $j \gt 0$ の場合は $k$ の範囲が $j \le k \le |T|$ となっていることに注意してください。

{G_2[j] = \left\lbrace
\begin{array}{ll}
\min_{0 \lt k \le |T|} \left\lbrace k \bigm\vert T[0:|T|-k] = T[k:|T|] \right\rbrace & (j = 0) \\
\min_{j \le k \le |T|} \left\lbrace k \bigm\vert T[0:|T|-k] = T[k:|T|] \right\rbrace & (j \gt 0)
\end{array}
\right.
}

ここで $G_1$ の計算において述べた通り、 $T[j:j+|T|-k] = T[k:|T|]$ を満たすようなすべての $k$ $(j \lt k \le |T|)$ は $f[j], f[f[j]], f[f[f[j]]], ...$ の形で表すことができます。つまり、 $T[0:|T|-k] = T[k:|T|]$ を満たすようなすべての $k$ $(0 \lt k \le |T|)$ は $f[0], f[f[0]], f[f[f[0]]], ...$ の形で表すことができます。

ということは、任意の $j$ に対して、 $G_2[j]$ の候補は $k \in \left\lbrace f[0], f[f[0]], f[f[f[0]]], ... \right\rbrace$ に限られるため、これらをすべて見て不等号の条件（ $j=0$ の場合は $0 \lt k \le |T|$ 、 $j\gt0$ の場合は $j \le k \le |T|$ ）を満たす最小の $k$ を $G_2[j]$ に代入すれば良いです。
実装上は $k := f[0]$ で初期化して、$j$ を $0$ から $|T|$ まで for ループで回しながら、以下を実行すれば良いです。

1. $G_2[j] = k$ を代入
2. $j = k$ ならば $k := f[k]$ と更新

これで良い理由を簡単に説明すると、まず $f, G_2$ の定義より、 $G_2[0] = f[0]$ は成り立ちます。また $G_2[j] = k$ であると仮定すると、$j \neq k$ すなわち $j \lt k$ ならば、

\begin{align}
k &= \min_{j \lt k' \le |T|} \left\lbrace k' \bigm\vert T[0:|T|-k'] = T[k':|T|] \right\rbrace \\
&= \min_{j+1 \le k' \le |T|} \left\lbrace k' \bigm\vert T[0:|T|-k'] = T[k':|T|] \right\rbrace \\
&= G_2[j+1]
\end{align}

であるため、そのまま次のループで $j := j+1$ と更新されても $G_2[j] = k$ と代入できます。
$j = k$ ならば、$f$ の定義より、

\begin{align}
f[k] &= \min_{k \lt k' \le |T|} \left\lbrace k' \bigm\vert T[k:k+|T|-k'] = T[k':|T|]\right\rbrace \\
&= \min_{j+1 \le k' \le |T|} \left\lbrace k' \bigm\vert T[k:k+|T|-k'] = T[k':|T|]\right\rbrace \\
&= \min_{j+1 \le k' \le |T|} \left\lbrace k' \bigm\vert T[0:|T|-k'] = T[k':|T|]\right\rbrace \\
&= G_2[j+1]
\end{align}

が成り立つため、$k := f[k]$ と更新することで、$j := j+1$ と更新したときに $G_2[j] = k$ が成り立ちます。なお 3 行目の式変形は $G_2[j] = k$ より、 $T[0:|T|-k] = T[k:|T|]$ であり、 $k \lt k'$ より、連続部分文字列について $T[0:|T|-k'] = T[k:k+|T|-k']$ が成り立つことを用いています。

よって帰納的に上記の実装で $G_2$ を求められます。

以上より、Good Suffix Heuristic 全体を実装したコードは以下のようになります。

def create_good_suffix_heuristic_table(t):
    f = [0] * (len(t) + 1)
    j = len(t) + 1
    f[len(t)] = j
    for k in reversed(range(1, len(t) + 1)):
        while j <= len(t) and t[k - 1] != t[j - 1]:
            j = f[j]
        f[k - 1] = j - 1
        j -= 1

    table = [0] * (len(t) + 1)
    for k in reversed(range(1, len(t) + 1)):
        j = f[k]
        while j <= len(t) and t[k - 1] != t[j - 1]:
            if table[j] == 0:
                table[j] = j - k
            j = f[j]

    # G_2の計算
    k = f[0]
    for j in range(len(t) + 1):
        if table[j] == 0:  # もし G_1[j] が代入されていないならば G[j] = G_2[j] を代入 
            table[j] = k
        if j == k:
            k = f[k]

    return table

本処理

本処理の探索では前処理で作成したそれぞれの規則のシフト幅のうち、大きい方を最終的なシフト幅として探索を進めれば良いです。全体のコードは以下の通りです。

import collections

def create_bad_calacter_heuristic_table(t):
    table = collections.defaultdict(lambda: -1)
    for k, c in enumerate(t):
        table[c] = k
    return table


def create_good_suffix_heuristic_table(t):
    f = [0] * (len(t) + 1)
    j = len(t) + 1
    f[len(t)] = j
    for k in reversed(range(1, len(t) + 1)):
        while j <= len(t) and t[k - 1] != t[j - 1]:
            j = f[j]
        f[k - 1] = j - 1
        j -= 1

    table = [0] * (len(t) + 1)
    for k in reversed(range(1, len(t) + 1)):
        j = f[k]
        while j <= len(t) and t[k - 1] != t[j - 1]:
            if table[j] == 0:
                table[j] = j - k
            j = f[j]

    k = f[0]
    for j in range(len(t) + 1):
        if table[j] == 0:
            table[j] = k
        if j == k:
            k = f[k]

    return table


def boyer_moore_search(s, t):
    bad_calacter_heuristic_table = create_bad_calacter_heuristic_table(t)
    good_suffix_heuristic_table = create_good_suffix_heuristic_table(t)
    i = 0
    res = []
    while i + len(t) <= len(s):
        j = len(t) - 1
        k = i
        while j >= 0 and s[i + j] == t[j]:
            j -= 1
        if j < 0:  # 検索パターンと一致しているため出力に追加、Bad Character Heuristicが使えないためシフト幅はGood Suffix Heuristicにより決定
            res.append(i)
            shift = good_suffix_heuristic_table[0]
        else:
            shift = max(j - bad_calacter_heuristic_table[s[i + j]], good_suffix_heuristic_table[j + 1])  # 2つの規則のうちシフト幅が大きい方を最終的なシフト幅とする
        i += shift
    return res

ガリル規則

この規則は Bad Character Heuristic や Good Suffix Heuristic の2つの規則と異なり、シフト幅を決定するものではなく、シフト後の無駄な比較を削るための規則となります。

具体的には前章で述べたところの $G_2$ のシフトが起きた後の比較を削るような規則で、 $S[i+j] \neq T[j]$ となったとき、もしくは $S[i:i+|T|] = T$ となったときに、 $G_2$ のシフトを行ったとします。シフト幅を $k$ とおくと、$S[i+k:i+k+|T|]$ と $T$ の先頭の $|T|-k$ 文字必ず一致します。そのため、次の比較ではこの部分まで比較をする必要はないので比較回数を減らすことができます。

なお、$G_2$ のシフトかどうかの判断ですが、シフト幅の範囲を考えると、Bad Character Heuristic は $1$ 以上 $j+1$ 以下、Good Suffix Heuristic の $G_1$ は $1$ 以上 $j$ 以下、 $G_2$ は $j+1$ 以上 $|T|$ 以下なので、シフト幅が $j+1$ 以上かつ $|T|$ 以下であれば、 $G_2$ のシフトであると言えます。

ガリル規則を実装した際のコードは下記の通りです。

import collections

def create_bad_calacter_heuristic_table(t):
    table = collections.defaultdict(lambda: -1)
    for k, c in enumerate(t):
        table[c] = k
    return table


def create_good_suffix_heuristic_table(t):
    f = [0] * (len(t) + 1)
    j = len(t) + 1
    f[len(t)] = j
    for k in reversed(range(1, len(t) + 1)):
        while j <= len(t) and t[k - 1] != t[j - 1]:
            j = f[j]
        f[k - 1] = j - 1
        j -= 1

    table = [0] * (len(t) + 1)
    for k in reversed(range(1, len(t) + 1)):
        j = f[k]
        while j <= len(t) and t[k - 1] != t[j - 1]:
            if table[j] == 0:
                table[j] = j - k
            j = f[j]

    k = f[0]
    for j in range(len(t) + 1):
        if table[j] == 0:
            table[j] = k
        if j == k:
            k = f[k]

    return table


def boyer_moore_search(s, t):
    bad_calacter_heuristic_table = create_bad_calacter_heuristic_table(t)
    good_suffix_heuristic_table = create_good_suffix_heuristic_table(t)
    i = 0
    p = 0  # すでに一致することが分かっている接頭辞の長さ
    res = []
    while i + len(t) <= len(s):
        j = len(t) - 1
        k = i
        while j >= p and s[i + j] == t[j]:  # すでに先頭何文字かが一致することが分かっている場合 j = 0 まで比較を行わなくてよい
            j -= 1
        if j < p:
            j = -1  # 次の p の決定の条件分岐のため j = -1 を代入
            res.append(i)
            shift = good_suffix_heuristic_table[0]
        else:
            shift = max(j - bad_calacter_heuristic_table[s[i + j]], good_suffix_heuristic_table[j + 1])
        p = len(t) - shift if j < shift <= len(t) else 0  # G_2によるシフトの場合、次の比較で必ず先頭の |T|-shift 文字は一致する
        i += shift
    return res

参考文献