stop-the-world

takuya-a のブログ

Information Retrieval and Web Search まとめ(9): ワイルドカード検索

前回は、ポスティングリストの圧縮のための様々な符号化について説明した。今回はワイルドカード検索についてまとめる。

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

adventar.org

ワイルドカードクエリ

  • ワイルドカードクエリ (wild-card query) は、ワイルドカードを表す * をもつクエリ
    • mon*: "mon" で始まるすべてのタームで検索する
      • 二分探索木 (binary search tree)、もしくは B木 (B-tree) で実装できる：
      • mon <= w < moo であるような全てのターム w を取得すればよい
    • *mon: "mon" で終わるすべてのタームで検索する
      • タームの逆順 (backwards) で構築した B 木が必要
      • nom <= w < non であるような全てのターム w を取得する
    • pro*cent のようなワイルドカードクエリは？

f:id:takuya-a:20201209225310p:plain
(IIR p.51 Figure 3.1) 辞書内のタームで構築した二分探索木

ワイルドカードクエリのクエリ処理

  • ワイルドカードクエリに合致するすべてのタームを列挙する
  • 列挙された各タームに対して、ポスティングを検索する
  • 大量の AND 検索が行われる可能性がある
    • 例： se*ate AND fil*er

Permuterm インデックス

  • co*tion のようなタームの中間に * があるクエリ
  • B木を使って co* AND *tion として検索できる
    • このようなクエリは高価
  • アイデア：ワイルドカードクエリを * が最後に来るように変換する
  • Permuterm インデックス
    • $ を各タームの最後に追加する
    • その文字列を1文字回転させて B木にインデックスするのを繰り返す
      • 例：hello --> hello$, ello$h, llo$he, lo$hel, $hello
    • 経験的には、辞書のサイズは 4 倍になる

f:id:takuya-a:20201209225345p:plain
(IIR p.54 Figure 3.3) "hello" の Permuterm インデックス

Permuterm クエリ処理

  • Permuterm インデックスでのクエリ処理の方法
  • 入力されたクエリに $ をつけ、 * が（あれば）最後に来るように回転させる
  • 入力クエリ X --> X$ で検索
    • hello --> hello$
  • 入力クエリ X* --> $X* で検索
    • hel* --> $hel*
  • 入力クエリ *X --> X$* で検索
    • *llo --> llo$*
  • 入力クエリ *X* --> X* で検索
    • *ell* --> ell*
  • 入力クエリ X*Y --> Y$X* で検索
    • h*lo --> lo$h*
  • 入力クエリ X*Y*Z --> X*Z で検索したあとフィルタする
    • h*a*o --> h*o --> o$h* で検索 --> h*a*o にマッチしないタームをフィルタ

k-gram インデックス

  • すべてのタームのすべての k-gram を列挙する
    • 例: "april" の 2-gram (bi-gram) は以下のようになる
      • $a,ap,pr,ri,il,l$
  • それらの k-gram からタームへの転置インデックスを作る
    • ポスティングリストとは別のもの
    • k-gram で引くと、それにマッチするすべてのタームが取れるようになる
    • 複数のタームがある場合、タームは辞書順で並べる

f:id:takuya-a:20201209225419p:plain
(IIR p.55 Figure 3.4) タームの 3-gram インデックスの例

講義資料

参考資料