（文字列検索の手法について）検索エンジンはなぜあんなに高速で検索できるのですか？

質問

googleなどの検索エンジンについて。
どうやってあれほどのスピードで検索できるのか？と言う疑問です。

天文学的な数が存在するウェブサイト群から、ほんの一瞬で何万件とリストアップできるのはなぜでしょう？
テキストデータとは言え、情報量にしたら何十？何百テラバイト？見当もつきませんが、
サーバー側にキャッシュが溜まっているとは言え、これらの内容全部を一瞬で走査することができるのが驚きです。
しかも利用者は私一人ではない、全世界中から次々と検索リクエストが来るのにも関わらずです。

私はかけだしのプログラマーですが、文字列検索のテストプログラムなどを作ってみても、
どうやってもあれほどのケタ違いのスピードは出せません。
自分のパソコンから検索するだけでもそれなりの時間がかかってしまいます。
とても不思議です。

後学のために、どのようなハードウェアで、どのような言語のプログラムで、
どのようなアルゴリズムで、あそこまでのスピードを実現しているのか教えていただきたいです。
よろしくお願いします。

回答No.2

todo36

Googleの論文をまとめた、技術解説本が出版されました。

Googleを支える技術 ……巨大システムの内側の世界
http://gihyo.jp/magazine/wdpress/plus/978-4-7741-3432-1/0003

著者インタビュー
http://gihyo.jp/magazine/wdpress/plus/978-4-7741-3432-1/0003

「1回の検索のために数千台のマシンを使う」だそうです。

個人的には、この本すげー読みたい。

回答No.1

shred

>これらの内容全部を一瞬で走査することができるのが驚きです
さすがのgoogleさんもこんなことは出来ません。
一般的に上の様な検索手法をgrep型検索と呼ぶのに対し
googleが実装するのは索引型検索というものです。
３０万台稼動しているとも言われるgoogleのサーバが全世界から
集めたwebページをそれぞれ走査して予め索引(index)を作っておきます。
索引の作り方は様々ですが私が学校の演習で行ったときは
形態素解析による手法を用いました。それぞれの形態素の出現頻度など
によりベクトルを作成します。
そしてユーザからのクエリからベクトルを計算し索引ベクトルと
類似度計算を行います。
その後google独自のランキングアルゴリズムによりユーザに結果を返します。
つまり一般的には
・索引生成アルゴリズム
・類似計算アルゴリズム
の２つを以下にうまく実装するかが検索精度、レスポンスの早さにつながるというわけです。
今回私が書いたのはかなり単純な例ですが基本的原理はgoogleでも変わらないはずです。

お礼

ありがとうございます。
30万台とは驚きです。
索引生成、形態素解析、類似計算といったキーワードで研究してみようと思います。