Boyer-Moore法

文字列検索アルゴリズム第二弾。
「最速」といわれたBoyer-Moore法(ボイヤー・ムーア法)です。
（今はもっと速いのがあるけど）

二つの関数を使って検索スピードをあげるという方法なのですが、結局どんな文献を見ても「標準的なテキストなら、一方のみを用いたほうが速い」とのこと。
（そもそも「標準的なテキスト」って何なのかという問題はありますが）

なので今回は一方の関数のみ実装して、余力があればもう一方を実装して時間比較でもしようかなあと思います。

以下アルゴリズムの解説。今回GIMPで作った概念図を試験的に運用。

前回と同じく例で説明。上のTextからPatternを検索します。

まあ、文字列の検索なんで、例によってTextを前から順番に見ていくわけです。
説明上、この「見ている位置」を「ポインタ(Pointer)」と呼ぶことにします。
（通常プログラムで使うポインタとは違います。）

このBM法がいきなりほかのアルゴリズムと違うのは
ポインタの最初の位置。

と、このようにパターンの末尾にポインタを置き、末尾と一致している所をまず探すわけです普通は最初の文字を見るもんですが。

今回は、いきなり"a"と"d"なんで一致しません。
末尾が一致しなかったら、その位置にパターンの中の最も右よりにある同じ文字を合わせます。（同じ文字がなかったらパターンの長さ分だけ一気に移動させます。）そうすれば、次に一致する可能性がある場所まで一気に移動できます。

このように移動させると、最大で文字の長さ分（上の例なら９文字！）移動させられるので、実に効率的です。この「何文字移動させるか」の関数は割と簡単にできます。末尾から何文字目か数えればいいんだから。
この先の説明で必要なので、この関数をφ(文字)とします。つまり上の例では、φ(a)=3　文字分移動させたわけです。

で、例ではこのとき末尾が一致したわけですが、
末尾が一致したら、今テキストを見ているポインタとは別のポインタを使い、末尾から先頭に向かって一致しているかを検索させます

このアルゴリズムの特に特殊な部分はここで、テキストを見ていく方向と照合する向きが真逆なんですよ。ここが、前回のKMP法と全く違う部分で、KMP法では、ポインタを移動させると同時に照合を行っており、ポインタ自体を一気に進めることはできなかったんですが、このようにテキストを見ていくポインタと照合するポインタを別にし、テキストを読んでいくポインタを文字通り一気に進める仕組みを取り入れて高速化したのがBoyer-Moore法というわけです。

話を戻して。
上の図の次の比較"e"と"b"でまた不一致です。
末尾以外で不一致が起きた時は、第二のポインタをφ(文字)右に移動させ、その位置に第一のポインタを持ってきます。このように。

すると、計算してみるとわかりますが、一部特殊な場合を除いて、不一致した文字と、パターン中の最も右よりにある同じ文字が重なって一致します。上の例では赤い位置で"e"が一致しましたね。（「一部特殊な場合」でも、パターンを見逃すことはないのでとりあえず安全です）

ちなみに、例の検索は次にφ(a)=3文字進んで終了します。

概要はこんな感じなんですが、まだ一つだけ注意することがあります。
例をこうした場合。

前回使った例ですね。今回のとは微妙に違う。
なんで微妙に変えたかというと、今から説明する「問題」が生じるからです。
ここで。

そう、つまり不一致が起こる場所と位置によっては、第一ポインタが戻ってしまうのですよ。戻ると悪くすれば無限ループにハマります。

これは、「BM法の簡易版」だからこそ起こる問題で、完全Boyer-Mooreアルゴリズムなら防げるのですが、簡易版でこれを防ぐためには「ポインタが戻ってしまうようなら、第二ポインタの位置ではなく、今ある位置から一つだけ進める」とすればいいです。

以上でアルゴリズムの説明は終わり。
図を使うと楽だ……。今後も多分これで行く（・ω・）♪

以下、Javaで書いたBM法のソース。
ちなみに、テキストは半角のみで、パターンはアルファベットのみ探索ができます。
(５／２７追記：ソースの誤りがありましたので訂正しました。φ関数の作成のforループの繰り返し条件はi<sizeでした。)

class bm{

	//検索パターン

	String pat=null;

	//パターンのサイズ

	int size=0;

	//φテーブル：ジャンプテーブル(1)

	//「照合に失敗した時にカーソルが指している文字」の関数

	int phi[] = new int[26];
	bm(String pattern){

		pat = pattern;

		size = pat.length();

		

		//φテーブル生成

		for(int i=0;i<26;i++){

			phi[i] = size;

		}

		for(int i=0;i<=size;i++){

			phi[(int)(pat.charAt(i))-'a'] = size-i-1;

		}

	}

	

	public int match(String str){

		int index = size-1;

		int k=1;

		int s_size=str.length();

		int pro=0;

		if(size>s_size)return -1;

		while(index<s_size){

			//末尾の文字と照合する

			if(str.charAt(index)==pat.charAt(size-1)){

				//末尾から逆に順次照合していく

				while(k<size && str.charAt(index-k)==pat.charAt(size-k-1))k++;

				//一致したらindex-size+1を返す

				if(k==size)return index-size+1;

				//照合失敗したらカーソルをシフト

				else{

					pro = (int)str.charAt(index-k)-'a';

					if(pro < 0 || pro > 25)index+=size;

					else if(phi[pro]>k)index+=phi[pro]+k;

					else index++;

				}

			}

			else {

				pro = (int)str.charAt(index)-'a';

					if(pro < 0 || pro > 25)index+=size;

					else index+=phi[pro];

				}

		}

		return -1;

	}

	

	public String toString(){

		String str="";

		for(int i=0;i<26;i++){

			str += (char)('a'+i) + ":" + phi[i] + ",";

			if(i==12)str += "\n";

		}

		str += "\b";

		return str;

	}

}
class bmDemo{

	public static void main(String args[]){

		bm x = new bm(args[0]);

		System.out.println(x.match(args[1]));

	}

}