-PR-
解決済み

検索アルゴリズム

  • 暇なときにでも
  • 質問No.46758
  • 閲覧数648
  • ありがとう数5
  • 気になる数0
  • 回答数7
  • コメント数0

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

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

 よろしくお願いします。
通報する
  • 回答数7
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

質問者が選んだベストアンサー

  • 回答No.7
レベル11

ベストアンサー率 58% (114/195)

>Perl からSQLが呼べないかなぁと
>PasageSQLやMySQLだと一般プロバイダのCGI環境では使えないから

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/
お礼コメント
noname#25358

 ありがとうございます。

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

 解説書は、財布と相談したうえで、ヒモが緩んでくれれば買いたいと思います(笑)
 URLの方はさっそくソースを落としに行きたいと思います。
投稿日時 - 2001-03-02 23:39:14
-PR-
-PR-

その他の回答 (全6件)

  • 回答No.2
レベル11

ベストアンサー率 55% (155/280)

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

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

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

 ありがとうございます。

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

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

 どっちにしろご指定の本は便利そうですね。
 本屋で探してみようと思います。
投稿日時 - 2001-03-02 16:27:17


  • 回答No.1
レベル11

ベストアンサー率 58% (114/195)

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

 ありがとうございます。

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

 よろしくお願いします。
投稿日時 - 2001-03-02 16:19:01
  • 回答No.3
レベル13

ベストアンサー率 37% (570/1525)

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

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

 ありがとうございます。

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

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

 データの内容もこちらが予測したものってわけにもいかないので、データの種類に前提を作ることもできませんし……。
投稿日時 - 2001-03-02 16:40:54
  • 回答No.4
レベル13

ベストアンサー率 37% (570/1525)

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

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

 ありがとうございます。

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

 でも、各アルゴリズムの処理速度を見ていると、何だか線形検索が最速のような気がしてきました(笑)
 線形検索なら速度が最善だろうが最悪だろうが O(n) にできますし。
 とりあえず、条件文の解析の高速化とか、そういう方面でやってみます(^_^;
投稿日時 - 2001-03-02 17:55:33
  • 回答No.5
レベル11

ベストアンサー率 55% (155/280)

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

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

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

そうだとすると、前から順に探すくらいしか思いつきません。
お礼コメント
noname#25358

 ありがとうございます。

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

 はっきりいって、現状を保つ(線形検索する)か袋小路で迷うかといったような瀬戸際ですね(笑)
 今のところ前者に心が動いておりますけれども(笑)
投稿日時 - 2001-03-02 17:59:00
  • 回答No.6
レベル11

ベストアンサー率 58% (114/195)

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

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

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

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

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

 MS SQL Server の解説書はめちゃくちゃ欲しいです(笑) 本屋にありますか?
 オープンソースのデータベースソフトがあるのなら、それもご紹介いただきたいんですが……(^_^;
投稿日時 - 2001-03-02 18:07:02
このQ&Aで解決しましたか?
AIエージェント「あい」

こんにちは。AIエージェントの「あい」です。
あなたの悩みに、OKWAVE 3,500万件のQ&Aを分析して最適な回答をご提案します。

関連するQ&A
-PR-
-PR-
こんな書き方もあるよ!この情報は知ってる?あなたの知識を教えて!
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する
-PR-
-PR-
-PR-

特集


専門家があなたの悩みに回答!

-PR-

ピックアップ

-PR-
ページ先頭へ