わからないことがあったらとりあえずググる、という人は多いだろう。しかしそのGoogleの技術について、詳しく知らない人は多いのではないだろうか。ここでは、西田圭介「Googleを支える技術」（技術評論社）とウェブマスターツールを参考に、そのシステムの内側を４回にわたって解説する。（敬称略）
１ 検索エンジンは３つの要素から成り立っている
検索エンジンは、検索サーバ、検索バックエンド、そしてインデックスの３つの要素から成り立っている。以下にそれぞれの要素について説明する。
検索サーバ
検索サーバとは、利用者からのリクエストに応えて検索を行うコンピュータである。その役割は、利用者の求める情報を「なるべく早く見つけ出すこと」である。そのため「検索サーバは速度が命」といえる。下記に主な役割を４点引用する。
- 利用者との通信を管理する
- 利用者からのリクエストを解析し、行うべき処理を判断する
- インデックスから必要な情報を探し出す
- 結果を見やすくレイアウトし、利用者に送り出す
検索バックエンド
検索バックエンドとは、インターネットから情報を集めて整理するコンピュータである。その役割は、「優れたインデックスを作り上げること」である。大きく分けてクローリングとインデックス生成の２つに分けられる（詳細は後述）。これらのインデックスを作るまでの「事前の努力」が、Googleの高速な検索を支えている。
インデックス
インデックスとは、検索サーバと検索バックエンドの間で利用されるデータベースである。その役割は、与えられたデータを安全に格納し、求められたデータを高速に見つけ出すことである。その本質は「与えられた検索キーに対応する値を返すこと」であり、データを数値化することによって高速化している。つまり、「インデックスは検索の柱」といえる。
２ クローリング
クローリングとは、世界中のWebページを収集することである。これには多くの時間が必要となるため、クローラという複数のマシンが分担して作業を進める。クローラが集めたWebページは一時的にリポジトリ（docID、url、textなどを格納）と呼ばれる領域に保管される。
その特徴として、以下の４つが挙げられる。
- 壊れやすい：多種多様なWebサーバ、Webページを相手にしているから
- 時間がかかる
- 多数のダウンロードを同時に進める
- 終わりがない
３ インデックス生成
インデックス生成とは、リポジトリからWebページを取り出して、検索用のインデックスを作り上げる処理である。「検索用データベースを作り上げること」ともいえる。この処理は、Webページの「構造解析」「単語処理」「リンク処理」「ランキング」といった様々な過程に分けられる。
構造解析
構造解析とは、Webページに含まれるHTMLタグを解析してタイトルなどの情報を抜き出し、同時に不要な情報は捨てて検索のためのテキストだけを取り出す作業である。この段階で、「DocIndex」と「URLlist」という２つのインデックスが生成される。
DocIndexはWebページの基本情報が書き込まれるインデックスで、「docID」をキーとして、そのWebページの情報が書き込まれる。
URLlistはそれとは逆に、WebページのURLをキーとしてdocIDを得るためのインデックスである。
単語処理
単語をwordIDに変換する（Lexicon：用語集）
テキストを単語に分解し、それを「wordID」という数値に変換すること。
単語インデックスの生成（Barrels：樽）
Webページ内の各単語の情報をインデックスに登録する作業のこと。初代Googleでは、docID、wordID、位置、大きさ、その他（装飾など）の情報が登録されていた。
転置インデックスの生成
単語が含まれるWebページの情報を検索するために、wordIDをキーにしてdocIDを得られるように並べ替えたもの。
リンク処理
インデックスURLlistとインデックス「Links」を結びつけることである。アンカーテキスト（リンクに付けられた文字列）もインデックスされる。
ランキング
単語処理とリンク処理後にインデックス形成されるものである。初代Googleでは、PageRank、アンカーテキスト、単語の３つでランキングが形成されていた。PageRankとは、リンクされればされるほど点数は高くなるが、相応に評価されたページからのリンクでないと重視されないということである。その概念は以下の３点にまとめられる（参考：Googleの秘密—PageRank徹底解説）。
- 各Webページは自分の点数を持つ
- 他のページにリンクすると、自分の点数を分配する
- 自分の点数は、他のページからもらった点数の合計で決まる
これらの過程を経るからこそ、Googleは高度なランキングを実現することができた。
４ 検索サーバ
検索サーバの仕事は「求める情報を即座に見つけること」である。それは、前述のインデックス生成がされることで果たすことができる。以下にその流れをまとめる。
- 利用者から検索リクエストが送られる
- 検索語が Lexicon によって wordID に変換される
- wordID を転置インデックスから検索し、docID のリストを得る
- 得られた docID のすべてについてランキング関数を適用し、点数の高い順に並べ替える
- ランキング上位の docID のそれぞれについて Web ページの情報を取り出す
- 得られた情報を見やすい結果に整え、利用者に返す
複数の単語の検索といった複雑な検索においても、共通のdocIDやwordIDの位置情報を見ることなどで対応できる。
最後に
「使う人にとっての便利を第一に考える」Googleの目的は当初からぶれていない。Googleと相性の良いサイトの推奨事項にも「ユーザーが探している情報を提供する」が挙げられている。本記事も読者の役に立てば嬉しい。
次回は大量のデータを用いるための、大規模な分散システムについてまとめる。
 |
