stop-the-world

takuya-a のブログ

Information Retrieval and Web Search まとめ(4): フレーズ検索と位置インデックス

前回はシンプルな AND クエリと、その最適化について紹介した。今回は、フレーズ検索を実現する方法について説明する。

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

adventar.org

フレーズクエリ

  • "stanford university" のようなフレーズのクエリに回答したい
    • "I went to university at Stanford" にはマッチさせない
  • そのためには <term:docs> というポスティングリストの構造では不十分
    • docID だけではなく、追加の情報が必要

2ワードインデックス

  • フレーズ検索の最初のアプローチとして、 2ワードインデックス (biword index) を考える
  • "Friends, Romans, Countrymen" というテキストがあったとすると、そこから以下の2ワード (biword) の組み合わせをつくる
    • friends romans
    • romans countrymen
  • これらの2ワードを辞書のタームとする
    • これにより、2つの単語によるフレーズクエリが可能になる
  • さらに長いフレーズクエリは、それを2ワードに分解する
    • 例:"stanford university palo alto" は以下のブーリアンクエリとして実行する
    • stanford university AND university palo AND palo alto
  • 2ワードインデックスの問題点
    • 文書そのものがないと(転置インデックスだけでは)フレーズに本当にマッチしているかはわからない
      • 2単語の組み合わせに関してはマッチしていることがわかるが、それ以上の組み合わせは保証できない
      • 偽陽性 (false positive) が発生しうる
    • 辞書サイズが非常に大きくなる
      • 単語の組み合わせになるのでユニークタームの数が組み合わせ爆発する
      • 3ワード以上のものに関してはもはや実現不可能

位置インデックス

  • 位置インデックス (positional index) では、ポスティングに docID とそのタームが出現した位置 (position) を、以下のように保存する:
<ターム, タームの文書頻度;
  docID1, 文書1内のターム頻度: <position1, position2 ...>;
  docID2, 文書2内のターム頻度: <position1, position2 ...>;
... >
  • ターム tobe の位置インデックスの例:

f:id:takuya-a:20201204211412p:plain
(IIR p.41 Figure 2.11) 位置インデックスの例

  • 文書 4 にはフレーズ "to be or not to be" が入っている可能性がある
    • ("or", "not" についてはこの図だけではわからないが)
  • 文書レベルでマージアルゴリズム再帰的に使うことでフレーズクエリが可能

位置インデックスを使ったフレーズクエリ

  • フレーズクエリ to be or not to be を考える
  • まず、それぞれのターム to be or not転置インデックスのエントリを取得する
  • to be or not to be のすべてのポジションで、マージアルゴリズムを実行する
    • to
      • 2: <1, 17, 74, 222, 255>; 4: <8, 16, 190, 429, 433>; ...
    • be
      • 1: <17, 19>; 4: <17, 191, 291, 430, 434>; ...

近接クエリ

  • 近接クエリ (proximity query) はフレーズクエリの一般化で、以下のようなクエリ
    • employment /3 place
      • /3 は「3単語以内に」という意味(距離)
      • この場合、 "employment at the place" というフレーズにもマッチする
  • 位置インデックスを使うことでこのようなクエリに答えられる
    • 2ワードインデックスでは不可能

f:id:takuya-a:20201204212218p:plain
(IIR p.42 Figure 2.12) 近接クエリを実行するアルゴリズム。`k` は近接クエリにおける距離で、`p1` `p2` はそれぞれ位置インデックスにおけるポスティングリストである。

位置インデックスのサイズ

  • 位置インデックスにすることで、必要な容量は当然大きくなる
    • 追加で出現位置を保存するので
  • にも関わらず、現在の標準的な検索システムでは位置インデックスが使われている
    • フレーズ検索や近接検索が有用なため
  • タームが出現するごとにその位置を保存しなければならないので、平均的な文書長が大きいコレクションでは、それに比例してインデックスサイズも大きくなる
    • 平均的な Web ページのターム数は 1000 以下
    • 本などでは 10 万語を超える
    • 文書長が 100 倍になれば位置情報も 100 倍
  • 大ざっぱな基準
    • 位置インデックスはそうでないインデックスより2~4倍大きくなる
    • 位置インデックスのサイズは元のテキストの 35~50%
      • 英語のような言語で書かれたテキストの場合

2ワードインデックスと位置インデックスの組み合わせ

  • "Michael Jackson" や "Britney Spears"、 "The Who" のような特定のクエリに対しては、位置インデックスで処理するのは非効率
  • Williams et al. (2004) は混合インデキシングの洗練された手法を従来手法と比較
    • 典型的な Web のクエリにおいて、単純に位置インデックスを使った方法より 4 倍速かった
    • 位置インデックスよりも 26% の余分なスペースが必要

講義資料

参考資料