検索エンジン自作入門 – 検索エンジンはいかにして動くのか（１）

検索エンジンとは

検索エンジンというと、GoogleやBingなどのウェブ検索がまず頭に思い浮かびますが、それ以外にもパソコンのOSに内蔵されているファイル検索やメールアプリの機能としてメール検索など、様々な用途で使われています。
今回のこの書籍では、予め用意されたテキストからなる文章の全部の文に対して検索を行う「全文検索」の検索エンジンの実装をしていきます。

検索エンジンを構成するコンポーネント

検索エンジンは、一般的に次の4つのコンポーネントから成り立っています。

• インデックス管理器（Index Manager）

本で表すと「もくじ」の部分になります。
「もくじ」がなかったら、本の中から目的のキーワード（文章）に辿り着くまで、先頭から順に読んでいかねばなりません。

• インデックス検索器（Index Searcher）

本で表すと「もくじから目的のキーワードを探す作業」の部分になります。
また、キーワードに合致した文章が一番有力なのか判断してランク付けなどを行い、ソートします。

• インデックス構築器（Indexer）

本の中からキーワードを抜き出していき、もくじを作成する部分になります。

• 文章管理器（Document Manager）

本の内容（文章）を管理したり、保存しておく部分になります。

検索エンジンに関連するコンポーネント

上で上げたコンポーネントの他にもウェブ検索だとしたら、各ウェブサイトをクローリングするクローラーなど、様々な関連コンポーネントが存在します。

全文検索の2つの方法

「全文検索」の方法としては、以下の2種類がありますが、当然、もくじがあった方が早く検索できます。
但し、予めもくじを作っておかなければなりません。

• 「もくじ」が存在せず、キーワードをとにかく端から端まで探して、目的の文章に辿り着く方法
• 「もくじ」からキーワードを探して、目的の文章に辿り着く方法

このもくじは、多くの検索エンジンは「転置インデックス」という方法で作成しています。

転置インデックスの仕組み

転置インデックスは、本のもくじと同じようなものと考えておけば問題ありません。

例えば、全部で2ページしかない本があったとして、次の文章が書かれていたとします。

ページ1（P1）：I like search engines.
ページ2（P2）：I search keywords in Google.

これをもくじにすると、次のようになるはずです。
これが転置インデックスです。

転置インデックスの作り方

このもくじを作るにはどうすれば良いでしょうか。

まず、ページ1の文章に存在する単語を抜き出して表にしてみると、次のようになります。

（○は、単語があったことを表しています。）

ここで気をつけておくことは、複数形の英単語を単数形にしている点です。
日本語においても揺らぎ表現のある単語は、直しておいた方が良さそうです。

この表にページ2の文章も追加していきます。

これで完成した表を縦軸の横軸を入れ替えてみると、初めに提示したもくじの表が完成します。
この入れ替えのことを「転置」というため、このインデックスのことを転置インデックスと呼ばれています。

転置インデックスで用いられる用語

次のような用語があります。

• 文書ID

例えば「本のページ番号（「P1」や「P2」）」「メール本文（メールID）」「ウェブサイトのURL」など

• 辞書

上の表で言うと「もくじ」がそれにあたります。

• ポスティング

上の表で言うと「search」だとしたら、「P1」や「P2」の単体がそれにあたります。

• ポスティングリスト

上の表で言うと「search」だとしたら、「P1 P2」のリストがそれにあたります。