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

最近、検索エンジンに非常に不思議に思っています。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
・・・・

のようなテーブルを作り、コアラとラッコの積集合を求め、重なっているものをページ情報テーブルよりさがすという方法を考えましたが(大まかな考え方です)、件数が多くなっていった場合で検索結果が存在しない時はインターセクションでは遅すぎるので現実的ではないと思います。ですので、非常に不思議に思っています。２単語以上の検索について、その内部的な仕組みがどのようになっているのか・・・。考えつく方いらっしゃったら是非勉強させてもらいたいです！宜しくお願いします。

No.2 ベストアンサー 回答者： dylandylan 回答日時： 2005/01/03 21:30

全文検索を行う方法としては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/20 …

この回答への補足

お返事ありがとうございます。
グーグルやヤフーがQDMBというものをつかっているとは知りませんでした。berkeley dbというものも初めてしりました。興味深い情報をありがとうございます。

ですが、おおまか、転置インデックス型がどのようになっているのかが当初のお聞きしたい内容でした(質問の最後の方に検索エンジンがどのような仕組みかと聞いてしまい、質問の仕方が少々悪かったです、申し訳ありません)。

例えば、
　　　コアラ　ラッコ　...
URL1　　0　　　1 　 ...
URL2　　1　　　0 　 ...
URL3　　1　　　1　　　...
...　　...　　...

とした場合、”行”の方は問題ないと思いますが、列の方が無限大に増えてしまい、作業を分散しにくいと思いますが、一般的な検索エンジンはこのような方法なのでしょうか？

補足日時：2005/01/04 21:38

No.3 回答者： dylandylan 回答日時： 2005/01/04 23:02

えーっと、QDBMやberkeley dbなどでは表という概念がありません。

キーとデータの関連付けが出来るだけです。
連想配列とかハッシュがディスクに記録できるものといえばわかりやすいでしょうか。

で1番目の回答でも答えたとおり、実際に記録するのは、
コアラという単語をキーにして011...というデータを
ラッコという単語をキーにして101...というデータを
記録するわけなので、列の方が無限大に増えてしまうことはありません(そもそも列という概念がない)。
1番目の回答で書いた表は説明のために作っただけで、実際にあのような巨大な表を作るわけではありません。

また、2番目の回答の文章が悪く誤解されたようですが、
グーグルやヤフーはQDBMを使ってはいないと思いますよ。
berkeley dbを使っているのは確かですが、検索部分に使っているかは知りません。
自分が検索エンジンを作ったときはberkeley dbを使いましたが。

この回答へのお礼

回答ありがとうございました。
転置インデックスの説明にはほとんどの解説書に表がかいてあったので表形式で検索されていると思いました。おっしゃっていることが分かりました。

検索エンジンを作りたいというわけではありませんが、今まで全く、わからなかった検索エンジンの仕組みがある程度は理解できました。

ありがとうざいました。

お礼日時：2005/01/06 00:10

No.1 回答者： dylandylan 回答日時： 2004/12/30 05:58

全文検索を行う場合、よく使われるのは転置インデックスという方法です。

たとえば、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