Googleはなぜ的確に探せるのか？ ― 第2回

悟空、秘剣「転置インデックス」を手に入れる

2008年12月08日 08時00分更新

文● 清田陽司／東京大学情報基盤センター図書館電子化研究部門助教

　「大量の文書を検索する」ことについて、最近のパソコンには人間をはるかに上回る性能があります。しかし、検索対象がパソコンの外側の世界になると、どんなに高性能なパソコンでも歯が立ちません。でも、ふだん私たちが利用しているGoogleなどのWeb検索エンジンは、検索キーワードをボックスに入力してから1秒足らずで検索結果を返してくれます。もしGoogleの検索が1分以上かかっていたらどうでしょうか？　検索結果を待つのにイライラしてしまい、そのうち使わなくなってしまうかもしれませんね。

　文書をキーワードで検索する能力で、私たち人間はパソコンの足元にも及びません。たとえば、何かの本で「自然言語」というキーワードが使われているページを全部探すとしたらどうでしょうか。その本を1ページずつめくって「自然言語」という文字列を血眼になって探しても、おそらく何十分もかかることでしょう。そのうち疲れてきて、見落としたりするかもしれません。

　とはいえ実際には本を1ページずつめくって探す必要はありません。私たちにはとっておきの秘密兵器があります。多くの本の巻末には、「索引ページ」があって、「自然言語……29,61,63」などと、本の中で登場するキーワードが何ページ目に登場するのか一覧になっています。索引ページを参照すれば、キーワードが使われている場所（ページ番号）を素早く探し出せます。索引は人間にとって、「文書検索の飛び道具」と言えるでしょう。

　「じゃあ、Googleも同じように索引を作っているの？　もしかして世界中のWebページ全部の巨大な索引を？」――その通りです！　Googleのあの検索スピードは、索引なくしては実現不可能です。今回は、パソコンが索引を使って文書を検索する仕組みに迫ります。

文書の索引を人手で作ってみる

　1台のパソコンのハードディスク内に、この連載の全文が回ごとにファイルとして格納されているとします。この連載は全部で7章あり、章を分割して連載の1回分として構成していますので、「はじめに」「おわりに」を合わせて9個のファイルがあります。

　キーワードを使って素早く検索できるように、この9個のファイルから索引を作ってみましょう。人手では、以下のようにすると索引を作れます。

　まず、それぞれのファイルから、索引の見出しとなるキーワードを全部抜き出します。

　上はそれぞれの文書に含まれるキーワードを列挙した表です。ただし、この表では素早く文書を検索できません。たとえば、「パソコン」というキーワードをそれぞれの文書の長いキーワード列から探すのはけっこう大変です。そこで表を変換して、それぞれのキーワードが含まれる文書を列挙した表を作ります。

　前の表が「文書ごとにまとめた表」であるのに対して、この表は「キーワードごとにまとめた表」になっています。これで、皆さんおなじみの「巻末索引」に相当するものができました。上の表を使えば、「パソコン」を含む文書がどれか、一目で分かります。

　これで、表に含まれるすべてのキーワードに対して文書を検索できます。実は、2つ以上のキーワードを組み合わせて検索するときにも同じ表が使えます。検索の条件が「パソコン AND 文書」（「パソコン」と「文書」の両方を含む文書という意味です）であるとしましょう。表を参照すると、「パソコン」を含む文書の集合は「第1章、第3章、……」、「文書」を含む文書の集合は「第2章、第3章」であることが分かります。両方の文書の集合に現れている「第3章」が、検索の条件にマッチする唯一の文書であると分かります。