IIR輪講復習 #3 Dictionaries and tolerant retrieval (前半)
お知らせ たつをさんによる補足情報 復習資料おきば http://chalow.net/clsearch.cgi?cat=IIR http://bloghackers.net/~naoya/iir/ppt/
参考 http://www-csli.stanford.edu/~hinrich/information-retrieval-book.html 本資料は書籍の輪読会に向けたサマリ 資料内で一部上記ドキュメントからの引用あり
3章のテーマ 正確にクエリを組み立てられないときに、ユーザーを助けるための機能 ワイルドカードクエリ typo 修正 (もしかして)
第3章前半の概要 辞書 (dictionary) 検索のためのデータ構造 ワイルドカードクエリの処理方法
前振り: standard inverted index 1章や2章で作った転置インデクス each vocabulary term has a postings list with the documents in the collection.
辞書検索のためのデータ構造
辞書から語句を探す
ハッシュ or 探索木 単純なハッシュは向いてない 探索木が良い クエリの微妙な間違いを扱いづらい ワイルドカードの実現が難しい Web 検索だとサイズが大きすぎる 探索木が良い binary search tree (二分探索木) O(log m) ~ O(m) / Rebalancing 問題 B-tree (B木) 多分木の平衡木 O (log m) 一般的に外部記憶装置 (ブロックデバイス) 上での探索に向いている
Binary Tree
B-Tree
B木の解説
ワイルドカードクエリ
ワイルドカードクエリ Goo* 役立つ場面 Goo, Good, Google, Goonies ... クエリのスペルが正確に分からないとき スペルが複数の変形を含んでいる 検索エンジンの処理が不透明なので「とりあえず全部」 外国語
mon* trailing wildcard query m, o, n とツリーを辿る そこから先の子ノードを全部取る mon* に対する term 群 W が決まる 転置インデックスから W に含まれる term に紐尽くドキュメントを取得する
* 一つに対する単純なアプローチ *mon se*mon Reverse B-tree を作って辿る lemon → root-n-o-m-e-l se*mon se を通常の B-tree から辿る → 集合W mon を Reverse B-tree から辿る → 集合R W ∩ R を取る (intersection)
もっと複雑な * に対するアプローチ fi*mo*er Permuterm indexes k-gram indexes for wildcard queries
Permuterm (順序入れ替え語) index hello$ を回転させてすべての回転パターンを作り、オリジナルにリンクする
Permuterm index からの探索 m*n → m*n$ → n$m* n$m* は trailing wildcard query。n$m* をツリーから探す
Permuterm Index の弱点 辞書が非常に大きくなる 全 term の回転を作ったら当然巨大
K-gram indexes for wildcard queries castle $ca, cas, ast, stl, tle, le$ 単語境界
k-gram index 全 term の k-gram を作る 各 term は k-gram からポイントされる
k-gram index からの探索 re*ve post-filtering $re AND ve$ relive, remove, retrieve にヒット post-filtering red* は $red AND red のため retired が引っかかる。 red* ではないので、除外する。
ワイルドカードクエリは高コスト コストが高い Advanced な UI からしか使えないようにしている例が多い 特別なインデックスを引く フィルタする 転置インデックスを引く Advanced な UI からしか使えないようにしている例が多い 通常の機能に含めるとユーザーが意図せず * を使って、検索エンジンが過負荷になる
3.3 Spelling correction へつづく...