線形探索の限界
「パソコンの文書を探す性能はすごいってことはよくわかった。でも、Googleが相手にしているのは世界中のWebページだよ。そんな莫大な量の文書にパソコンの性能で本当に立ち向かえるの？」―――おっしゃる通り、パソコンで書いた日記と世界中のWebページは、大きさでは比べものになりません。世界中のWebページ相手に線形探索したとき、どれぐらいの時間がかかるのかをざっと計算してみましょう。
世界中のWebページの総数は、現在1兆ページを超えているといわれています。1ページあたりの平均文字数をかりに1000文字とすると、Webページ全体を探すには1000兆文字、1000兆×3バイト=3000兆バイトを処理する必要があります。さきほどの紙テープの例えでは、150億キロメートル、地球から冥王星への距離の約3倍（！）になります。パソコンが1秒間に5000キロメートル相当の距離を探せるとすれば、300万秒=約35日かかる計算になります。「キーワードを検索窓に入れてから結果が出てくるまで1ヶ月以上かかるの?! 話にならないよね」―――こんなに時間がかかってしまうのでは、気軽にキーワードで探そうという気分にはとてもなれないですよね。
「たしかGoogleはたくさんのパソコンが組み合わさってできているって言っていたよね。パソコン1台でダメでも、何百万台ものパソコンで分担して探したらもっと速くなるんじゃない？」―――その通り、150億キロメートルの紙テープをハサミで短く切り分けてしまえば、たくさんのパソコンで分担できます。5000キロメートル（1ギガバイト）ごとに分割すれば、300万台のパソコンがあれば1秒で探し終わる計算になります。
「300万台のパソコンをそろえるのは大変そうだけど、Googleならそれくらいやりそうだよね」―――ちょっと待って。Googleを使っているのはあなただけじゃありませんよ。Googleは世界中の人々から1秒間あたり何万回もの検索要求を受け付けています。1秒間あたり1万回の要求に応えるためには、300万台の1万倍、300億台のパソコンが必要になります。パソコン1台あたり5万円とすると1500兆円ですから、アメリカ合衆国の1年間のGDP(国内総生産)を超えてしまいます……。
「そりゃいくらGoogleでも無理だね。けっきょく線形探索ではWeb検索エンジンは作れないのか。これまでの説明はいったいなんだったの？」―――ここまで長々と説明してきた方法だけではWeb検索エンジンをつくることはコスト面から不可能です。コストの壁を乗り越えるには、「転置インデックス」という名の秘密兵器が必要になります。次回の連載では、「転置インデックス」について説明していきます。お楽しみに！
