Information Retrieval and Web Search まとめ(9): ワイルドカード検索
前回は、ポスティングリストの圧縮のための様々な符号化について説明した。今回はワイルドカード検索についてまとめる。
この記事は Information Retrieval and Web Search Advent Calendar 2020 の9日目の記事です。
ワイルドカードクエリ
- ワイルドカードクエリ (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
のようなワイルドカードクエリは?
ワイルドカードクエリのクエリ処理
- ワイルドカードクエリに合致するすべてのタームを列挙する
- 列挙された各タームに対して、ポスティングを検索する
- 大量の 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 倍になる
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$
- 例: "april" の 2-gram (bi-gram) は以下のようになる
- それらの k-gram からタームへの転置インデックスを作る
- ポスティングリストとは別のもの
- k-gram で引くと、それにマッチするすべてのタームが取れるようになる
- 複数のタームがある場合、タームは辞書順で並べる
講義資料
- Wildcard queries and Spelling Correction (pdf)
- Wild-card queries
参考資料
- IIR chapter 3
- MG section 4.2