moshimore Knowledge

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

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

f:id:moshimore:20181127212033p:plain
引き続き「検索エンジンはいかにして動くのか」について、書籍「検索エンジン自作入門」に則って進めていきます。

前回のエントリーの続きになります。
内容が通じない場合があるので、先にこちらをご覧ください。
knowledge.moshimore.jp

転置インデックスを深く知る

転置インデックス=辞書+転置リスト

前のエントリーで詳しく説明した転置インデックスは、辞書(もくじ)とポスティングリスト(ページ番号)から成り立ってることが分かりました。

辞書(もくじ) ポスティングリスト(ページ番号)
engine P1
Google P2
I P1,P2
in P2
keyword P2
like P1
search P1,P2

これによって、辞書が引ければ、その単語に対応するポスティングリストが取得できて、リストから文書IDを取得できるようになります。

転置インデックスから単語を探す

もし、1つの単語だけでなく、複数の単語で検索したい場合は、どうすれば良いでしょうか。

例えば、「search engine」を検索したい場合は、「search」と「engine」両方のポスティングリストを取得します。

search P1,P2
engine P1

この2つのリストから両方に含まれている文書IDは、「P1」であることが分かります。

転置リストに単語の位置情報を加える

これまでに作ってきた転置インデックスでは、取得した文書IDにあるテキストのどの部分にそのキーワードがあるのか分かりません。
それが分かるように「文書ID:位置情報(先頭から何番目の単語か)」という風に表現してみましょう。

  • I like search engines.
ページ1(P1) I like search engine
位置 1 2 3 4
  • I search keywords in Google.
ページ2(P2) I search keyword in Google
位置 1 2 3 4 5
辞書(もくじ) ポスティングリスト(ページ番号)
engine P1:4
Google P2:5
I P1:1,P2:1
in P2:4
keyword P2:3
like P1:2
search P1:3,P2:2

これで転置インデックスに単語の位置情報が加わりました。

転置インデックスからフレーズを探す

先ほど、「検索エンジン」に関するテキストを検索したくて「search engine」というキーワードで検索をした結果、「P1」の文書IDを無事に取得できました。
もし、ページ3に「I search for a gas station because my car's engine doesn't start.」というテキストがあった場合、どうなるでしょうか。
このテキストにも「search」と「engine」両方が含んでいるため、検索結果に上がってきます。

しかし、このテキスト(車のエンジンがかからないので、ガソリンスタンドを探します。)は、「検索エンジン」に関する内容ではありません。
この時に威力を発揮するのが単語の位置情報です。
ページ3の「search」は2番目、「engine」は10番目に出現します。

検索したい「search engine」は隣り合ったキーワードですが、ページ3は、2番目と10番目で隣り合いません。

ページ1の「search」は3番目、「engine」は4番目なので隣り合っているので、検索結果として正しい内容が取得できました。

日本語文書から転置インデックスを作る

日本語の文を分割する方法

日本語の単語は英語のようにスペースで区切られていないので、単語を取り出すには工夫が必要です。
方法は、次の2種類があります。

  • 形態素解析による分割

例えば、「全文検索エンジン」という文章を「全文」「検索」「エンジン」という風に分割する方法です。

  • N-gramによる分割

例えば、2-gramの場合は、「全文検索エンジン」という文章を「全文」「文検」「検索」「索エ」「エン」「ンジ」「ジン」という風に分割する方法です。

分割方法のトレードオフ

どちらの方法にもメリットとデメリットがあります。

方法 メリット デメリット
形態素解析 ・辞書のサイズを小さくできる場合がある ・検索漏れが生じる *1
N-gram ・検索漏れが生じない ・辞書のサイズが大きくなる
・単語の境界を考慮できない *2

今日のまとめ

  • 日本語の文章の場合、単語間が繋がっているため、英文と同じようには辞書を作れない
  • N-gramで検索漏れが生じないようにしても、意味のない検索結果を取得してしまうことがある

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

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

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

*1:例えば、文章に「チョコレート」という単語があった場合、キーワード「チョコ」で検索できません。

*2:例えば、文章に「東京都」という単語があった場合、「京都」でも検索されます。