ボイヤー-ムーア文字列検索アルゴリズム（Boyer-Moore String Search Algorithm）は、効率的な文字列検索アルゴリズムの一種。 と が 1977年に開発した。ボイヤー-ムーア法とも呼ばれる。このアルゴリズムでは検索文字列（パターン）の前処理を行い、検索対象テキストの前処理は行わない。したがって、テキストについて何度も検索を行わない場合に適している（他のアルゴリズムではテキスト側に前処理を施し、繰り返し検索を行うことで前処理のコストを償却する）。テキスト上の全文字をチェックする必要はなく、前処理で得た情報を活用してスキップしながら処理していく。一般にパターン文字列が長いほど検索が高速化される。検索文字列とテキストの間での不一致が発生するたびに、不一致であったという情報を最大限に利用して照合しなくてもいい位置を可能な限り排除することで、効率を向上させている。ボイヤー-ムーア法は T における P の出現を検索するもので、異なる位置で明示的に何度も文字を比較することで検索する。全部で m - n + 1 カ所ある位置について力まかせ探索するのではなく、P を前処理して得た情報を使ってなるべく位置をスキップする。まず、k = n として P が T の先頭に配置されるようにする。そして P の n 番目と T の k 番目から文字を照合しはじめ、インデックスを順次小さくして照合していく。つまり、P の最後尾から先頭に向かって照合していく。この照合は不一致が発生するか P の先頭に到達するまで行われ（その場合は一致が見つかったことになる）、その後いくつかの規則に従って位置を右にシフトできる最大値を求める。新たな位置で再び同様の照合を行い、T の最後尾に到達するまでそれを繰り返す。シフト規則は、P の前処理で生成したテーブル群を参照することで実装されており、定数時間でシフト量が決定される。不一致文字規則は照合が失敗した位置の T 内の文字に注目する。P のその位置から左側にその文字が存在する場合、その位置までスキップさせて不一致となった文字が一致するよう提案する。P の左側にその文字が存在しない場合、不一致の発生した文字の次から P が配置されるような位置を提案する。不一致文字規則のためのテーブルの正確な形式によって前処理の詳細は異なるが、単純な定数時間の参照では次のようになる。まず2次元のテーブルを作る。その際、第1の添字は文字 c のアルファベット順であり、第2の添字はパターン内の文字の位置 i である。このテーブルを参照すると、P 内で c が存在する位置 j の最大値（ただし j < i）を返すか、そのような c が存在しない場合は -1 を返す。提案するシフト量は i - j または n となる。アルファベットが有限で k 個とすれば、必要な領域は O(kn)、参照時間は O(1) となる。一致サフィックス規則は概念上も実装上も不一致文字規則より格段に複雑である。ボイヤー-ムーア法が最後尾から照合を始めるのはこの規則のためである。形式的には次のように説明される。T に対して P がある位置に置かれ、T の部分文字列 t が P のサフィックスと一致しているが、その左隣の文字で不一致になったとする。そこで、t の左端からの部分文字列 t' が P のサフィックス以外の部分にないかを捜す。このとき、P のサフィックスの t の左隣の文字と P 内の t' の左隣の文字が違うものでなければならない。そして、P 内の部分文字列 t' が T の部分文字列 t と一致する位置に P をシフトする。t' が存在しなければ、P の左端が T における t の左端を過ぎた位置になるようシフトし、T 内の t のサフィックスとパターンのプレフィックスが一致するように配置する。そのようなシフトが不可能な場合、P の長さ n のぶんだけシフトする。P 全体が一致した場合、P のサフィックスとプレフィックスに一致があればそれを考慮してシフト量を最小にする。そのような一致がない場合は、P の長さ n のぶんだけシフトする。一致サフィックス規則には2つのテーブルを必要とする。1つは通常使用し、もう1つは前者が意味のある結果を返さない場合や一致が起きた場合に使う。前者のテーブルを L、後者のテーブルを H とする。これらの定義は次の通りである。各 i について L[i] は、文字列 P[i..n] が P[1..L[i]] のサフィックスに一致し、そのサフィックスの前の文字が P[i-1] と同じでない場合の最大の値を格納する。そのような条件を満たす位置がない場合 L[i] にはゼロを格納する。H[i] には P のプレフィックスでもある P[i..n] の最大サフィックスの長さを格納する（もしあれば）。そのような一致が存在しない場合 H[i] をゼロとする。どちらのテーブルも構築には O(n) の時間と O(n) の領域を必要とする。提案されるシフト量は n - L[i] または n - H[i] で、H は L[i] がゼロとなるか、P 全体が一致した場合にのみ使われる。1979年、 はボイヤー-ムーア法に単純だが重要な改良を施した。追加されたガリル規則はシフト量を決めるものではなく、各位置での照合を高速化するものである。位置 k で P と T を照合して T 上の文字 c まで照合し、次にシフトした位置 k によりパターンの先頭の位置が c と k の間になったとき、P のプレフィックスは部分文字列 T[(k - n)..k] と必ず一致する。したがってこの際の文字照合は T の k の位置まででよく、k より前の照合は省略できる。ガリル規則はボイヤー-ムーア法の効率を向上させるだけでなく、最悪ケースでも線型時間であることを保証するのに必須である。オリジナルの論文では、パターンがテキスト内に存在しない場合のボイヤー-ムーア法の最悪ケースは O(n+m) だとされている。これは1977年、ドナルド・クヌース、、 が初めて証明した。さらに1980年、 と が最悪ケースの文字比較回数の上限を 5m 回以下だと証明した。1991年、Coleは最悪ケースの比較回数の上限が 3m 回以下であることを証明した。パターンがテキスト内に出現する場合、オリジナルのアルゴリズムの最悪ケースは O(nm) となる。これはパターンもテキストも同じ文字の羅列の場合に容易に発生する。ただし、ガリル規則を加えるとあらゆるケースで線型時間となる。

出典:wikipedia