HorspoolのアルゴリズムとSunday's Quick Search
BM法についての記事を書いたとたんに、
「最速の文字列検索アルゴリズムってなんだ？」
と思って調べまくった次第です（；＾ω＾）。この無駄な凝り性はプラスにもマイナスにも働きそうで怖い。
そしたらBM法の亜種がいくつか研究されてるみたいですね。
んで、この亜種についての一般的な話を。
（あ、BM法の記事：http://d.hatena.ne.jp/g940425/20100522/1274520718 を見てない人はわかりにくいかもです（；´・ω・`））
Boyer-Mooreのアルゴリズムの要は、「テキストのどの文字で不一致が起こったか」によって一気に先へ先へとジャンプしていくところだったわけだ。
上のテキストから下のパターンを検索するとき、
BM法では、パターンの後ろから見ていって、
初めて不一致となったこの位置に
パターン中の同じ文字を合わせることでパターンの位置を何文字か（例では二文字）ジャンプさせる。
まあ、細かいとこは置いといてこんな感じだった。
でも、よく考えれば、この「パターン中の同じ文字を合わせる位置（関数を適用する位置）」は、別に「不一致が起きたその位置」じゃなくてもいいということに気づく。
つまり、下の図の青い四角の中の"d"に着目して、
ここまで一気に飛ばすことができるじゃないか、
ということ。
つまり、やりたいことは「完全に一致する可能性がない場所は省く」ということだったんだから、この末尾の"d"とパターン中の何らかの文字が一致していないような移動の仕方は考えるだけ無駄だということです。そこでこの"d"が一致してないような移動の仕方を全部無視してポインタをすすめる。
この考え方を用いて高速化したのが「Horspoolのアルゴリズム」。
ソースは以下。
無駄を省いたりはしてないんで、無駄な処理があるかも。
java Hoospool "パターン" "テキスト"
で文字位置を出力。
このソース毎回見づらいですねえ……そのうち改善します。
class Horspool{
String pat=null;
//パターンのサイズ
int size=0;
//φテーブル：ジャンプテーブル
//「照合に失敗した時に末尾の文字が指している文字」の関数
int phi[] = new int[26];
Horspool(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)-'a';
if(pro < 0 || pro > 25)index+=size;
else index+=phi[pro];
}
}
else {
pro = (int)str.charAt(index)-'a';
if(pro < 0 || pro > 25)index+=size;
else index+=phi[pro];
}
}
return -1;
}
public static void main(String args[]){
Horspool x = new Horspool(args[0]);
System.out.println(x.match(args[1]));
}
}
さて。
末尾で比較することによって、
関数を適用する位置を前に持ってくることになり、
必然的にジャンプできる文字数を増やすことができます。
しかも、常にこの位置で比較し、この位置でジャンプするので、前回簡易型BMアルゴリズムで考えたような「検索位置の逆戻り」も心配無用です。
BM法の亜種は、このようにジャンプの仕方を変えたものであり、
特に一文字の比較を以てしてジャンプを行うときは、その「位置」が前にあるほど、ジャンプによって進める文字数が増えていく。
そう考えると、このアルゴリズムは、パターンの「末尾」であることから、
これ以上同類のアルゴリズムでは速くならないような気がします。
が、よくよく考えれば、
そもそもパターンは少なくとも一つは前に進むわけですから、
一つ進んだ先、すなわち
の位置に注目すると、この位置で文字が一致しないような移動の仕方は無意味です。
しかし、この位置で文字が一致する可能性もあります。
つまり、何が言いたいかというと、不一致が起こったとき、
この「一つ進んだ位置」の文字を見て、そこに一致するような移動のさせ方を考える、つまりこの位置の文字をみて関数を適用することで、パターンを見逃さず、かつ末尾で関数を用いるHorspoolのアルゴリズムより高速なアルゴリズムになります。
例でいうと、さっきの
から、一気に
まで進めることができ、なんとこの方法だと一回のジャンプでテキスト検索を終えます。
（例だと、「一致なし」を返すことになる。）
（１２／１６訂正：間違いです：そのひとつ前の"b"で止まります。申し訳ありません！この例だとジャンプ二回で探索を終えます。）
これをクイックサーチ(Sundayのアルゴリズム)といいます。（厳密には、出現頻度の低い文字から一致・不一致を調べる、BM法の第二ストラテジによる関数も用いる等の違いはあるが、ここでは割愛します）
そして、これ以上先で比べてしまうと、末尾から一つだけ進んで一致する可能性を無視してしまうことになるので、それはできません。
つまり、この「パターンの末尾の一つ先」というのは、BM法と同種の方法で比べるときの最良の方法だということになります。
Javaで書いたソースを。
φ関数が従来のプログラムより１大きいことに注意。
末尾からの移動量ではなく「末尾の一つ先からの移動量」なのです。
class Quicksearch{
String pat=null;
//パターンのサイズ
int size=0;
//φテーブル：ジャンプテーブル
//「照合に失敗した時に末尾の一つ先の位置にあるテキストの文字」の関数
int phi[] = new int[26];
Quicksearch(String pattern){
pat = pattern;
size = pat.length();
//φテーブル生成
for(int i=0;i<26;i++){
phi[i] = size+1;
}
for(int i=0;i<size;i++){
phi[(int)(pat.charAt(i))-'a'] = size-i;
}
}
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{
if(index==s_size-1)return -1;
pro = (int)str.charAt(index+1)-'a';
if(pro < 0 || pro > 25)index+=size;
else index+=phi[pro];
}
}
else {
if(index==s_size-1)return -1;
pro = (int)str.charAt(index+1)-'a';
if(pro < 0 || pro > 25)index+=size;
else index+=phi[pro];
}
}
return -1;
}
public static void main(String args[]){
Quicksearch x = new Quicksearch(args[0]);
System.out.println(x.match(args[1]));
}
}
java Quicksearch "パターン" "テキスト"
で検索。
ふう、以上で文字列検索については、
BM法の亜種中最速のアルゴリズムを提示したところで一旦終わり。
最近割と書くネタがあるので、ガンガン更新するよ！（`・ω・´）
(５／２７追記：ソースの誤りがありましたので訂正しました。φ関数の作成のforループの繰り返し条件はi<sizeでした。)
