前章ではBoolean検索についてまとめたが、ドキュメントもタームもそのままも状態では用いることができない。
そこでそれらの問題点、前処理の方法を考えることにする。
ドキュメント
- フォーマットの問題
pdf, word, excel, html etc...
フォーマットごとに処理する必要がある。
- 言語の問題
1つのドキュメントに複数の言語が使用されている場合がある。
- 文字セットの問題
ターム(自然言語処理)
Boolean検索を用いるために、タームの正規化を行う。
例えば、U.S.AとUSAは同じものとして扱いたいといったもの。
しかし、windowsとWindowsは異なるものとして扱いたいといったように、簡単にはいかなそうである。
以下では、処理順に見ていく。
Tokenization
まず、ドキュメントをトークンに区切る。
単純にスペースで区切る、というだけではうまくいかないものも多い。
以下に問題点を挙げる。
- 区切りの問題
- ハイフンの問題
State-of-the-art,co-education etc...
-
- スペースの問題
data base,San Francisco etc...
- 数字(日付)の問題
3/20/91,Mar 20, 1991 etc...
- 言語固有の問題
例えば日本語だと、単語の区切りがなく英語みたいにうまくいかない。
これが日本語の形態素解析が難しいと言われる所以。
ストップワードの除去
a, an, and, are, as, at, be, by, for etc...
これらの単語はドキュメントを特徴付けないので除去する。
多くのWeb検索システムではストップワードのインデックスを持っている。
Lemmatization(見出し語化)
am, are, is → be
car, cars, car’s, cars’ → car
etc...
語尾変化や派生に対応。
Stemming(ステミング)
邪魔な語尾を切る。
caresses → caress
cats → cat
etc...
Skip pointers
転置インデックスのインターセクションの際の効率化を図るためのアルゴリズムを考えることにする。
そこで、リストを逐次的にたどるのではなく、何個かごとにスキップしながらたどっていく。
１度にスキップする個数とスキップする回数はトレードオフである。
- １度にスキップする個数を少なくすると、沢山スキップを行える。
- １度にスキップする個数を多くすると、なかなかスキップが行えない。
１度にどの程度スキップするのがよいか？
- リストの長さが
の時、
インデックスが静的な場合はスキップは容易いが、動的な場合はなかなか厳しい。
フレーズクエリ
Web検索でのクエリの約10%はフレーズである。
'stanford university'はフレーズとして処理したい！
→しかし単純なBoolean検索では、stanford AND universityとして処理される。
そこで、フレーズ検索のための様々なインデックスを考える。
Biwordインデックス
クエリを2タームずつに分け、それらを全てフレーズとして扱う。
例えば、
A B C D
というクエリがあれば、
'A B' AND 'B C' AND 'C D'
というように変換する。
しかし、これでは2語のフレーズしか扱えない。
そこで…
拡張Biwordインデックス
NX*Nをフレーズとして扱う。(N:名詞 X:前置詞)
例えば、catcher in the rye (N X X N), king of Denmark (N X N) など
しかし、これら2つは以下のような問題点のため、実際にはほとんど使われていない。
- False alarms(誤報)を含む
- タームのボキャブラリサイズが大きくなる
そこで、より効率的なインデックスとして、以下のものがある。
Positionalインデックス
上記に加えて、タームの出現位置情報も考慮。
BiwordインデックスとPositionalインデックスを組み合わせて使うといいかも。
