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

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

ボイヤー-ムーア文字列検索アルゴリズム(Boyer-Moore String Search Algorithm)は、効率的な文字列検索アルゴリズムの一種[1]Robert S. BoyerJ Strother Moore が 1977年に開発した[2]ボイヤー-ムーア法とも呼ばれる。

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

定義[編集]

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 -
テキスト ANPANMAN に対して k=3 から k=8 までパターン PAN を配置した様子。k=5 の位置で一致している。
  • S[i] は、文字列 Si 番目の文字を指す。先頭は 1 である。
  • S[i..j] は、文字列 Si 番目から j 番目までを含む部分文字列を指す。
  • S のプレフィックスとは、文字列 S の長さを n としたとき、[1, n] の範囲にある i を使って表される S[1..i] という部分文字列を指す。
  • S のサフィックスとは、文字列 S の長さを n としたとき、[1, n] の範囲にある i を使って表される S[i..n] という部分文字列を指す。
  • 検索文字列を「パターン」と呼ぶ。
  • 検索対象文書を「テキスト」と呼ぶ。
  • パターンは P で表される。
  • テキストは T で表される。
  • P の長さを n とする。
  • T の長さを m とする。
  • P の最後尾の文字が T の先頭から k 番目の位置になるよう配置したとき、kT に対する P の「位置」とする。
  • P の一致または出現とは、配置した PT[(k-n+1)..k] が等価である場合をいう。

アルゴリズム[編集]

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

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

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

シフト規則[編集]

不一致文字規則[編集]

解説[編集]

- - - - X - - K - - -
A N P A N M A N A M -
- N N A A M A N - - -
- - - N N A A M A N -
パターン NNAAMAN での不一致文字規則の適用例

不一致文字規則は照合が失敗した位置の T 内の文字に注目する。P のその位置から左側にその文字が存在する場合、その位置までスキップさせて不一致となった文字が一致するよう提案する。P の左側にその文字が存在しない場合、不一致の発生した文字の次から P が配置されるような位置を提案する。

前処理[編集]

不一致文字規則のためのテーブルの正確な形式によって前処理の詳細は異なるが、単純な定数時間の参照では次のようになる。まず2次元のテーブルを作る。その際、第1の添字は文字 c のアルファベット順であり、第2の添字はパターン内の文字の位置 i である。このテーブルを参照すると、P 内で c が存在する位置 j の最大値(ただし j < i)を返すか、そのような c が存在しない場合は -1 を返す。提案するシフト量は i - j または n となる。アルファベットが有限で k 個とすれば、必要な領域は O(kn)、参照時間は O(1) となる。

一致サフィックス規則[編集]

解説[編集]

- - - - X - - K - - - - -
M A N P A N A M A N A P -
A N A M P N A M - - - - -
- - - - A N A M P N A M -
パターン ANAMPNAM での一致サフィックス規則の適用例

一致サフィックス規則は概念上も実装上も不一致文字規則より格段に複雑である。ボイヤー-ムーア法が最後尾から照合を始めるのはこの規則のためである。形式的には次のように説明される[3]

T に対して P がある位置に置かれ、T の部分文字列 tP のサフィックスと一致しているが、その左隣の文字で不一致になったとする。そこで、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 とする。これらの定義は次の通りである[3]

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] で、HL[i] がゼロとなるか、P 全体が一致した場合にのみ使われる。

ガリル規則[編集]

1979年、Zvi Galil はボイヤー-ムーア法に単純だが重要な改良を施した[4]。追加されたガリル規則はシフト量を決めるものではなく、各位置での照合を高速化するものである。位置 k1PT を照合して T 上の文字 c まで照合し、次にシフトした位置 k2 によりパターンの先頭の位置が ck1 の間になったとき、P のプレフィックスは部分文字列 T[(k2 - n)..k1] と必ず一致する。したがってこの際の文字照合は Tk1 の位置まででよく、k1 より前の照合は省略できる。ガリル規則はボイヤー-ムーア法の効率を向上させるだけでなく、最悪ケースでも線型時間であることを保証するのに必須である。

性能[編集]

オリジナルの論文では、パターンがテキスト内に存在しない場合のボイヤー-ムーア法の最悪ケースは O(n+m) だとされている。これは1977年、ドナルド・クヌースJames H. MorrisVaughan Pratt が初めて証明した[5]。さらに1980年、Leonidas J. GuibasAndrew Odlyzko が最悪ケースの文字比較回数の上限を 5m 回以下だと証明した[6]。1991年、Coleは最悪ケースの比較回数の上限が 3m 回以下であることを証明した[7]

パターンがテキスト内に出現する場合、オリジナルのアルゴリズムの最悪ケースは O(nm) となる。これはパターンもテキストも同じ文字の羅列の場合に容易に発生する。ただし、ガリル規則を加えるとあらゆるケースで線型時間となる[4][7]

実装例[編集]

派生[編集]

  • Apostolico-Giancarlo algorithm は、与えられた位置での照合に際して、一致することが分かっている文字の照合をスキップすることで高速化したものである。これは、パターンの前処理でえられた情報と各位置での一致したサフィックス長についての情報を利用する。ただし、これには検索対象のテキストと同じサイズの追加のテーブルを必要とする。

脚注[編集]

  1. ^ Hume and Sunday (1991) [Fast String Searching] SOFTWARE—PRACTICE AND EXPERIENCE, VOL. 21(11), 1221–1248 (NOVEMBER 1991)
  2. ^ Boyer, Robert S.; Moore, J Strother (October 1977). “A Fast String Searching Algorithm.”. Comm. ACM (New York, NY, USA: Association for Computing Machinery) 20 (10): 762–772. doi:10.1145/359842.359859. ISSN 0001-0782. http://dl.acm.org/citation.cfm?doid=359842.359859. 
  3. ^ a b Gusfield, Dan (1999) [1997], “Chapter 2 - Exact Matching: Classical Comparison-Based Methods”, Algorithms on Strings, Trees, and Sequences (1 ed.), Cambridge University Press, pp. 19–21, ISBN 0521585198 
  4. ^ a b Galil, Z. (September 1979). “On improving the worst case running time of the Boyer-Moore string matching algorithm”. Comm. ACM (New York, NY, USA: Association for Computing Machinery) 22 (9): 505–508. doi:10.1145/359146.359148. ISSN 0001-0782. http://dl.acm.org/citation.cfm?id=359146.359148. 
  5. ^ Knuth, Donald; Morris, James H.; Pratt, Vaughan (1977). “Fast pattern matching in strings”. SIAM Journal on Computing 6 (2): 323–350. doi:10.1137/0206024. http://epubs.siam.org/doi/abs/10.1137/0206024. 
  6. ^ Guibas, Odlyzko; Odlyzko, Andrew (1977). “A new proof of the linearity of the Boyer-Moore string searching algorithm”. Proceedings of the 18th Annual Symposium on Foundations of Computer Science (Washington, DC, USA: IEEE Computer Society): 189–195. doi:10.1109/SFCS.1977.3. http://dl.acm.org/citation.cfm?id=1382431.1382552. 
  7. ^ a b Cole, Richard (September 1991). “Tight bounds on the complexity of the Boyer-Moore string matching algorithm”. Proceedings of the 2nd annual ACM-SIAM symposium on Discrete algorithms (Philadelphia, PA, USA: Society for Industrial and Applied Mathematics): 224–233. ISBN 0-89791-376-0. http://dl.acm.org/citation.cfm?id=127830. 
  8. ^ 情報処理学会誌に掲載された論文(英語)

関連項目[編集]

外部リンク[編集]