moshimore Knowledge

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

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

f:id:moshimore:20181127212033p:plain
実際の転置インデックスを実装するために辞書と転置リストの実装方法について考えてみます。
あちらこちらで処理のコスト削減のための策が用意されています。

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

転置インデックスの実装

辞書の実装

辞書(もくじ)は素早く検索したいため、ハッシュや木構造などのデータ構造を用いて、一次記憶装置に格納します。

転置リストの実装

転置リスト(ポスティングリスト)は辞書に比べて、大きいデータ量になるため、二次記憶装置に格納します。
この転置リストには前回のエントリーで触れた単語の位置情報の他にも単語の出現数(TF:Term Frequency)も格納され、検索結果のランキング処理などに用いられます。
例えば、「文書ID_A:出現数:位置情報1:位置情報2:位置情報3:…位置情報x,文書ID_x…」となり、以下のようになります。

辞書 ポスティングリスト
I P1:1:1,P2:1:1
search P1:1:3,P2:1:2

他にも必要であれば日付などの情報を持たせたりします。

転置インデックスを用いて検索する

ブーリアン検索

検索キーワードの全てが含む検索方法のことをAND検索などと呼びますが、この論理演算子(ANDやORやNOT)を用いた検索のことをブーリアン検索と呼びます。
また、論理演算子のことをブーリアンオペーレータ、ブーリアン検索を行う検索モデルのことをブーリアンモデルと呼びます。

転置インデックス用いた検索処理の流れ

転置インデックス用いたAND検索の処理は、次のような流れになります。

  1. ポスティングの比較回数をできるだけ少なくするために「検索キーワード」を「ポスティングリスト」にある「ポスティング」の件数の「昇順」に並び替えます。
    例えば、検索キーワードが「search engine」の場合は、「engine search 」に並び替えます。

    engine P1:4 件数
    Google P2:5 1件
    I P1:1,P2:1 2件
    in P2:4 1件
    keyword P2:3 1件
    like P1:2 1件
    search P1:3,P2:2 2件


  2. 「検索キーワード」を1件取り出して、その「ポスティングリスト(1)」を取得します。
    例えば、検索キーワードが「engine search」の場合は、「engine」のポスティングリストを取得します。

    engine P1:4


  3. (※)その次の「検索キーワード」を1件取り出して、その「ポスティングリスト(2)」を取得する
    例えば、検索キーワードが「engine search」の場合は、「search」のポスティングリストを取得します。

    search P1:3,P2:2


  4. 「ポスティングリスト(1)」と「ポスティングリスト(2)」の両方にポスティングが含むポスティングリストを新しく作成します。
    このとき、新しく作成したポスティングリストは「ポスティングリスト(1)」へ格納します。

    P1:3,P1:4

  5. 他にも「検索キーワード」がある場合は(※)の処理へ戻ります。
  6. 作成した「ポスティングリスト(1)」のデータをランキング処理やソート処理にかけます。
  7. 「ポスティングリスト(1)」を検索結果として表示します。

    I like search engines.


関連度の計算方法

ウェブ検索において、検索結果のランキング処理やソート処理には、コサイン類似度やOkapi BM25などが用いられます。

ベクトルのなす角 - Wikipedia
Okapi BM25 - Wikipedia

情報検索における検索

全文検索の学術分野においては、検索キーワードが含んでいない文章だとしても、キーワードとの関連度が高い場合には、その文章を検索結果に表示することがあります。
その際に検索処理のコストを抑えるため、指定のキーワードが1つだけは含む文章に絞り込んでいたりします。

今日のまとめ

  • ポスティングリストにはポスティングや位置情報だけでなく、ランキング処理に必要な情報を持たせておく必要がある

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

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

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