読者です 読者をやめる 読者になる 読者になる

IIR1章まとめ

Boolean検索

Boolean検索では、Boolean演算子(and,or,not)を用いてクエリを作成する。

例えば、

CAESAR AND BRUTUS

というクエリを投げると、CAESARとBRUTUSというタームを共に含むドキュメントをサーチする。

インデックスとして、以下のような行列を作成する。

出現:1 非出現:0

例えば、CALPURNIAというドキュメントには、Julius Caesar というタームが含まれている。

この行ベクトルを用いて、Boolean演算を実行する。

例えば、

BRUTUS AND CAESAR AND NOT CALPURNIA

というクエリなら、

110100 AND 110111 AND 101111 = 100100

というように実行できる。

ただし!

ドキュメントセットが大きい場合、非常に大きな行列になるので、メモリにのらない。


しかし行列の要素はほとんど0なので、1だけを記録するインデックスにしよう。

これがいわゆる転置インデックス(Invarted Index)である。

以下のようなものである。

例えばBrutusというタームは、ドキュメント1,2,4,…に出現する。

これらをインターセクションすることで、Boolean演算が実行可能である。

ちなみに、リストの短いものから順に演算していくと効率がよい。(この場合だとCALPURNIA,BRUTUS,CAESARの順)

メリット

  • 正確である。

デメリット

  • 逐次検索であるため、大量にドキュメントセットがある場合は非常に遅い
  • 例えば「COUNTRYMANの近くにROMANSがあるような文書」のようなクエリは作成できない