こんにちは、 @kz_morita です。

今回は，検索に使われる転置インデックスについてまとめます．

検索におけるインデックスとは

情報検索システムの目的は，ユーザーが入力したクエリに関連する文書を見つけることにありますが，文書が大量にある場合は全文検索では到底探しきれないためインデックス付けを行います．

インデックスをつける際は，どのような用語がどの文書に現れるかを知る必要があります．

そこで，文書と用語を行列で表す方法があります．具体的には以下のようなものになります．

文書を以下のようなものだと仮定します．

• 文書1: I have a pen.
• 文書2: This is a pen.
• 文書3: I am grad to see you.

すると，出てくる単語は，I, have, a, pen, This, is, am, grad, to, see, you となります．これらの対応表を書くと以下のとおりです． (現れるところは 1 それ以外は 0)

上記を結合行列といいます．

上記は特徴として，ほとんどの要素が 0 (Sparse な行列) なため，この形式で持つのは非効率です．

そこで，各用語ごとに，どの文書に含まれているかという文書ID のリストを持つような形式が取られます．

以下のような形です．

• I => 1, 3
• have => 1
• a => 1, 2
• pen => 1, 2
• This => 2
• is => 2
• am => 3
• grad => 3
• to => 3
• see => 3
• you => 3

この 左側の用語集を辞書とよび，右の文書IDのリストをポスティングリストと呼びます． また，これらは転置インデックスとも呼ばれます．（もとの結合行列を転置した形なのでそうよばれているのだと思ってます）

基本的には，このような転置インデックスを用いて検索が行われます．

インデックスを用いた検索

では，実際に検索をするときにはどのような動きになるかというと以下のようになります．

• I という単語で検索しようとする．
• 辞書に I という用語が見つかる
• I に紐付いているポスティングリストを見ると，文書 1 と 文書 3 が該当
• これらの文書を返す

もう一つ AND 検索の例も考えます．

たとえば，I AND pen という検索クエリを考えます．

I に紐づく文書の集合は，1, 3 で，pen に紐づく 文書の集合は，1, 2 になります．

AND 検索なので，これらの集合の積を取れば良いため，結果の文書は，1 のみとなります．

まとめ

今回は，検索のシステムにおいて インデックスがどのように用いられるか簡単に説明しました．

が，これだけではおそらく全く使い物にならないシステムで以下のようなことも考慮する必要があります．

今後の課題としては，

• 辞書をどのように作るか？（用語の表記ゆれなどをどのように扱うか？)
• スペルミスを考慮した検索 (もしかして oo ?)
• 用語の頻度なども考慮して文書を重み付け
• フレーズ検索 (Googe検索などで "" でくくるやつ) などの検索する用語の位置関係を考慮した検索
• 検索結果のランク付け

次回は, 1 番目の 辞書をどのように作るかについてまとめようと思います．

参考

• 情報検索の基礎