10章では、XMLにおける探索において。
主なサーチエンジンは、構造化されていないテキストが検索対象だが、ここでは、構造化されているドキュメント(ここではXML)における検索を考える。
以下の例で説明する。
Shakespeare Macbeth Macbeth’s castle Will I with wine and wassail ...
XML検索
1.ドキュメントのどの部分を検索結果として返せばよいのか
どの部分がクエリにマッチする結果であるかを決めるのは難しい。
そこで、以下のstructured document retrieval principleというものがある。
検索システムは、常にクエリに対応して最も明確な部分を結果として返すべきである。
しかし、実際にこの原則を満たすようにアルゴリズムを実装できるかどうかは別問題。
2.ドキュメントのどの部分をインデックスにするか
以下の4つのアプローチがある。
- オーバーラップのない擬似的なドキュメントへとまとめる
欠点は、1つの木が他と切り離されているため、それだけでは意味をなさない可能性があること。
根要素(root elements)のみを扱い、検索結果への後処理で子要素を見付ける。
欠点は、ある要素の適合性とその子要素の適合性は一致しないことがあること。
トップダウンとは逆に、葉要素(leaf elements)のみを扱い、検索結果への後処理で親要素を見付ける。
欠点は、ある要素の適合性とその親要素の適合性は一致しないことがあること。
- 全ての要素をインデキシング
欠点は、意味のあまりない要素が多いため、かなり冗長になること。
以上4つのアプローチにはそれぞれに欠点がある。
3.ネスト要素をどうするか
ネスト要素は冗長性を引き起こすため、要素集合を制限するのが普通である。
VSM
上で見たように、XMLの検索には様々な問題点があるので、これらにVSMで対応する。
VSMの各次元を、XMLパスとタームのペア[tex:
すなわち、これまでのようにタームのみに着目するのではなく、構造にも着目する。
: クエリパス
: ドキュメントパス
: クエリパス上のノード数
: ドキュメントバス上のノード数
破線は、その間に任意のノードを挿入可能であることを意味する。
は以下のようになる。
- = 4/4 = 1.0
- = 0
- = 3/4 = 0.75
- = 3/5 = 0.6
XML検索の評価
ここでは、XMLにおける標準的なベンチマークであるINEX(INitiative for the Evaluation of XML retrieval)について説明する。
INEXには以下の2つのタイプがある。
- CO(content-only)
ドキュメントの内容のみに着目する。言ってしまえば今まで通り。
- CAS(content-and-structure)
ドキュメントの内容と構造に着目する。当然CAより評価は複雑になる。
CASでは、内容と構造の2次元で適合性を評価する。
まず、内容(rel)は以下の4段階に分ける。
- 3…非常に適合
- 2…まあまあ適合
- 1…少し適合
- 0…不適合
次に、構造(cov)を以下の4段階に分ける。
- E…メイントピックをとらえており、情報量が十分
- S…メイントピックはとらえているが、情報量が不十分
- L…関係のあるトピックはとらえているが、メイントピックではない
- N…関係のあるトピックをとらえていない
そしてこのQの値を、適合率・再現率・F値などの導出に用いる。