「高速検索アルゴリズム」について、基本的なことがわかるサイトを教えてください。

また、有名な技術や最先端の技術があれば、紹介してください。

回答の条件
  • 1人2回まで
  • 登録:2006/06/01 22:28:06
  • 終了:2006/06/08 22:30:05

回答(2件)

id:aiaina No.1

aiaina回答回数8179ベストアンサー獲得回数1312006/06/01 22:59:58

id:testnoda

参考になりました。ありがとうございます。

考えてみれば、ハッシュ・ジョインやビットマップ索引も、検索アルゴリズムの一つですよね。

関係ないですが、データウェアハウスってDWHでなくDSSと略すことがあるんでしょうか?初めて知りました。

2006/06/01 23:43:20
id:znz No.2

znz回答回数193ベストアンサー獲得回数252006/06/02 02:37:45

ポイント35pt

http://www2.starcat.ne.jp/~fussy/algo/index.htm

の「検索・探索ルーチン」のところはどうでしょうか?

KMP法やBM法は有名だと思います。

正規表現のアルゴリズムについて詳しいことはWeb上ではなかなかなさそうなので、書籍になってしまいますが、 詳説 正規表現 第2版 をみるのが良さそうです。

正規表現のアルゴリズムは

http://dev.ariel-networks.com/articles/workshop/regex

で少しわかりますが、DFAやNFAという理論になります。


検索のアルゴリズムではありませんが、インデックスを作成してから検索するものの場合、形態素解析で文字列を分解したり、N-gramで部分文字列にしたりしていることが多いです。

id:testnoda

線形探索、ハッシュ法、2分検索、木検索は、例えば情報処理試験の参考書に載っているので名前だけは知ってましたが、内容の理解は曖昧でした。

また、検索アルゴリズムというキーワードから、これらの概念を再確認できたのがよかったです。

KMP法やBM法については、単純な文字列照合の説明があった上で、その改良という形で説明を進めてあるのがよいと思います。

正規表現の部分は、図表が一部欠落しているものの、オートマトンを使用するのは基本的な考え方なんだということに気づけたのが有り難かったです。

DFA、NFA、形態素解析やN-gramというキーワードを紹介して頂いたのも参考になりました。

ありがとうございました。

2006/06/02 12:00:20
  • id:testnoda
    この質問を出したのは、SIGMAエンジンについて調べる用事があったためでした。
    SIGMAエンジンを使用したデータベースエンジンとして、富士通が「Shunsaku」という製品を発表しているようです。
    http://ldm-rg.com/public/3-4ab.pdf

    このアルゴリズムでは、オートマトンを並列で動かすことで、検索条件が何件あっても安定して検索できる、ということのようです。本当なんでしょうか…。
    下記のページを見ると、インデックスが無くても高速検索できるとか書いてあるし…。
    http://www.infoteria.com/jp/product/asteria/solution/shunsaku/

    とにかく自分としては、オートマトンを使うのは検索アルゴリズムでは特殊なことではなさそうだとわかっただけで満足でした。

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません