情報検索問題
背景
皆さんは検索エンジンをいつ頃から使っていますか？ WWW (World Wide Web) がバーナーズ・リーによって発明されたのは1989年なので、皆さんが生まれたときには、WWWはすでにネット上に存在していました。Googleが登場したのは1998年です。ですから早い人であれば、小学生のときには、家庭や学校などで検索エンジンを使っていたかもしれませんね。ちなみに「エンジン」という言葉は、普通は自動車やロケットなどで使われている内燃機関(より一般的には、力を動きに変換する装置)のことを指しますが、コンピュータサイエンスの分野では、ある機能に特化した処理装置のことをなぜか「エンジン」と呼びます。「検索エンジン」のほかにも、PS3などでも使われている「グラフィックエンジン」や「レンダリングエンジン」などの呼称が有名です（個人的には、サイボーグ009で出てくる加速装置みたいで好きな呼称です :-）。
検索エンジンがしなくてはならないこと
我々が使っている検索エンジンの基本動作は、与えられたキーワードからそのキーワードにマッチするページのネットワーク上の位置(URL)を出力することです。それでは、キーワードを受け取ってから結果を出力するまでの間に、検索エンジンの内部ではどのような処理がおこなわれているのでしょうか？キーワードを受け取ってからインターネット上を探し回り、キーワードにマッチする答を返してくれているのでしょうか？コンピュータはいろいろな仕事をあっという間に片付けてくれる魔法の箱なので(笑)、インターネット上で必要な情報を探し回るのもあっという間だと思いますか？
少し考えればわかることですが、実はそのような方法だとぜんぜん使い物になりません。ネットワークがよほど混雑してでもいない限り、Googleにキーワードを入力してから回答が返ってくるまでの時間は1秒以内です(試してみてください)。物理の時間で習ったように、光は1秒間に地球を7周半しかできませんから、たとえば地球の裏側にあるコンピュータにメッセージを送ってそこからメッセージを返した場合、往復するだけで0.13秒かかってしまいます。つまり検索の途中で10回程度の地球規模の通信がなされるだけで、持ち時間の1秒を使い切ってしまうのです。それどころか、メッセージを中継するコンピュータの忙しさの度合いによっては、検索結果を出力するまでの時間は軽く数日を超えてしまうでしょう。検索結果はインターネット全体をカバーしているはずなのに、インターネット全体を探し回ったのではとても間に合わない、というところに問題の面白さがあります。
Google の解決法
この状況を克服するためにGoogleがやっているのは実はとても単純なことです。
全世界のウェブページをすべてコピーして、自分のもっているコンピュータ上にあらかじめ保存しておけばよい。そしてユーザからの要求を受け取ったときは、その要求にマッチするページがあるかどうかをコピー上でチェックすれば、ネットワーク上を探し回ってチェックしたのと同じような結果が得られるはずです。加えて、返される結果に「そのコンテンツのオリジナルがどのコンピュータ上に保管されているのか」という情報(URL)も含めておけば、完璧です。そうすることでユーザは検索エンジンからの回答をもとにして、(コピーではなく)ウェブページそのものにアクセスすることが可能になります。
インターネットはどのくらい「広い」のか
一説によると、インターネット上のウェブページの総量は数PBだそうです。PBはペタバイトと読み、DVDの記憶容量をあらわすのに使われているGB(ギガバイト)という単位の100万倍にあたります。仮にこの値が1PBだとすると、DVDの約20万枚分です。この値を大きいと思うかどうかは人によって違うと思いますが、2008年現在、1000GBの容量をもつHDD(ハードディスク)の価格は10万円以下ですから、１億円を投資すれば十分実現できる程度の大きさです。また、1000台程度のHDDであれば、高校の教室にも十分おさまります(多少の電気工事は必要ですが)。インターネットが「無限の広さ」をもっているという感覚を持っている人は、少し考えを改めた方がいいかもしれませんね。
ちなみに、過去のさまざまな時点でのウェブページを保存してあるインターネットアーカイブというサイトがあるのですが、このサイトにはインターネット上に存在していた多くのウェブページの“履歴”が保存されており、それらを過去にさかのぼってアクセスすることができます(ちょっとしたタイムマシンのようなものです。皆さんの高校の昔のページをのぞいて見てみると面白いかもしれません)。このアーカイブの2006年現在の容量は2PBだそうなので、上記の試算ともほぼ一致しています。
それでは１億円用意してHDDを設置すれば明日からでもGoogleのようなことができるのかというと、それも少し違う。ここまで述べてきたことは、インターネット上のすべての情報をコピーしておくためのスペースはこうやったら実現できますよ、という話であって、集めた情報の中からキーワードにマッチする情報をどのようにして素早く見つけるのかについては、まだ何も言っていません(ハードウェアについては述べたけれども、ソフトウェアについては何も言っていないということです)。実際、この部分をうまく実現できれば、Googleの性能をはるかに超える性能をもった新しいタイプの検索エンジンをつくることだってできるはずです。どのように実現するのがよさそうかを記述するには、このページの余白はせますぎますが（笑）。
検索エンジンのソフトウェアをどのようにつくればよいのかという点については、ある程度の予備知識が必要なので、興味のある人は自分で勉強してみてください。ここでは、「与えられた条件にマッチする情報を素早く見つける」という問題が、コンピュータサイエンスの分野では過去何十年にもわたって研究されている重要なテーマのひとつだということだけを指摘しておきます。詳しくは大学の授業で勉強しますが(たとえばほとんどの情報系の学科では「アルゴリズムとデータ構造」という名前の授業があります)、基本的な考え方だけであれば、高校生でも十分理解できるはずです。
| 次のテーマを見る | トップページへ戻る |
