文字列の探索アルゴリズムについて

松井勝正といいます。自分なりのアイディアで文字列の探索アルゴリズム
を作成したのですが。質問が2点程あります。

1点目：既に世に出回っているアルゴリズムかご教授願えれば幸いです。
2点目：改良の余地やバグ等ございましたらご指摘いただければ幸いです。

それではよろしくお願いいたします。

No.1 回答者： kmee 回答日時： 2011/04/06 20:22

> 1点目：既に世に出回っているアルゴリズムかご教授願えれば幸いです。

「文字列探索」で検索すれば、沢山見つかるし、
ウィキペディアにも複数載ってるし
http://ja.wikipedia.org/wiki/%E6%96%87%E5%AD%97% …
↑にある「外部リンク」にはJavaのサンプル付きで更に多くのアルゴリズムが紹介されている。
http://www-igm.univ-mlv.fr/~lecroq/string/

これくらいのことだったら、まずは人に聞く前に自分で調べましょうよ。

> 2点目：改良の余地やバグ等ございましたらご指摘いただければ幸いです。

ソースをざっと眺めただけでは、何をしようとしているかわかりませんでした。詳しく解析するつもりになれません。
どんなところが既存の方法より優れているか、説明できますか?

mallocがやたらとあって、ポインタのポインタのポインタなんてものがあって....
と、下手すれば単純な探索より時間がかかりそうな気さえします。

この回答への補足

　さて、基本的な部分の説明をさせて頂きましたが、もう少し踏み込んだ説明をさせていただきます。縦軸の一文字分のデータの作成方法ですが、16で割った値と16で割った余りの値をそれぞれ用意します。少し説明が難しいのですが、多重ポインタの要素数16（一番右端）のポインタ配列部分に割った値と余りの値をそれぞれ格納します。これにより16×16=256（0xFF）のデータが作成されます。つまり一文字分のデータです。
　ここで、2次元配列を思い描いてもらいたいのですが、 int bit[a][b]はa行b列の配列となります。これが3次元になっても4次元になっても列は必ず存在します。つまり一番右端の配列です。
先ほどのポインタ配列に話を戻しますが、一文字分のデータは一番右端のポインタ配列に格納されています。先ほど演算した値は、ポインタ配列の0～15のうちどこかに必ず格納されます。説明をさらに進めます。ソースを確認してもらえれば有難いのですが、bit[0][i][s－>indexbit][spot[0]]|=bitcalとbit[1][i][s－>indexbit][spot[1]]|=bitcalが記述されていると思いますが、この一番左端のポインタ配列の[0]と[1]に着目します。これが縦軸のビット列を表す重要な部分になります。省略して記述しますが、bit[0][][][spot[0]]が16で割った値の多重ポインタ配列、bit[1][][][spot[1]]が16で割った余りの値の多重ポインタ配列を表します。
　つまり、一文字を縦軸のビット列に分解することにより横軸のビット列1ビット分で一文字を表現できるようにしたのです。
　説明が長くなりましたので、ここで一旦切り上げさせていただきます。残りはまた次回説明させていただきたいと思います。長文大変失礼いたしました。

補足日時：2011/04/09 13:11

この回答へのお礼

　早速のご回答ありがとうございます。こんなに早く回答を頂けるとはうれしい限りです。
自分で調べるという点につきましては、危言のお言葉有難く拝読させていただきました。
拙い文章ではございますが、ソースについて説明させていただきます。
まず、mallocやポインタのポインタを多用した件につきましては、ヒープ領域の確保という点からでございます。
　次に、このアルゴリズムの特徴として申し上げたいのはint型32ビットのビット列を出来る限り有効利用したいという考えに基づいたものです。その為のアイディアとして、多重層のビット平面という考えに至りました。
　この多重層のビット平面を簡単に説明いたします。通常ビット列は、インターネットや書籍などの説明にありますように横一直線に型宣言文だけビット長が図に示されているものを良く見かけます。
このビット列を縦にも拡張したらどうなるかと思い多重ポインタを利用し縦×横の平面を作成いたしました。つまり、縦軸が一文字分のデータ、横軸が文字数というものです。当然int型なので32ビット、つまり32文字しか扱えません、そこで多重層という考え方を取り入れ32文字以上の文字列も扱えるようにいたしました。
　分かりにくい説明で誠に恐縮ではございますが、基本的な部分の説明とさせていただきます。長文大変失礼いたしました。

お礼日時：2011/04/07 21:18