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