moshimore Knowledge

アプリ開発・紹介とメモ書き、日々の日記。

検索エンジン自作入門 - 検索エンジンはいかにして動くのか(1)

f:id:moshimore:20181127212033p:plain
このエントリーは書籍「検索エンジン自作入門」に則って実際に検索エンジンを作っていきます。
途中で挫折してしまいそうですが、少しずつ読み進めていきたいと思います。

検索エンジンの構成を理解する

検索エンジンとは

検索エンジンというと、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.

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

もくじ ページ番号
engine P1
Google P2
I P1,P2
in P2
keyword P2
like P1
search P1,P2

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

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

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

ページ番号 I like search engine
P1

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

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

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

ページ番号 I like search engine keyword in Google
P1 - - -
P2 - -

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

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

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

  • 文書ID

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

  • 辞書

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

  • ポスティング

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

  • ポスティングリスト

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

今日のまとめ

検索エンジンは、割と地味な方法でインデックスを作ってることが分かりました。
ただこれは、英単語だからこそ成功していて、日本語の場合にはなかなか難しい方法になります。

続きは、以下のエントリーです。
knowledge.moshimore.jp

書籍の内容は、以下のエントリーで紹介しています。
knowledge.moshimore.jp

以上、検索エンジン自作入門 - 検索エンジンはいかにして動くのか(1)でした。