BM法

BM法の考え方

応用編第2日目で述べたとおり、BM法や、KMP法よりも、理論的にも実践的にも優れた方法です。KMP法とBM法の大きな違いは、KMP法がパターンを先頭から比較していくのに対して、BM法は、後ろから比較していくという方法をとる点にあります。

BMとは、Boyer-Mooreの略で、やはりKMP法と同様にアルゴリズムの作者の頭文字をとったものです。このアルゴリズムでポイントになるのは、BM法は、不一致になった文字によって、パターンを何文字ずらしていくかを決定するという点にあります。

パターンの分類

このように、パターンの後ろ側から比較を始めていくBM法ですが、この際、その比較結果により、処理は以下の2つに分類されます。

抽象的な説明だけだと分かりずらいので、実際のサンプルを通して説明していくことにします。

BM法の実際

不一致だった文字が、パターンに含まれる文字でなかった場合

まずは、一番シンプルなケースである、不一致だった文字が、パターンに含まれる文字でなかった場合について説明しましょう。

(1) パターンの末尾が一致しない場合
パターンが「abc」、テキストが「defghi」だったケースについて考えてみましょう。このとき、パターンの末尾と、テキストの該当箇所を比較すると、前者が「c」であり、後者が「f」で、不一致です。この「f」という文字は、パターンには含まれない文字ですから、この文字列が、パターンの一部だと考えることはできません。

この時、テキストの注目点は、テキストの「f」の上にあります。したがって、ここからパターンの文字数である、3文字分移動し、注目点は、現在の位置から3右にずれることになります。(図3-1.)

図3-1.パターンの末尾が一致しない場合
パターンの末尾が一致しない場合

(2) 途中の文字が一致しない場合
続いて、パターンが「abcdef」、テキストが「xyzdefghi」だったケースについて考えてみましょう。この場合、末尾から3文字目までは、「f」と「e」、「d」と一致しますが、末尾からの4文字目が、パターンの場合は、「c」、テキストの場合は「z」となり、不一致です。(図3-2.)

図3-2.途中の文字が一致しない場合
途中の文字が一致しない場合

このような場合も、「z」という文字がパターンに含まれていないことから、それ以前にさかのぼっても、一致することがないことがわかります。なので、この注目点から、パターンの文字数である5文字分移動した地点から比較を再開します。

不一致だった文字が、パターンに含まれる文字であった場合

続いて、不一致だった文字が、パターンに含まれる文字であった場合についてみてみましょう。

(1) パターンの末尾が一致しない場合
パターンが「abc」、テキストが「abaacd」だった場合について考えてみましょう。このとき、パターンの末尾と、テキストの該当箇所を比較すると、前者が「c」であり、後者が「a」で、不一致です。しかし、テキストの文字「a」は、パターンの中に含まれていることがわかります。(図3-3.)

図3-3.パターンの末尾が一致しない場合
パターンの末尾が一致しない場合

この時、現在比較している文字「c」がパターンの3文字目、そして、不一致だったテキストの文字「a」の現れる位置が、パターンの1文字目であることから、この差である、2文字分右へテキストの注目点を移動します。すると、パターンの先頭の文字と、該当する位置のテキストの文字が一致し、ここから新に毛比較を再開すればよいことがわかります。

(2) 途中の文字が一致しない場合
続いて、パターンが「abcdef」、テキストが「cbadefaab」だったケースについて考えてみましょう。この場合、末尾から3文字目までは、「f」と「e」、「d」と一致しますが、末尾からの4文字目が、パターンの場合は、「c」、テキストの場合は「a」となり、不一致です。(図3-4.)

図3-4.パターンの末尾が一致しない場合
パターンの末尾が一致しない場合

ただ、この「a」という文字列は、パターンの中に存在しています。現在パターンは「c」という3文字目の文字に着目しており、なおかつこの「a」という文字は、パターンの1文字目ですからこの差である2文字分だけ、テキストの注目位置を右に移動させます。すると、テキストの2文字目の「a」と、新たな位置に移動したパターンの先頭の「a」が一致します。

BM法の特徴

BM法の計算量

BM法を実際に運用してみると、ほとんどの場合、パターンの文字数をm文字とすると、m文字ずつパターンがずれていくことになります。したがって、実質的にO(n/m)の計算量になることが想定されます。

ただ、実質的には、力まかせ法と、KMP法は、ほぼO(n)であることがほとんどです。力まかせ法が最悪の結果を得るのは、テキストに対してパターンがほとんど同じ位という特殊なケースであるからです。

BM法の問題点

では逆に、BM法の問題点はどこにあるのでしょうか？BM法で最悪のケースとして想定されるのが、テキストの文字がすべて「a」であり、パターンの文字が、「baa」のように、先頭以外はすべて「a」というケースです。この場合は、力まかせの場合と同じで、計算量はO(mn)となります。

しかし、こういったケースが極めて例外的なケースであるということは、容易にわかるでしょう。したがって、たいていの場合は、BM法が、力まかせ法およびKMP法よりも優れていることがわかります。