検索エンジンの２単語以上の検索について

2004/12/29 15:59

このQ&Aのポイント

検索エンジンについて疑問があります。２単語以上での検索が非常に速いため、その仕組みについて知りたいです。
検索エンジンの２単語以上の検索にはどのような仕組みがあるのでしょうか？形態素解析後の実際の検索部分についても解説してください。
検索エンジンでの２単語以上の検索について考えています。現在のインターセクションによる絞り込み検索の仕組みを超える新たな方法が存在するのでしょうか？

検索エンジンの２単語以上の検索について

最近、検索エンジンに非常に不思議に思っています。SQLなど検索効率のことが分かる方に質問です。あまりにも速すぎる検索ができることです。実際の検索の部分がどのような設計になっているのか検討がつきません。そこでどのような仕組みになっているのか、解説できる方がいましたら、教えて頂きたいです、ベールに包まれた謎の仕組みを・・・。疑問に思っているのは形態素解析後の実際の検索部分です。１単語で検索されることを前提とすると、単純に先頭の文字コードからインデックスを作ればよく、世界に１つもない単語であっても、もっとも近い付近から探せば「ない」という結果がすぐにわかります。問題は次のステップで、２つ以上の単語の組み合わせの場合どのような仕組みになっているのかということです。絞り込み検索の仕組みがどのようになっているかということです。自分が考えた方法では、例えば、ページ情報テーブル、コアラテーブル、ラッコテーブル、を作り、ページ情報テーブル ABDEFSD,http://animal-rakuen.dom/koara_to_rakko/ VBCEFSD,http://animal-rakuen.dom/koara/kaisetsu/ CBFEFSD,http://rakko.dom/ DBGEFSD,http://uminoikimono.dom/rakko/ ・・・・コアラテーブル ABDEFSD VBCEFSD ・・・・ラッコテーブル CBFEFSD ABDEFSD DBGEFSD ・・・・のようなテーブルを作り、コアラとラッコの積集合を求め、重なっているものをページ情報テーブルよりさがすという方法を考えましたが(大まかな考え方です)、件数が多くなっていった場合で検索結果が存在しない時はインターセクションでは遅すぎるので現実的ではないと思います。ですので、非常に不思議に思っています。２単語以上の検索について、その内部的な仕組みがどのようになっているのか・・・。考えつく方いらっしゃったら是非勉強させてもらいたいです！宜しくお願いします。

jamjam_goo
お礼率33% (1/3)

その他(データベース)
回答数3
ありがとう数6

みんなの回答 （3）
専門家の回答

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

ベストアンサー

dylandylan
ベストアンサー率33% (1/3)

2005/01/03 21:30 回答No.2

全文検索を行う方法としてはSuffix Arrayなど他にもありますが、転置インデックス以上に早い検索方法は聞いたことがないのでグーグルやヤフーなどが転置インデックス法を行っているのはほぼ間違いないと思います。ただ、検索エンジンをつくるときはRDBMSなどの重たいDBMSは使いません。全て自作するか、berkeley dbやQDBMなどの軽いデータベースを使うのが普通です。ちなみに、検索部分に使っているかはわかりませんが、グーグルやヤフーがberkeley dbを使っているのは以下のURLでわかります。 http://www.sleepycat.com/solutions/customers.shtml QDBMを使った検索エンジンとしてはEstraierなどがあります。ただ、グーグルやヤフーレベルになるとそれでも足りなくて、安いサーバを何台も買ってきて並べ検索を1,000台以上のマシンが並列して行っているようです。また、それだけサーバが多いと1日に何台も故障するため、耐障害性の高いソフトウェアを独自に開発しているそうです。

参考URL：: http://internet.watch.impress.co.jp/cda/event/2004/11/16/5430.html

質問者

補足 2005/01/04 21:38

お返事ありがとうございます。グーグルやヤフーがQDMBというものをつかっているとは知りませんでした。berkeley dbというものも初めてしりました。興味深い情報をありがとうございます。ですが、おおまか、転置インデックス型がどのようになっているのかが当初のお聞きしたい内容でした(質問の最後の方に検索エンジンがどのような仕組みかと聞いてしまい、質問の仕方が少々悪かったです、申し訳ありません)。例えば、　　　コアラ　ラッコ　... URL1　　0　　　1 　 ... URL2　　1　　　0 　 ... URL3　　1　　　1　　　... ...　　...　　... とした場合、”行”の方は問題ないと思いますが、列の方が無限大に増えてしまい、作業を分散しにくいと思いますが、一般的な検索エンジンはこのような方法なのでしょうか？

その他の回答 (2)

dylandylan
ベストアンサー率33% (1/3)

2005/01/04 23:02 回答No.3

えーっと、QDBMやberkeley dbなどでは表という概念がありません。キーとデータの関連付けが出来るだけです。連想配列とかハッシュがディスクに記録できるものといえばわかりやすいでしょうか。で1番目の回答でも答えたとおり、実際に記録するのは、コアラという単語をキーにして011...というデータをラッコという単語をキーにして101...というデータを記録するわけなので、列の方が無限大に増えてしまうことはありません(そもそも列という概念がない)。 1番目の回答で書いた表は説明のために作っただけで、実際にあのような巨大な表を作るわけではありません。また、2番目の回答の文章が悪く誤解されたようですが、グーグルやヤフーはQDBMを使ってはいないと思いますよ。 berkeley dbを使っているのは確かですが、検索部分に使っているかは知りません。自分が検索エンジンを作ったときはberkeley dbを使いましたが。

質問者

お礼 2005/01/06 00:10

回答ありがとうございました。転置インデックスの説明にはほとんどの解説書に表がかいてあったので表形式で検索されていると思いました。おっしゃっていることが分かりました。検索エンジンを作りたいというわけではありませんが、今まで全く、わからなかった検索エンジンの仕組みがある程度は理解できました。ありがとうざいました。

dylandylan
ベストアンサー率33% (1/3)

2004/12/30 05:58 回答No.1

全文検索を行う場合、よく使われるのは転置インデックスという方法です。たとえば、URL1にラッコ、URL2にコアラ、URL3にラッコとコアラの単語が含まれていた場合　　　コアラ　ラッコ　... URL1　　0　　　1 　 ... URL2　　1　　　0 　 ... URL3　　1　　　1　　　... ...　　...　　... という表を作っておいてコアラという単語をキーにして011...というデータをラッコという単語をキーにして101...というデータを記録しておきます。で、コアラ　ラッコで検索をかけるときはこの2つのデータのANDをとればいいだけなのでそれほど遅くはならないと思います。またこの覚えておくデータは0がほとんどなので(ほとんどのページにはラッコやコアラという単語は現れてこない)、工夫次第でANDをとるときの速度や記録するための容量を減らすことができます。まあここで下手な説明聞くより転置インデックスで検索すれば詳しい説明が読めると思いますが。

参考URL：: http://www.jaist.ac.jp/~kshirai/lec/i223/12.pdf

質問者

補足 2004/12/30 20:07

返答ありがとうございます。転置インデックス型も一度考えましたが、システムに登録したい文字が数百万個の場合、カラムが数百万になると思いますので、大変なことになってしまうのではないでしょうか？大規模な検索エンジンのグーグルやヤフーなどはこの転置インデックス型のような仕組みで検索されているのでしょうか？細かいですが宜しくお願いします。