３章は、クエリ入力支援について。
辞書
大量のタームが含まれているインデックスから、どのようにクエリのタームを見付けるか。
大きく分けて、ハッシュと木構造の2つのデータ構造がある。
どのような時に、どちらを使えばいいのか？
ハッシュ
クエリのタームをハッシュ化する。
この時、コリジョン(衝突)を避ける。
メリット
- 木構造と比較して、検索がはやい。
デメリット
- 細かな違いを識別できない
- 接頭辞検索ができない
- ボキャブラリが増えると、全てをハッシュ化し直さなければならない。
木構造
メリット
- 接頭辞検索が可能
デメリット
- ハッシュと比較して、検索が遅い。
以下に代表的な木構造を挙げる。
2分探索木
最も単純な2分木。
バランスを再び整えるにはコストがかかる(リバランス問題)。
B木
常にバランスされている。
ワイルドカード
これをどう扱うべきか。
以下では、ワイルドカードの出現位置で場合分けして説明する。
mon*
m→o→nとたどり、そこから先の子ノードを全部取る。
*mon
今度は逆からn→o→mとたどる。
m*nchen
上記の2つを適用し、それらのインターセクションを取る。
しかしこれは非常にコストがかかる。
そこで考えられた2つのインデックス手法。
Permuterm indexes
クエリを回転させ、ワイルドカードが末尾に現れるように変更する。
このように、全ての回転パターンを作成し、元のタームへリンクする。
サイズが非常に大きくなってしまう(B木の4倍以上)。
kグラム indexes
kグラムを全て列挙する。
例えば、
April is the cruelest month
は、以下のようになる。
$a ap pr ri il l$ $i is s$ $t th he e$ $c cr ru ue el le es st t$ $m mo on nt h$
各タームのkグラムを作る。
Permuterm indexesよりもメモリ効率がよい。
デメリットとしては、false alarms(誤報)を含むことが挙げられる。
例えば、
mon*
は
$m AND mo AND on
となるが、これにはMOONも含まれてしまう。
よってfalse alarmsをフィルタリングしなければならない。
この点においては、フィルタリングを全く必要としないPermuterm indexesの方が優れているといえる。
どの手法にせよワイルドカードは非常にコストがかかるので、実際にはあまり使われていない。
クエリ修正
クエリのタイポを修正する手法についていくつか紹介する。
編集距離
基本的なアイデアとして、ミススペルと本当のスペルとの距離を考え、この距離が最小となるものを正しいスペルとして修正する。
この距離のことを編集距離といい、2つの文字列がどの程度異なっているかを示す。
編集距離として最もよく使うものにレーベンシュタイン距離というものがあり、文字の挿入・削除・置換で一方を他方に変形するための最小の手順回数で定義する。
dogとdoなら1(回),catとactなら2(回)といった具合。
上の操作に文字の転移(transposition)を加えた、Damerau-レーベンシュタイン距離というものもある。
これを用いると、cat-actは1(回)となる。
kグラムインデックス
全タームに対してkグラムを作成し、最もヒットする回数が多いものを正しいスペルとする。
以下の例(bord)ならabroad,boardroom,boarderが候補となる。
文脈依存
クエリのそれぞれのタームを修正し、それらを組み合わせたフレーズの中で最も出現頻度の高いものを正しいクエリとする。
例として、'flew form munich'を考える。flewの修正候補としてはfleaなど7種類、formの候補としてはfromなど20種類、munichの候補としてはmunchなど3種類あるとする。
そして、flea form munich,flew from munich,flew form munch…というように、組合せ得る全ての通りを順に試していく。
この中でflew from munichが最もヒットするので、これを修正クエリとする。
しかし、上の例だと7*20*3パターンの候補を作成しなければならず、コストがかかる。
Soundex
上記のものは全て文字に着目して修正していたが、これは、音に着目して修正する。
目的の言葉と同じような発音の語に間違えてしてタイポしてしまったものを修正できる。
以上クエリ修正について説明したが、クエリ修正は潜在的にコストが高いので、クエリにマッチするドキュメントがほとんどない場合のみ修正を行うといったような、インタフェース上の工夫が必要である。
