stop-the-world

takuya-a のブログ

Information Retrieval and Web Search まとめ(3): クエリ処理

前回はインデックスを構築する方法を説明した。今回から、クエリをどうやって処理するのか説明していく。

この記事は Information Retrieval and Web Search Advent Calendar 2020 の3日目の記事です。

adventar.org

AND クエリ

  • Brutus AND Caesar というクエリを考える
    • 辞書から "Brutus" を探す
      • そのポスティングリストを取得する
    • 辞書から "Caesar" を探す
      • そのポスティングリストを取得する
    • 2つのポスティングリストを「マージ」する（文書集合の共通部分をとる）

f:id:takuya-a:20201203234915p:plain
"Brutus" と "Caesar" のポスティングリスト

  • 2つのポスティングリストを同時に走査する
    • 2つのポスティングリストのエントリの総数に線形の時間でできる
    • リストの長さがそれぞれ x, y なら、マージ処理は O(x+y) 回の操作で実行できる
  • 重要：ポスティングリストは docID でソートされている！
  • 2つのポスティングリストは以下のアルゴリズムでマージできる

f:id:takuya-a:20201203235123p:plain
IIR p.11 Figure 1.6 2つのポスティングリストのマージアルゴリズム

ブーリアン検索モデル

  • ブーリアン検索モデル (boolean retrieval model) で論理式のクエリ（ブーリアンクエリ）を実行できる
    • ブーリアンクエリ (boolean query) はクエリのタームを AND, OR, NOT で接続したもの
      • 文書を単語の集合 (set of words) とみなす
      • 条件にマッチするかしないかのどちらか
    • 情報検索でもっともシンプルなモデル
  • 今も使われている検索システムの多くはブーリアンである
    • メール、macOS Spotlight など
  • 例
    • Brutus AND NOT Caesar
    • Brutus OR NOT Caesar
    • (Brutus OR Caesar) AND NOT (Antony OR Cleopatra)
    • これらは線形時間で実行できるだろうか？さらに高速に処理するためには？

クエリ最適化

  • n タームをつないだ AND クエリを考える
  • 例：クエリ Brutus AND Calpurnia AND Caesar
  • Q: 複数のポスティングリストをどの順番でクエリ処理するとよいだろうか？

f:id:takuya-a:20201203235458p:plain

  • A: 数が少ないものから順番に処理する
    • 小さい集合から始めて、それをさらに少なくしていく
    • このためにターム辞書には文書頻度（そのタームを含んでいる文書数）を保存しておく
    • (Calpurnia AND Brutus) AND Caesar というふうにクエリを実行する
  • さらなる最適化
    • (madding OR crowd) AND (ignoble OR strife) というクエリを考える
    • すべてのタームについて、文書頻度を取得する
    • それぞれの OR の結果のリストの長さを推定する
      • 単純に2つのポスティングリストの文書頻度を足したもので推定（保守的）
    • 推定した長さが短いものから順番に処理する

講義資料

参考資料