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

###BM法とは

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

基本方針は、**パターンの末尾文字から先頭側へと照合を行う過程で不一致文字を見つけた場合に 
事前に用意した表に基づいてパターンの移動量を決定する**というものになります。

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

まずは、テキストとパターンの先頭文字を重ねた上で、パターンの末尾文字`C`に着目すると、
テキスト4文字目の`X`と不一致であることがわかります。
![スクリーンショット 2021-05-17 16.28.06.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/521565/cd5f4512-3f50-3394-1cff-c41a784be251.png)
そのままパターンをパターンを１~３文字ずつ移動しながら照合してみましょう。
![スクリーンショット 2021-05-17 16.31.55.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/521565/fcb4650f-80bc-6ac8-6528-dd1af48be475.png)
そのまま移動しても、文字`X`とパターン内の文字が一致しないことが分かります。

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

つまり、ここでは最初の比較後にパターンを一気に4文字（`X`の次まで）進めることができそうです。
次に、テキスト末尾の`C`とパターンと比較すると、パターン末尾の`C`が一致します。
![スクリーンショット 2021-05-17 16.38.10.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/521565/cb34cff1-0089-261d-fea4-78828f718488.png)
そこで、次の照合対象をテキストの`Z`とし、パターン内を１文字ずつ照合していきます。
![スクリーンショット 2021-05-17 16.40.00.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/521565/fae0cb4a-28c2-2f2e-e079-cb0a57e79e6e.png)
パターンの先頭まで`Z`と照合しましたが、一致するものはありませんでした。
しかし、最初の`C`とは一致していたので、`C`の部分まで3文字分パターンを移動してみます。
![スクリーンショット 2021-05-17 16.41.21.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/521565/aad7de30-0dde-cd93-e19c-511eded8074f.png)
テキスト側の末尾の`A`はパターンの末尾文字である`C`と一致しません 。
ところが、テキスト側の`A`はパターンの1文字目と2文字目の2箇所に存在しています。
 そこで、後ろ側の`A`が重なるように、パターンを1文字だけ移動してみましょう。
![スクリーンショット 2021-05-17 16.41.58.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/521565/956fb935-8e8c-a280-9947-e50e71e18fdb.png)
改めてパターンの末尾側から順にテキストと比較すると、全て一致してるので、ここで初めて探索に成功しました。

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

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

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

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

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

■ パターンに含まれない文字だったとき
先程の１巡目のように、テキスト側の`X`がパターンのどこにも存在しなかった場合、移動量はn文字となります。
![スクリーンショット 2021-05-17 16.28.06.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/521565/cd5f4512-3f50-3394-1cff-c41a784be251.png)
このような場合は、テキストの`D`から照合を始めたいので、そのままn文字分移動すれば良いということになります。

■ パターンに含まれる文字だったとき
テキスト側で最後に出現する位置のインデックスがkであれば、移動量は`n-k-1`となります。
例えば、以下のようにテキストの`A`に着目したとき、
パターン側には２つの`A`が存在しますが、最後に出現するインデックスは２番目の`A`なので、
`４-２-1`ということで１文字移動すれば良いということになります。
![スクリーンショット 2021-05-17 17.13.13.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/521565/d95420be-7675-db33-cd0c-bc21a48fdced.png)
含まれる文字がパターン内に１つしかなく、かつパターンの末尾文字だった場合の移動量はnとします。
![スクリーンショット 2021-05-17 17.17.01.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/521565/36f9a39e-6a04-f284-b79a-6b0fcbf54e9e.png)
このように`C`は一致していますが、パターン内に`C`は１文字しかなく末尾でもあるので、この場合はn文字分移動すれば良いということです。

`ABCXDEZCABACABAC`で`ABAC`であれば、パターンは4文字で
`A`であれば、パターン内に複数あり、最後のインデックスは2なので、`４-２-1`で１
`B`であれば、パターン内に一つしかなく、最後のインデックスは1なので、`４-１-1`で２
`C`であれば、パターン内に一つしかなく、パターンの末尾でもあるので、そのまま4となります。
これで、A-Zまでの一覧が完成しました。（実際はこれ以外の文字も含まれますがそれも同様に4となります）
![スクリーンショット 2021-05-17 17.19.20.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/521565/660da9e0-bdda-87dd-78be-d99fb625a5e1.png)

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


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

```java:BM.java
 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`

となります。結果的に下記のようなスキップテーブルを完成させることが出来ました。
![スクリーンショット 2021-05-17 17.19.20.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/521565/660da9e0-bdda-87dd-78be-d99fb625a5e1.png)

他にも`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`
となり、以下のような表を作成することができます。
![スクリーンショット 2021-05-17 19.13.35.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/521565/b83f0378-dac9-ca02-16ba-57e985ff5fed.png)

あとはこの表を元に探索を行えばいいので、
まずは、`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文を抜けます。
![スクリーンショット 2021-05-17 21.49.05.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/521565/a7a8a646-f48f-f40f-ec8c-1c4e27dab6c3.png)
スキップテーブルのXの値（4） > パターンの長さ（4）-ppの値（3）はtrueなので、
ここではスキップテーブルの値がptに足され、そのままターゲットのカーソルは４つ進み、ptは７となります

この時点で　ptはターゲットの長さは超えてないので、そのまま照合に移ります。
`while (target.charAt(７) == pat.charAt(３))`は　`C`と`C`で一致するも、ppは０ではないので、
ppとptをそれぞれデクリメントします。
![スクリーンショット 2021-05-17 21.59.34.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/521565/abb73a92-b41b-7995-9953-83419d7424e9.png)
`while (target.charAt(６) == pat.charAt(２))`は　`Z`と`A`で一致しないので、while文を抜けます。
![スクリーンショット 2021-05-17 22.05.28.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/521565/c69a109b-40c6-7ec6-0fac-127bc7f9f4b4.png)
スキップテーブルのZの値（4） > パターンの長さ（4）-ppの値（2）はtrueなので、
ここではスキップテーブルの値がptに足され、そのままターゲットのカーソルは４つ進み、ptは１０となります。

この時点でもptはターゲットの長さは超えてないので、そのまま照合に移ります。
`while (target.charAt(１０) == pat.charAt(３))`は　`A`と`C`で一致しないので、while文を抜けます。
![スクリーンショット 2021-05-17 22.03.56.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/521565/ee1164cc-415d-f1bb-ec10-4dc7cc661df8.png)
スキップテーブルの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が８として一致する文字列の最初のインデックスが返却されるという流れになります。
![スクリーンショット 2021-05-17 22.14.08.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/521565/9db00263-b2dd-3c5d-7bd2-3fc2d9c8a8ca.png)
このように、最初は文字列だけで説明していたものが、スキップテーブルを参照することによって
無駄な照合をせずに探索を行うBM法を実現させることができましたね！

###学んだこと

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

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