(文字列)BMアルゴリズム簡易版(改良できた)

今日のアルゴリズムはは、非常に難解だが、実用上もっとも優れた文字列照合アルゴリズムである。それはBoyer-Mooreアルゴリズムと呼ばれている。ここではBMアルゴリズムという。岩波のソフトウエア科学PP307にそのソースがPascalで記述されていますが。goto文を多用しているのであまりよい例とはいえない。そこでgoto文を無くすように改良してみた。他にも前回のKMPや前々回のシンプルな照合の大筋をできるだけ変えないようにし、見やすさ、扱いやすさを考えた部分は逆に改良を施し、試験をしやすくした。是非前回、前々回のソースを御覧になりながらじっくり読んでほしい。

概要
BMアルゴリズムはシンプルなアルゴリズム同様テキストを左から順に照合してゆくが、いったんテキストの位置が決まったら、パターンは右から調べてゆく。

比較回数を減らす方法は実は2つあり、今回は不一致となった点のテキストの文字によってパターンをずらす量を決める方法を取る。不一致が判明した点のテキスト側の文字がパターンの中に含まれているかどうか、あればどの位置にあるかによって何文字ずらすかが決定される。

改良点
(キーポイント1)
おもな改良点は第3ループ(内部ループ)の条件をpp307で用いられているif(text[i]=pattern[j])で始まるif文をループの条件としてループを回しています。
(キーポイント2)
前回まで定義していた文字列の長さを今回はstring.h内のstrlenを用います。この関数は少々危険を孕んでおり、文字列のターミネータ(null文字)までの長さをはかるため、ターミネータを設定していない場合の利用は絶対避けましょう。
(キーポイント3)
今回下準備としてskipをする量を前もって計算しています。それがmkskip関数です。これの1番目のループはキャラクターコードの大きさです。符号つきchar型を利用しているので文字の種類は128種類。符号なしの場合、256にせっていします。

ソースコードは以下の様になる

#include
#include
#include

char text="abcdacbdbdbddadabd";
char pattern="dad";
int skip[127];
void mkskip(void)
{
int i,m,j;
m=strlen(pattern);//キーポイント2
for(i=0;i<128;i++)//キーポイント3
skip[i]=m;
for(j=0;j0)//patternが左に行くまで
{
while(text[i]==pattern[j])//textが一致したら(キーポイント1)
{
if(j==0)//patternが左端にたどり着いたら
{
printf("探している文字列は%d番目から\n",i+1);//textのi+1番目ですよ
return 0;
}
--i;//textの照準を左に
--j;//patternの照準を左に
}
if(skip[i]>plen-j)//skipの左側からpatternの照準までの幅がskip幅より小さい
i+=skip[text[i]];
else
i+=plen-j+1;
}
}
printf("no matched\n");
return 0;
}

実行結果

テキスト：abcdacbdbdbddadabd
パターン：dad
探している文字列は13番目から

テキスト：ababacbababddadabd
パターン：ababd
探している文字列は8番目から
テキスト：ababacbababddadabd
パターン：abebd
セグメントエラー (coreを出力しました)

え?また改良??もういいっしょ(￣□￣；)

次回改良できたら載せます。さらにもうひとつの高速化をはかります。

と言っていましたが一眠りしたら構造がなんとなく察しがついて完璧に理解した感じ。
改良版

#include
#include
#include

char text="ababacbababddadabd";
char pattern="abdd";
int skip[256];
void mkskip(void)
{
int i,m;
m=strlen(pattern);
for(i=0;i<256;i++)
skip[i]=m;
for(i=0;iplen-j)
i+=skip[text[i]&0xff];//skipの左側からpatternの照準までの幅がskip幅より小さい
else
i+=plen-j;
}
printf("no matched\n");
return 0;
}

改良点
unsigned charにした。途中出てくる0xffのand演算は配列の添字表現で文字を使うときに使用する演算で構造上のもの。一個while文をなくしif文でループの脱出を図るように補った
if(j==0)//patternが左端にたどり着いたら
{
printf("探している文字列は%d番目から\n",i+1);
return 0;
}
の部分。
実行結果

テキスト：ababacbababddadabd
パターン：abdd
探している文字列は10番目から

テキスト：ababacbababddadabd
パターン：aeb
no matched

テキスト：ababacbababddadabd
パターン：abdc
no matched