ITエンジニアのための勉強会・イベントレポート情報メディア

10分で理解する検索エンジン--書籍の索引から発展した検索エンジンの仕組み
lifehack

10分で理解する検索エンジン--
書籍の索引から発展した検索エンジンの仕組み

2018.12.03

 
  • このエントリーをはてなブックマークに追加

キーワード検索をするたびに、
世界中のウェブを全文検索している!?
わけではありません

グーグルなどでおなじみの検索エンジン。キーワードを入れれば、その言葉が含まれるウェブを瞬時に世界中から探し出し出してきてくれます。でも、この検索がどのような技術で行われているのかについては、意外と知らない人が多いようです。

まさか、キーワード検索をするたびに、世界中のウェブを全文検索していると思っている方はいらっしゃないと思います。そんなことをしていたら、とてもあのような短い時間で検索することは不可能です。世界にはウェブが3億サイトほどあると言われています。ひとつのサイトに複数のウェブページがあり、グーグルは、すでに1兆ページを発見しているそうです。1ページ分の全文検索が0.01秒で済むとしても、全文検索をするのに317年もかかる計算になります。1ページの検索にかかる時間が0.001秒だとしても、32年かかるのです。

多くの人は「グーグルはクローラーと呼ばれるプログラムを使って、ウェブのカタログを作成し、それを検索する」ということをご存知だと思います。クローラーというのは虫などが這い回る姿を指す言葉で、ウェブからウェブへ這い回り、そのカタログ情報をグーグルに送信し、グーグルはそれを蓄積して、検索をしています。

クローラーと呼ばれるプログラムを
使って、ウェブのカタログを作成

では、このカタログ情報というのはどんなものでしょうか。単なるウェブのテキストコピーだとしたら、30年はかからないまでも、1秒以下で全文検索が完了するわけはありません。

このカタログの作り方に、瞬時にキーワード検索ができる秘密があるのです。

このカタログ作りの基本的なアイディアは、グーグルが発明したものではありません。グーグルが1998年に創業した時、すでにInfoseek、Lycos、AltaVistaなどの検索エンジンが存在していました。しかし、このような検索エンジンも発明者ではありません。15世紀に活版印刷が始まった頃、すでにこのカタログのアイディアが存在していました。書籍の索引です。

学術書などの最後には、本文に出てくる重要単語の一覧があり、その単語が何ページに登場するかを示した索引=インデクスがあります。検索エンジンのカタログは、本文をそのままコピーするのではなく、このインデクスの構造になっています。書籍の索引は、登場するページを示しますが、検索エンジンの索引は、各ウェブページのURL(アドレス)を示します。

検索エンジンは、利用者が
検索ワードとして入力した単語を
索引から検索

検索エンジンは、利用者が検索ワードとして入力した単語を、この索引から検索して、示されたURLを出力します。ですので、瞬時に必要なページを並べた検索結果を表示することができるのです。

しかし、これだけではあまり検索エンジンとしては役に立ちません。複数の単語やフレーズで検索したいことの方がはるかに多いからです。例えば、your moneyというフレーズを検索したい時のことを考えましょう。your big moneyやyour bitcoin moneyなどではなく、your moneyというフレーズを検索するため、多くの検索エンジンでは””(ダブルコーテーション)で括って、”your money”として検索します。こうすると、間に別の単語が入ったフレーズは検索されません。

図のインデクスを見ると、yourは2、3、3にあり、moneyは1、2、3にあることがすぐにわかります。ということは2ページと3ページにyour moneyというフレーズが含まれている可能性があることがわかります。

しかし、your moneyというフレーズがあるかどうかはどうやって知ればいいのでしょうか。



(3つのウェブページがあると考え、その索引を作る。検索エンジンは、この索引を検索して、求めるページを検索結果として返す。)

検索エンジンの設計者たちは、
インデクスの作り方を工夫

この難問を解決するために、検索エンジンの設計者たちは、インデクスの作り方を工夫しました。それは単に単語が出現するページ数だけをインデクスするのではなく、その単語がページの中で何番目に登場する単語であるかも記録しておくということでした。例えば、moneyは1ページ目の3番目に登場する単語なので「1/3」などと記録します。

これで「your money」を検索してみましょう。yourとmoneyの両方が登場するページは2ページ目と3ページ目です。2ページ目では「2/9、2/5」となっていて、それぞれ9番目と5番目に登場します。ここから「your money」という連続したフレーズになっていないことがわかります。

3ページ目では「3/2、3/6、3/3」となっていて、3/2、3/3が連続したフレーズであることがわかります。ここから検索結果として、3ページ目を返せばいいのです。



(検索エンジンの索引には、ページ数だけでなく、その単語がページ内の何番目に登場するかも記録されている。検索した複数の単語の位置関係を知ることができる。単語が近くにあるほど関連性が高いと推測することができる。)

また、コーテーションで囲まず、単に「time money」と検索した場合はどうなるでしょうか。これは必ずしも「time money」というフレーズでなくてもかまわないものの、timeとmoneyが強く関連しているページを検索したいという意味です。検索をしてみると「1/1、1/3」、「2/2、2/5」が見つかります。1ページ目の単語の距離は2で、2ページ目の単語距離は3になります。ここから1ページの方が、検索をした人の意図に適っているのではないかと推測ができます。

インデクスに単語の位置も
記録するというのは、
検索エンジンならではのアイディア

このようなインデクスに、単語の位置も記録するというのは、検索エンジンならではのアイディアです。ただし、先ほど触れたようにグーグルが最初に思いついたわけではなく、先行した検索エンジン各社がさまざまなアイディアを出していきました。ウェブを記述しているHTMLには、メタタグを使ってタイトルや本文という文章の構造を指定することができます。このようなメタタグも単語として扱うことができるので、インデクスに記録をしていけば、さらに複雑な検索に対応することができるようになります。

それでもやはりグーグルの登場は、検索エンジンの世界を変えました。ウェブ間のリンクを利用して、各ウェブサイトの「有用度」を数学的に算出するページランク技術を開発します。これにより、検索結果を有用度順に並べ替えることができるようになり、検索すれば上位に求めるウェブが表示される精度の高い検索エンジンが生まれます。

それでも、検索エンジンの仕組みの大元は、書籍の索引であり、それを改良することで発展してきたのです。

原稿:牧野武文(まきの・たけふみ)

テクノロジーと生活の関係を考えるITジャーナリスト。著書に「Macの知恵の実」「ゼロからわかるインドの数学」「Googleの正体」「論語なう」「街角スローガンから見た中国人民の常識」「レトロハッカーズ」「横井軍平伝」など。

10分で理解する検索エンジン--書籍の索引から発展した検索エンジンの仕組み

この記事はどうでしたか?

おすすめの記事

キャリアを考える

BACK TO TOP ∧

FOLLOW