Information Retrieval and Web Search まとめ(4): フレーズ検索と位置インデックス
前回はシンプルな AND クエリと、その最適化について紹介した。今回は、フレーズ検索を実現する方法について説明する。
この記事は Information Retrieval and Web Search Advent Calendar 2020 の4日目の記事です。
フレーズクエリ
- "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ワードに分解する
- 2ワードインデックスの問題点
位置インデックス
- 位置インデックス (positional index) では、ポスティングに docID とそのタームが出現した位置 (position) を、以下のように保存する:
<ターム, タームの文書頻度; docID1, 文書1内のターム頻度: <position1, position2 ...>; docID2, 文書2内のターム頻度: <position1, position2 ...>; ... >
- ターム
to
とbe
の位置インデックスの例:
- 文書 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ワードインデックスでは不可能
位置インデックスのサイズ
- 位置インデックスにすることで、必要な容量は当然大きくなる
- 追加で出現位置を保存するので
- にも関わらず、現在の標準的な検索システムでは位置インデックスが使われている
- フレーズ検索や近接検索が有用なため
- タームが出現するごとにその位置を保存しなければならないので、平均的な文書長が大きいコレクションでは、それに比例してインデックスサイズも大きくなる
- 平均的な Web ページのターム数は 1000 以下
- 本などでは 10 万語を超える
- 文書長が 100 倍になれば位置情報も 100 倍
- 大ざっぱな基準
- 位置インデックスはそうでないインデックスより2~4倍大きくなる
- 位置インデックスのサイズは元のテキストの 35~50%
- 英語のような言語で書かれたテキストの場合
2ワードインデックスと位置インデックスの組み合わせ
- "Michael Jackson" や "Britney Spears"、 "The Who" のような特定のクエリに対しては、位置インデックスで処理するのは非効率
- Williams et al. (2004) は混合インデキシングの洗練された手法を従来手法と比較
- 典型的な Web のクエリにおいて、単純に位置インデックスを使った方法より 4 倍速かった
- 位置インデックスよりも 26% の余分なスペースが必要