文字列検索のアルゴリズム

KMP法とBM法

ここからは、実際の様々なアルゴリズムを通して、計算量の観点から、それぞれのアルゴリズムの有用性について検討していくことにします。第一弾としてとりあげるのが、文字列検索のアルゴリズムです。

このアルゴリズムは、インターネットの普及と、googleなどの検索エンジンの普及により、現在用いられているもっとも重要なアルゴリズムの一つであるといえるでしょう。文字列検索のアルゴリズムには、KMP法と呼ばれるものと、BM法と呼ばれるものがあります。今回は、まずKMP法について説明します。

文字列検索

KMP法のアルゴリズムの詳細について説明する前に、そもそも文字列検索とはどういうものか、ということについて説明します。文字列検索とは、ある文章の中に、指定した文字列が存在するかどうかを検索することを指します。たとえば、ある本の中から、birdという文字列を検索するということは、その本の文字を頭から解析していき、b,i,r,dという文字のならびを探すことにほかなりません。

この時、探し出したい文字列のことを、パターン(pattern)、パターンを探索する対象となる文章のことを、テキスト(text)と呼びます。（図2-1.）つまり、文字列を探索するということは、「テキストの中にある、指定されたパターンが出現する場所を見つけ出す」ことだということになります。

図2-1.テキストとパターン
テキストとパターン

力まかせのアルゴリズム

力まかせのアルゴリズムとその計算量

このようなパターンマッチングのアルゴリズムのうち、もっとも単純なものは、以下のような手順での探索でしょう。(図2-2.)

  1. テキストの先頭から、パターンと同じ長さの文字列を取得し、一致するかどうかを調べる
  2. 一致しなければ、一文字次から同じ長さの文字列を取得し、一致するかどうかを調べる
  3. 以上の処理を一致するまで繰り返す
図2-2.力まかせのアルゴリズム
力まかせのアルゴリズム

このような単純な検索方法のことを、力まかせのアルゴリズム（brute-force algorithm）と呼ばれます。では、こういった力まかせのアルゴリズムの計算量は、どれくらいになるのでしょうか？結論から先に言うと、テキストの長さをn文字、パターンの長さをm文字とすると、O(nm)というオーダーになります。

KMP法

KMP法とは

力まかせのアルゴリズムよりも若干洗練されたアルゴリズムが、KMP法です。これは、KMPとは、Knuth-Morris-Prattの略で、作成者の3人の名前に由来するものです。

KMP法では、パターンに含まれる各文字について、その文字で不一致になったときにパターンをどれだけずらせばよいかを記憶しておき、その情報を基にしてパターンをずらしていくアルゴリズムです。ではいったい、KMP法とはどのようなアルゴリズムなのでしょうか。実例を参考にして、見てみましょう。

今、テキストの中から、sunsurfというパターンを検索するものと仮定します。その時、KMP法では、以下の手順で検索を行います。

(1) 1文字目で失敗した場合
力まかせ法同様、テキストの読み出し位置を1文字ずらし、パターンを一つずらして、再びパターンの先頭から比較します。(図2-3.)

図2-3.1文字目で失敗した場合
1文字目で失敗した場合

(2) 2文字目で失敗した場合
(1)の場合と同じです。力まかせ法同様、テキストの読み出し位置を1文字ずらし、パターンを一つずらして、再びパターンの先頭から比較します。(図2-4.)

図2-4.2文字目で失敗した場合
2文字目で失敗した場合

(3) 3文字目で失敗した場合
ここから、力まかせ法との違いが出てきます。sunsurfという単語は、1文字目が「s」、2文字目が「u」であり、明らかに違う文字です。この場合、1文字ずらしても、一致しないことはすでに明らかです。そこで、こういった場合は、パターンを2つ図らして、まだ比較を行っていないところから改めて比較を始めるのです。(図2-5.)

図2-5.3文字目で失敗した場合
3文字目で失敗した場合

(4) 4文字目で失敗した場合
これも、(3)のケースと一緒です。最初の三文字は、「s」、「u」、「n」と、明らかに違うので、パターンを3つずらして検索していきます。(図2-6.)

図2-6.4文字目で失敗した場合
4文字目で失敗した場合

(5) 5文字目で失敗した場合
この場合のケースは、今までのものと異なるケースです。このパターンは、1文字目と4文字目が、ともに「s」です。したがって、この場合は、もしかしたら5文字目から一致するかもしれません。そこで、パターンを3つずらして、「s」の次の2文字目から比較を続けます。(図2-7.)

図2-7.5文字目で失敗した場合
5文字目で失敗した場合

(6) 6文字目で失敗した場合
このパターンは、1文字目と4文字目がともに「s」、2文字目と5文字目がともに「u」であり、したがって、この場合は、もしかしたら6文字目から一致するかもしれません。そこで、パターンを3つずらして、「su」の次の3文字目から比較を続けます。(図2-7.)

図2-8.6文字目で失敗した場合
5文字目で失敗した場合

7文字目については、(1)～(3)のケースと同じなので省略します。

KMP法の特徴

KMP法の計算量

KMP法の計算量は、最悪の場合でも、O(n)になります。つまり、力まかせ法よりも効率の良いアルゴリズムであることがわかります。これは、KMP法が、決して力まかせとは違い、後戻りしないことに由来します。

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

KMP法の問題点とBM法

また、KMP法自体も、このようにパターンの中に重複するケースがあればよいですが、そのような例はむしろ少数で、しかもアルゴリズムが若干複雑になっていることから、場合によっては力まかせ法のほうがすぐれている場合も多く、この方法を使用するメリットはあまりないといえます。

つまり、KMP法は、「理論的には優れているが、実践的ではない」アルゴリズムであると言えます。そんなKMP法よりも優れているのが、BM法なのです。