ボイヤー-ムーア文字列検索アルゴリズム

ボイヤー-ムーア文字列 検索 アルゴリズム

ボイヤー-ムーア文字列検索アルゴリズムは、効率的な文字列検索アルゴリズムの一種であり、1977年にRobert S. BoyerとJ Strother Mooreによって開発されました。このアルゴリズムは、特に長いパターン文字列の検索においてその高速性が際立ち、テキストの前処理を行わない点が特徴です。

基本原理

ボイヤー-ムーア法の核となるのは、検索対象のテキスト全体を逐一チェックするのではなく、パターン文字列（検索文字列）を前処理することで得られた情報を用いて、テキスト内の照合を効率的にスキップすることです。このアプローチにより、検索処理の高速化を実現しています。このアルゴリズムでは、パターン文字列の末尾から先頭に向かって照合を行います。

用語の定義

- S[i]：文字列Sのi番目の文字。
- S[i..j]：文字列Sのi番目からj番目までの部分文字列（i文字目、j文字目を含む）。
- len(S)：文字列Sの長さ。
- プレフィックス：文字列Sの先頭を含む部分文字列。
- サフィックス：文字列Sの末尾を含む部分文字列。
- T：テキスト（被検索文字列）。
- P：パターン（検索文字列）。
- k：テキストT上でのパターンPの最後の文字の位置。

ここで、mはlen(T)、nはlen(P)を表します。PがTに一致するとは、T内にPと等価な部分文字列が存在することを意味します。

1. 初期設定：パターンPをテキストTの先頭に配置し、Pの最後の文字から照合を開始します。
2. 照合：パターンPの末尾から先頭へ向かって、テキストTとの文字照合を行います。不一致が発生するか、Pの先頭に到達するまで照合を続けます。一致が確認されれば、一致箇所が見つかったことになります。
3. シフト：不一致が発生した場合、またはパターン全体が一致した場合に、以下のシフト規則に従って、パターンPをテキストT上で右にシフトさせます。シフト量は、Pの前処理によって生成されたテーブルを参照して決定します。
4. 繰り返し：テキストTの末尾に到達するまで、上記2と3のステップを繰り返します。

シフト規則

ボイヤー-ムーア法では、効率的なシフトのために、以下の二つの主要な規則を利用します。

不一致文字規則

不一致が発生したテキストT内の文字に着目します。もしパターンPの中に、不一致が発生した文字と同じ文字が左側に存在すれば、その文字と一致するようにパターンをシフトさせます。もしパターン内に該当する文字が存在しない場合は、不一致が発生した文字の次の位置からパターンPを配置するようにシフトさせます。

前処理：この規則のため、パターンPの文字と位置を対応させたテーブルを作成します。このテーブルを参照することで、不一致時のシフト量を高速に決定できます。

一致サフィックス規則

この規則は不一致文字規則よりも複雑です。テキストT内で、パターンPのサフィックスと一致する部分文字列tが見つかり、その左隣の文字で不一致になった場合を考えます。このとき、tの左端からの部分文字列t'がPのサフィックス以外の場所に存在するかを調べ、もし存在すれば、t'とtが一致するようにPをシフトします。もし該当するt'が存在しない場合は、Pの左端がtの左端を過ぎるようにシフトし、tのサフィックスとPのプレフィックスが一致するように配置します。

前処理：一致サフィックス規則では、LテーブルとHテーブルという2つのテーブルを使用します。Lテーブルは、P[i..n]がP[1..L[i]]のサフィックスに一致し、かつサフィックスの前の文字がP[i-1]と異なる場合の最大の値を保持します。Hテーブルは、PのプレフィックスでもあるP[i..n]の最大サフィックスの長さを保持します。これらのテーブルを用いて、シフト量を決定します。

ガリル規則

1979年、Zvi Galilによって導入されたガリル規則は、照合処理を高速化するための改良です。この規則は、パターンのシフト量を決定するものではなく、照合の効率を向上させるものです。ガリル規則は、テキスト上で既に照合済みの部分をスキップすることで、不要な文字照合を減らすことができます。これにより、最悪の場合でも線形時間での検索を保証します。

性能

ボイヤー-ムーア法の最悪ケースの計算量はO(m+n)です。ただし、パターンがテキスト内に存在する場合、オリジナルのアルゴリズムの最悪ケースはO(mn)になる可能性があります。ガリル規則を追加することで、どのような場合でも線形時間での検索が可能になります。

実装例

このアルゴリズムは、Python、C、Javaなどの多くのプログラミング言語で実装されています。以下にPythonでの簡単な実装例を示します。

python
def boyer_moore(text, pattern):
n = len(text)
m = len(pattern)

if m == 0:
return 0

last_occurrence = {}
for i in range(m):
last_occurrence[pattern[i]] = i

i = m - 1
j = m - 1

while i < n:
if text[i] == pattern[j]:
if j == 0:
return i
else:
i -= 1
j -= 1
else:
if text[i] in last_occurrence:
l = last_occurrence[text[i]]
else:
l = -1
i += m - min(j, 1 + l) if l != -1 else m
j = m - 1
return -1

派生アルゴリズム

- ボイヤー-ムーア-ホースプール法：不一致文字規則のみを使用する簡略化されたアルゴリズム。
- Apostolico-Giancarlo アルゴリズム：一致した文字の照合をスキップすることで高速化を図るアルゴリズム。
- 連続文字列マッチング手法：連続する2つの文字列を使ってマッチングを行う手法。

まとめ

ボイヤー-ムーア法は、テキスト内の文字列検索において、特に長いパターン文字列の検索において、高い効率を発揮する強力なアルゴリズムです。不一致文字規則、一致サフィックス規則、ガリル規則などの要素を組み合わせることで、高速な検索を可能にしています。これらの規則を理解することで、より効率的な文字列検索の実装が可能になります。

もう一度検索

ボイヤー-ムーア文字列検索アルゴリズム