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

転置インデックス＝辞書＋転置リスト

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

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

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

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

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

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

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

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

• I like search engines.

• I search keywords in Google.

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

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

先ほど、「検索エンジン」に関するテキストを検索したくて「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番目なので隣り合っているので、検索結果として正しい内容が取得できました。

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

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

• 形態素解析による分割

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

• N-gramによる分割

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

分割方法のトレードオフ

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