ビットラインサーチ

質問

以前、自分なりのアイディアでビットアレイサーチ(bitarraysearch)についても質問させて
いただきましたが、今回も同様な質問をさせていただきたいと思います。

Webサイトをいろいろ検索した結果、今回作成したサーチアルゴリズムが無さそうだなとは
思うのですが、「もし既にあるよ」というお言葉があれば、回答をよろしくお願いします。

今回作成したサーチアルゴリズムは、ランダムに作成した5000000文字の中から任意の文字列の
位置を検索するというものです。任意の文字列は10000文字まで対応しています。もちろんこれらは
ヘッダファイルの書き換えで変更することが出来ます。

最後にバグや改良点等ございましたら合わせてご回答頂ければ幸いです。

回答No.5

Tacosan

念の為突っ込んでおきますが, 「アルゴリズム」と「(そのアルゴリズムを実装した) プログラム」とは区別してください.

このプログラムは, アルゴリズム的には
int matching(const char *text, const char *pattern, int *match)
{
int i, j;
int index = 0;

for (i = 0; text[i] != '\0'; ++i) {
if (text[i] == pattern[0]) {
for (j = 1; text[i+j] != '\0' && pattern[j] != '\0'; ++j) {
if (text[i+j] != pattern[j]) {
break;
}
if (pattern[j] == '\0') {
match[index++] = i;
}
}
return index;
}

とほとんど同じです. 違いは, これの
text[i] == pattern[0] とか text[i+j] != pattern[j] とか ++i とか ++j とか
を, ビットマップを使ってより複雑怪奇にしている (結果として遅くなる) だけ.

回答No.4

Tacosan

ちなみにこのアルゴリズム, 「同じ文字がひたすらつづく」という場合に弱いので
・テキスト: a が 5000000文字
・検索パターン: a が 100文字
とかいういじわるなことをやると (本質ではない) 時間のかかりかたが明確になったりしますね.

ランダムって, 実はわりと「都合がいい」データだったりする....

回答No.3

kmee

その「速い」というのは、どうやって検証したのですか?あるいは「速い」ということの理論的な説明はできますか?

例えば、プログラムの一部を次のように変えて、実行速度を測ってみたらどうです?
少なくとも手許の環境では
bitline: 28.899 ms
strstr : 8.459 ms
と「標準ライブラリのstrstr」の圧勝でした。

//ビットラインサーチ
clock_t tt=clock();
bitlinesearch(bit, hex1,hex2,sc,piece);
clock_t t0=clock();

// strstr
const char * sc0 = searchchar ;
const char * sc1 ;
i = 0 ;
while( NULL != ( sc1 = strstr(sc0, sc) )) {
// piece0[i++] = sc1 - searchchar ;
sc0 = sc1 + strlen(sc) ;
}

clock_t t1=clock();

printf("bitline: %9.3f ms\n",1000.0 * (double)(t0-tt)/CLOCKS_PER_SEC);
printf("strstr : %9.3f ms\n",1000.0 * (double)(t1-t0)/CLOCKS_PER_SEC);

お礼

確かにstrstrのほうが圧倒的に早かったです。
（脱力）良いアルゴリズムができたと思ったのですが、全然だめでした。
精進します。

回答No.2

Tacosan

反応がないけど読んでくれたのかなぁ?

パッと見た感じ, 「ふつ～の文字列探索」の超絶劣化バージョンとしか思えません. 単純に書けるはずの処理を「より面倒なプログラムで」「より大量のメモリを用いて」「より長い時間をかけている」だけ.

回答No.1

Tacosan

とりあえずど～でもいい突っ込みですが「1バイトが 8ビットを越える環境でも大丈夫ですか?」とはいわせてもらいましょうか.

閑話休題.

例えば既存のアルゴリズムに比べて「ここがこんな風にうれしい」とかプレゼンをお願いします.

お礼

ホームページのほうにexeファイルをアップしましたので、
よろしければ、実行速度を体感してみてください。
最初にランダムな5000000文字分のデータを出力した後、
検索に入ります。ビットラインサーチはかなり速いと思います。
http://www.scn-net.ne.jp/~charlie/