前回に引き続きサーチエンジンの仕組みの話をしたいが、今日はインデクスについて話したいと思う。とりあえず、インデクスがぴんと来ない人は本の後ろにある索引を想像してもらうと良い。五十音順に単語とページ番号が対になって並んでいるあれだ。
サーチエンジンのインデクスも本の索引も本質的に変わらないので、このような理解でまずは良い。
さてこのインデクスを作成するプログラム(一連の処理)をインデクサーと呼ぶ。
サーチエンジンの仕組みを理解する上で、大きく3つに分けて考えると言ったが二つ目の要素がインデクサーだ。今回はこのインデクサーの仕組みを話そうと思う。
- インデクサー
インデクサーはクローラーに収集されたHTMLからインデクスを作成する。インデクスとはこの場合、「単語とURLの対」と思っておけば良い。本のページ番号の代わりにURLが書いてあると想像して欲しい。そのためまずはHTMLから単語を切り出す作業が必要になる。
単語を切り出す作業には通常、形態素解析が用いられる。英語では単語と単語の間はスペースで区切られるが、日本語は単語と単語の間に明確な区切りがない。なんらかの手法により文章を単語に分けなければいけないが、この時に用いられるのが形態素解析だ。中国語、韓国語でも同様の処理が必要になる。
形態素解析には大手メーカーの研究所や大学のものが存在するが、いずれかのプログラムを用いて文章を単語の集まりに分解する。
例えば、「私は日本人です。」は「私+は+日本人+です+。」というように。形態素解析には基になる辞書が必要だが、最近の言葉や一部だけで使われる固有名詞などは辞書に登録されていなかったり、あるいは登録するとその弊害で元々うまく分けられていた文章を誤って分けたりするので、簡単に辞書を変更するわけにも行かない。各社独自に出来るだけ自然に分けられるアルゴリズムの開発を研究している。
ここでは形態素解析を使っているということを理解していただければよい。この形態素解析を使っているという事実が想定しない検索結果を生み出す原因となることがある。自分が入力した言葉が思った通りに解釈されていない可能性があるのだ。
また同じ単語でも「引越」、「引越し」、「引っ越し」などと色々な書き方があるが、通常では全く別の単語としてインデクスに登録される。同じ単語でもひらがな、カタカナ、漢字で書いた場合では違った単語として認識される。最近Googleに切り替えたGooでは、このような表記のゆれを前段階で処理することによりどのように書いても同じ結果が出るような工夫をしている。
さらにインデクスを作成する際にはその他の作業が行われることが多い。例えば、その文章が何語で書かれているかという判定(Language Detection)をしたり、検索結果で表示する際に必要となる「サマリー」の情報を作成しておく等である。
最終的には形態素解析で分けられた単語とURLを対応付けたものがインデクスだ。
インデクスは先ほども述べたとおり本の例で考えると分かりやすい。例えば今手元にある「Googleポケットガイド(オライリー・ジャパン)」の索引の"P"のところを見ると、
P
Pagerank ....................... 9, 63, 115
PDF .................................... 38, 40
phonebook: ............ 32, 37, 94, 123
PHP ........................................ 32
となっている。キーワードを引けば、それがどのページにでているか分かるものが索引だ。洋書を読まれる方はお気づきと思うがが、索引は英語で"Index"だ。そう、まさにこれがサーチエンジンで言われるところのインデクスと同じことを意味している。
上記の例で、ページ番号の変わりにURLを書いてみたらどうなるでしょうか?こんな風になりますかね。
Pagerank ... http://www.google.com/techno... http://www.google.com/intl... ... http://www.adobe.com/products/... http://www.adobe.com/ phonebook: ... http://www.phonebook.com/ http://www.uiuc.edu/ricker... http://www.hep.net/sites/... PHP ... http://www.php.net/
どうだろうか?なんだかサーチエンジンらしくなってきたでしょう?インデクスとはまさに本の索引のように「キーワードとURLの対応表」なのだ。インデクスとは、いわばWWWの索引と言える。
一番簡単にインデクサーの理解をするために、PageRankなどの順番を決める処理部分の説明を省いた。これらの処理もインデクス作成の一連の処理の中で行われる。
次回はクエリーサーバーについて説明しよう。
(追記:2004/5/12)
「索引」を誤って「目次」と書いたため、訂正させて頂きました。ご指摘いただいた方、ありがとうございました。
-inoue