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

ウィキペディア

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

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/10 16:30 UTC 版)

このアルゴリズムでは検索文字列（パターン）の前処理を行い、検索対象テキストの前処理は行わない。したがって、テキストについて何度も検索を行わない場合に適している（他のアルゴリズムではテキスト側に前処理を施し、繰り返し検索を行うことで前処理のコストを償却する）。テキスト上の全文字をチェックする必要はなく、前処理で得た情報を活用してスキップしながら処理していく。一般にパターン文字列が長いほど検索が高速化される。検索文字列とテキストの間での不一致が発生するたびに、不一致であったという情報を最大限に利用して照合しなくてもいい位置を可能な限り排除することで、効率を向上させている。

記号の定義

A	N	P	A	N	M	A	N	-
P	A	N	-	-	-	-	-	-
-	P	A	N	-	-	-	-	-
-	-	P	A	N	-	-	-	-
-	-	-	P	A	N	-	-	-
-	-	-	-	P	A	N	-	-
-	-	-	-	-	P	A	N	-

テキスト T = "ANPANMAN" に対して k = 3 から k = 8 までパターン P = "PAN" を配置した様子。この場合、k = 5 の位置で一致する。

文字列 S に対する操作を以下のように表す：

• S[i]： 文字列 S の i 番目の文字
• S[i..j]： 文字列 S の i から j 番目までの部分文字列（i 文字目、j 文字目をそれぞれ含む）

文字列 S に含まれる文字の個数を文字列の長さと定義する。また、文字列 S の先頭を含む部分文字列をプレフィックス、末尾を含む部分文字列をサフィックスと定義する。

• len(S)：S の長さ
• S[1..i], 1 ≤ i ≤ len(S)：S のプレフィックス
• S[i..len(S)], 1 ≤ i ≤ len(S)：S のサフィックス

検索文字列をパターンと呼び、P で表す。被検索文字列をテキストと呼び、T で表す。また T 上での P の位置を T の先頭から数えた P の末尾の文字の位置と定義し、k で表す。

• T：テキスト（被検索文字列）
• P：パターン（検索文字列）
• k：テキスト T 上でのパターン P の最後の文字の位置（len(P) ≤ k ≤ len(T)）

「P が T に一致する」とは P と文字列として等価な部分文字列 T[i..j] が存在することをいう。より具体的に、P が位置 k で T と一致するとは、k 番目から前方 len(P) 文字分を取り出した部分文字列 T[(k − len(P) + 1)..k] が P と文字列として等価であることをいう。

本項では特に断りない限り、m を len(T), n を len(P) の意味で使う。

アルゴリズム

ボイヤー-ムーア法は T における P の出現を検索するもので、異なる位置で明示的に何度も文字を比較することで検索する。全部で m − n + 1 ある位置について力まかせ探索するのではなく、P を前処理して得た情報を使ってなるべく位置をスキップする。

まず、k = n として P が T の先頭に配置されるようにする。そして P の n 番目と T の k 番目から文字を照合しはじめ、インデックスを順次小さくして照合していく。つまり、P の最後尾から先頭に向かって照合していく。この照合は不一致が発生するか P の先頭に到達するまで行われ（その場合は一致が見つかったことになる）、その後いくつかの規則に従って位置を右にシフトできる最大値を求める。新たな位置で再び同様の照合を行い、T の最後尾に到達するまでそれを繰り返す。

シフト規則は、P の前処理で生成したテーブル群を参照することで実装されており、定数時間でシフト量が決定される。