検索アルゴリズム

質問

今、高速な検索アルゴリズムを探しています。
　下記の条件のときに使えるアルゴリズムが何かないか、ご存知の方おしえてください。

　　１．データの順番は基本的にバラバラ
　　２．トゥリーやインデックスは検索の直前に作る

　よろしくお願いします。

回答No.7

alfeim · ベストアンサー

>Perl からＳＱＬが呼べないかなぁと
>PasageSQLやMySQLだと一般プロバイダのＣＧＩ環境では使えないから

SQL自体はそれぞれのモジュールがあると思います
(少なくともPostgresはPg.pmがあります)
一般プロバイダでは使えませんが、海外などのFreeWebサービスではMySQLやPostgresを遣わせてくれる所もありますよ
また、DataBaseは通常Networkアクセスできるように作ってあるので設定まで出来る所であれば、webサーバ(Perlプログラムが動いてる所ですね)とDBサーバは別々に出来ます
またODBCドライバモジュールがあれば大体のDetabaseは使えるはずです(多分探せばODBC用perl moduleがあると思います・・・自信無いですが(^^;)

SQL Serverの内部解説書ですが、私が読んだのは
出版社: リックテレコム
書名: リファレンス WindowsNTによるSQL Server6.5チューニングガイド
著者: 飛鳥 亮
定価: 2800円(税別)
ISBN: 4-89797-211-6
です
ちょっと古い本ですが、まだ手に入るようです＞参考URLを参照してください

>オープンソースのデータベースソフトがあるのなら、それもご紹介いただきたいんですが……(^_^;
オープンソースのデータベースソフトはPostgreSQLやMySQLがそうですよ(^^;
PostgreSQLは
http://www.sra.co.jp/people/t-ishii/PostgreSQL/
からダウンロードできるはずです

MySQLはこちら
http://www.softagency.co.jp/mysql/

参考URL：

http://www.amazon.co.jp/exec/obidos/ASIN/4897972116/qid%3D983533864/249-2995887-0212321

お礼

ありがとうございます。

　まあ、「手軽に使える」ことを売りにしてますからね。少なくともそれだけは誰にも負けないはずです(笑)

　解説書は、財布と相談したうえで、ヒモが緩んでくれれば買いたいと思います(笑)
　ＵＲＬの方はさっそくソースを落としに行きたいと思います。

回答No.6

alfeim

なんかDatabaseのようなものを作ろうとしてらっしゃるみたいですね・・・
であれば一番手っ取り早いのはDatabaseに突っ込んでSQLでQueryするってのが一番早いですが(笑)

結局自分で実装するにしてもDBと同じ手法を使う事になるでしょう
データを一意に識別出来るindexを付けてやり
それぞれの項目毎にB木やバランスツリー、ハッシュなどで一意識別できるindexとキーを関連付けてやります
それで検索条件毎にそれぞれの項目毎のツリーなどからindexを限定してやって、最後にindexから実体を出力してやる、という方法が使えると思います

また、検索条件の最適化を行うと言う事も(条件によっては)出来るでしょう

・・・以上の事は実際のdatabaseがやってる事です(^^;
MS SQL Serverなどの内部動作解説本などがあるのでそういう物を読むか、OpenSourceなDatabaseのSourceCodeを調べるのもいいかもしれません

お礼

そぉです(^_^;　Perl からＳＱＬが呼べないかなぁと思って、今作ってるんです(笑)（←PasageSQLやMySQLだと一般プロバイダのＣＧＩ環境では使えないから、といったようなコンセプト）
　つっても、ver.1 はすでにヴェクターに登録申請しましたけど。

　MS SQL Server の解説書はめちゃくちゃ欲しいです(笑)　本屋にありますか？
　オープンソースのデータベースソフトがあるのなら、それもご紹介いただきたいんですが……(^_^;

回答No.5

punchan_jp

条件としては一般にどんなものが与えられるんでしょう？
項目A =~ /regexp/ && !(項目B =~ /regexp/ && 項目C =~ /regexp/)
ぐらい一般的なんでしょうか？

あと、検索の回数に関してですが、アプリケーションから1回呼ば
れるごとに1回検索するだけなんですね？

で、2回目の検索というのがあったとしたとき、CSVのデータに変更
がある可能性もあって、そのことを知るすべがないのでしょうか？

そうだとすると、前から順に探すくらいしか思いつきません。

お礼

ありがとうございます。

　条件文はだいたいおっしゃるとおりです。
　入力されたＳＱＬ文に対して条件にマッチするデータを抽出します。
　で、検索回数は、１回の呼び出しに対して１回のみです。１回目の呼び出しでインデックスを作って２回目からはそれを使うという手もアリですが、そのインデックスは「ありとあらゆる条件」において流用できなければ実用できません(^_^;
　……こんなところです。

　はっきりいって、現状を保つ（線形検索する）か袋小路で迷うかといったような瀬戸際ですね(笑)
　今のところ前者に心が動いておりますけれども(笑)

回答No.4

toysmith

#3を書いた後で#1への補足を読んだのですが、線形文字列検索ではダメですか？

CSVファイル内の任意の文字列を高速検索するならBM法で何とかなるかでしょう。
アルゴリズム辞典で確認してください。

お礼

ありがとうございます。

　駄目ってことはないんですが、言語が Perl なので、できれば高速化したいんです。あと、文字列検索ではなく、厳密にはデータ抽出ですね(^_^;
　今のところ、処理能力が秒間６００件（セルロン３００）ですが、これだとちょっと弱いので……。

　でも、各アルゴリズムの処理速度を見ていると、何だか線形検索が最速のような気がしてきました(笑)
　線形検索なら速度が最善だろうが最悪だろうが O(n) にできますし。
　とりあえず、条件文の解析の高速化とか、そういう方面でやってみます(^_^;

回答No.3

toysmith

順次検索や大小比較が必要無いならハッシュで行けますね。
ハッシュ表を使わずにデータをほおりこめばインデックスもツリーも不要です（容量的には不利ですが）。

検索の“直前”であろうと“事前”であろうと「ツリーやインデックスを作る」のならB木で良いような気もしますが…。

補足

ありがとうございます。

　「ハッシュ表を使わずにデータを放り込む」とはどういうロジックなんでしょう？　データそのものをハッシュ値として使うのでしょうか。

　それから、ツリー（インデックス）を直前に作るのは、検索条件が複数であるためです。
　Ｂ木検索ではいけない理由は、それを作るためにソートを行うと、条件１、条件２……条件ｎというように条件の個数分だけソートを行わなければならないことになり、結果として処理速度が落ちるのです(^_^;
　なぜそういうことをするのかというと、１つのデータは複数の項目を持っており、条件１では項目Ａをキーとして検索を行い、条件２では項目Ｂをキーとして検索を行う、ということをやるからなわけです。

　データの内容もこちらが予測したものってわけにもいかないので、データの種類に前提を作ることもできませんし……。

回答No.2

punchan_jp

1回しか探索しないのだとすると、木を作る間に探せてしまうでしょ
うから、何度も探索するのを木で高速化したいということでよろし
いでしょうか？

そういう目的なら2分探索木かB木ということになると思います。前
者はバランスが悪い木になってしまうと、リニアサーチと変わらな
くなります。順序がバラバラといっても、もし部分的にソートされ
てたりする可能性があるなら、後者を使うべきでしょうね。

どちらも、
「C言語による最新アルゴリズム事典」奥村晴彦・技術評論社
で解説されています。

補足

ありがとうございます。

　検索回数に関しては……。
　まず俺が作っているのは、他のプログラムから呼び出されるモジュールです。
　アプリケーションからの要求に応じてＣＳＶファイルの中身を読み込み、サーチします。よって、１回しか検索しないかどうかについては何とも言えないのです(^_^;

　ちなみに、データそのものもアプリケーションが用意した物を使うので、部分的にソートされている可能性があるとも言えるし、ないとも言えます。

　どっちにしろご指定の本は便利そうですね。
　本屋で探してみようと思います。

回答No.1

alfeim

データの内容によって色々変わってくると思うのですが・・・
キーの重複の有無、
キーのデータとの完全一致か、一部との一致か
などありますので、もう少し具体的な補足をお願いします

補足

ありがとうございます。

　そういう条件もあるのですね。
　データは基本的に、「ありとあらゆるデータ」が来る可能性があります。テキスト形式で記述されたＣＳＶファイルの中身を検索するためのものだからです。
　よって、キーが重複することもありえます。また、１回の検索で複数のデータが取得できてしまうこともありえます。
　完全一致とかそういうのは、正規表現でなんとでも対処できるので、部分一致は考えなくていい、というところです。

　よろしくお願いします。