【Java アルゴリズム修行⑱】文字列探索 ~BM法~

BM法とは

このBoyer-Moore法というのは、理論的にも、実践的にもKMP法より優れていて、
実際の文字列探索でも広く利用されているものだそうです。

基本方針は、パターンの末尾文字から先頭側へと照合を行う過程で不一致文字を見つけた場合に

事前に用意した表に基づいてパターンの移動量を決定するというものになります。



テキストをABCXDEZCABACABAC、パターンをABACとしたときの流れを見てましょう。

まずは、テキストとパターンの先頭文字を重ねた上で、パターンの末尾文字Cに着目すると、
テキスト4文字目のXと不一致であることがわかります。

そのままパターンをパターンを１~３文字ずつ移動しながら照合してみましょう。

そのまま移動しても、文字Xとパターン内の文字が一致しないことが分かります。

このように、テキストとパターンを末尾から照合していく中で
パターンに含まれない文字をテキスト中に発見した場合、
そこまでの文字と一致する可能性はなくなるので、
着目した要素の次の要素からパターンとの照合を始めることができます。
ABSZXYOというテキストとABXを照合したときに、既にSとXは異なっているので、
それ以前が一致していたとしても、そこはスキップして、テキストのZから照合できるということですね！

つまり、ここでは最初の比較後にパターンを一気に4文字（Xの次まで）進めることができそうです。
次に、テキスト末尾のCとパターンと比較すると、パターン末尾のCが一致します。

そこで、次の照合対象をテキストのZとし、パターン内を１文字ずつ照合していきます。

パターンの先頭までZと照合しましたが、一致するものはありませんでした。
しかし、最初のCとは一致していたので、Cの部分まで3文字分パターンを移動してみます。

テキスト側の末尾のAはパターンの末尾文字であるCと一致しません
。
ところが、テキスト側のAはパターンの1文字目と2文字目の2箇所に存在しています。

そこで、後ろ側のAが重なるように、パターンを1文字だけ移動してみましょう。

改めてパターンの末尾側から順にテキストと比較すると、全て一致してるので、ここで初めて探索に成功しました。

パターンの長さがn文字だとすると、パターンに存在しない文字と出会った場合、
パターンをn文字移動するのではなく、
着目している文字の位置がn文字ズレるようにパターンを移動する点に注意します。

１巡目は1文字も一致しなかったので、5文字目であるDから着目したいので4文字分
２巡目では末尾Cのみ一致していたので、そのCから着目するために3文字分移動しています。

３巡目はテキスト側のAとパターン側のCが不一致なので、
パターン側を一個ズラしたところ、結果的に全てが一致したということですね。

流れは掴めましたが、このアルゴリズムを利用するには、
テキスト側で着目したそれぞれの値の移動量を格納した表を事前に作っておく必要があります。
（テキスト側の文字によって、パターン側を何文字ズラせば良いのかをまとめておく）

パターンをn文字としたときのそれぞれの移動量を考えてみましょう。

■ パターンに含まれない文字だったとき
先程の１巡目のように、テキスト側のXがパターンのどこにも存在しなかった場合、移動量はn文字となります。

このような場合は、テキストのDから照合を始めたいので、そのままn文字分移動すれば良いということになります。

■ パターンに含まれる文字だったとき
テキスト側で最後に出現する位置のインデックスがkであれば、移動量はn-k-1となります。
例えば、以下のようにテキストのAに着目したとき、
パターン側には２つのAが存在しますが、最後に出現するインデックスは２番目のAなので、
４-２-1ということで１文字移動すれば良いということになります。

含まれる文字がパターン内に１つしかなく、かつパターンの末尾文字だった場合の移動量はnとします。

このようにCは一致していますが、パターン内にCは１文字しかなく末尾でもあるので、この場合はn文字分移動すれば良いということです。

ABCXDEZCABACABACでABACであれば、パターンは4文字で
Aであれば、パターン内に複数あり、最後のインデックスは2なので、４-２-1で１
Bであれば、パターン内に一つしかなく、最後のインデックスは1なので、４-１-1で２
Cであれば、パターン内に一つしかなく、パターンの末尾でもあるので、そのまま4となります。
これで、A-Zまでの一覧が完成しました。（実際はこれ以外の文字も含まれますがそれも同様に4となります）

この表を元に、あとは探索を繰り返していけば良さそうなので、このままコードに落とし込んでみます！

コードに落とし込んでみる

 static int bmMatch(String target, String pat) {
    int pt;                             // テキストをなぞるカーソル
    int pp;                             // パターンをなぞるカーソル
    int txtLen = target.length();       // テキストの文字数
    int patLen = pat.length();          // パターンの文字数
    int[] skip = new int[Character.MAX_VALUE + 1];  // スキップテーブル

    // スキップテーブルの作成
    for (pt = 0; pt <= Character.MAX_VALUE; pt++) {
      skip[pt] = patLen;
      }
    for (pt = 0; pt < patLen - 1; pt++) {
      skip[pat.charAt(pt)] = patLen - pt - 1;
      }                             // pt == patLen - 1である

    // 探索
    while (pt < txtLen) {
      pp = patLen - 1;              // パターンの末尾文字に着目

      while (target.charAt(pt) == pat.charAt(pp)) {
        if (pp == 0) {
          return pt;                // 探索成功
          }   
        pp--;
        pt--;
      }
      pt += (skip[target.charAt(pt)] > patLen - pp) ? skip[target.charAt(pt)] : patLen - pp;
    }
    return -1;                      // 探索失敗
  }

ターゲットをなぞるカーソルと、パターンをなぞるカーソルをそれぞれ持たせ、
それぞれの文字数もローカル変数として持たせています。



skipする文字数の表であるスキップテーブルは、
文字列として成立する全ての文字をの移動量を計算しなければならないので、

スキップテーブルを構成する配列の要素数は、char型で表現できる文字数　+ 1 としています。（厳密には65536個です）

そのスキップテーブルの初期値はskip[pt] = patLen;としてまずは統一します。
その後、パターンの末尾要素を除いた全ての文字をスキップ数をそれぞれ格納していきます。

例えば、パターンがABACであれば、
for (pt = 0; pt < ４ - 1; pt++)となるので、
skip[pat.charAt(0)](A) = 4-0-1となります
char型のAも暗黙のint型への変換が行われ6５となりスキップテーブルのAに３という値が格納されます
その後、ptがインクリメントされ繰り返すと
skip[pat.charAt(0)](B) = 4-１-1　
skip[pat.charAt(0)](A) = 4-２-1

となります。結果的に下記のようなスキップテーブルを完成させることが出来ました。

他にもABCABCと末尾文字も含めて全ての文字が繰り返されている場合も、、
skip[pat.charAt(0)](A) = ６-0-1
skip[pat.charAt(0)](B) = ６-１-1
skip[pat.charAt(0)](C) = ６-２-1
skip[pat.charAt(0)](A) = ６-３-1
skip[pat.charAt(0)](B) = ６-４-1
となり、以下のような表を作成することができます。

あとはこの表を元に探索を行えばいいので、
まずは、pp = patLen - 1;としてパターンのカーソルを末尾に移動します。
その後、while (target.charAt(pt) == pat.charAt(pp))として、
パターンとテキストが一致している限り繰り返し処理を行い、もしppが０の場合は、
パターンの先頭まで照合が終わっているので、探索完了ということになります。

もし不一致であった場合は、改めてptのカーソルを移動していますが、下記の三項演算子を用いています。
pt += (skip[target.charAt(pt)] > patLen - pp) ? skip[target.charAt(pt)]: patLen - pp;
パターンと比較して、一致しなかった文字のスキップテーブルの値と、
パターンの文字数からパターンのカーソルを引いた数を比較して大きいほうをptに加えることで
スキップする要素数を導くことができます。

実際にABCXDEZCABACABACでABACというパターンから、スキップテーブル作成後の流れを見てみましょう。
while (pt < txtLen)は、ターゲットのカーソルがターゲットの長さを超えてしまった場合は、
そのまま探索終了として−１を返すようにしています。

まずスキップテーブルを作成した時点で、パターンの末尾インデックスまでptをインクリメントしたので、
ptは３から始まります　ppは末尾からなので、pp = patLen - 1;から、３となります。

while (target.charAt(３) == pat.charAt(３))は　XとCで一致しないので、while文を抜けます。

スキップテーブルのXの値（4） > パターンの長さ（4）-ppの値（3）はtrueなので、
ここではスキップテーブルの値がptに足され、そのままターゲットのカーソルは４つ進み、ptは７となります

この時点で　ptはターゲットの長さは超えてないので、そのまま照合に移ります。
while (target.charAt(７) == pat.charAt(３))は　CとCで一致するも、ppは０ではないので、
ppとptをそれぞれデクリメントします。

while (target.charAt(６) == pat.charAt(２))は　ZとAで一致しないので、while文を抜けます。

スキップテーブルのZの値（4） > パターンの長さ（4）-ppの値（2）はtrueなので、
ここではスキップテーブルの値がptに足され、そのままターゲットのカーソルは４つ進み、ptは１０となります。

この時点でもptはターゲットの長さは超えてないので、そのまま照合に移ります。
while (target.charAt(１０) == pat.charAt(３))は　AとCで一致しないので、while文を抜けます。

スキップテーブルのAの値（1） > パターンの長さ（4）-ppの値（3）はfalseなので。
ここではパターンの長さ-ppの値がptに足され、そのままターゲットのカーソルは１つ進み、ptは１１となります。

while (target.charAt(１１) == pat.charAt(３))はCとCで一致。
while (target.charAt(１０) == pat.charAt(２))はAとAで一致。
while (target.charAt(９) == pat.charAt(１))はBとBで一致。
while (target.charAt(８) == pat.charAt(０))はAとAで一致。
ここで、 (pp == 0)なので、そのままptが８として一致する文字列の最初のインデックスが返却されるという流れになります。

このように、最初は文字列だけで説明していたものが、スキップテーブルを参照することによって
無駄な照合をせずに探索を行うBM法を実現させることができましたね！

学んだこと

• パターンの中の文字列が最後に一致した場合に、次はどこから探索を再開するかを表としてまとめることで、無駄な探索を減らすことができる。
• 末尾だけであれば、パターンの文字数分、それ以外はパターン内で最後に出てくるインデックスを参考に表を作成する

最初に見た時は、また複雑な感じだな。。と思いましたが、パターンの文字を基準に、
もしテキストと一致しなかった場合でも、その文字がパターンに含まれていれば無駄な探索をしなくて済み、
そのための表を作成して、必要に応じてスキップしていくというのはかなり合理的ですし、
先頭から照合して、パターン内の同一文字まですっ飛ばすKMP法よりも
より実践的な感じというのが分かった気がします。。！引き続き頑張っていきます！