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

Javaで簡潔ビットベクトル(30)

Java

疎なビットベクトルに対する完備辞書が利用できるケースについて考えてみた。「複数の文書をまとめたFM-Index(CSAでもいいけど)からの文書IDの復元」で利用できると思う。

複数の文書をまとめたFM-Indexから文書IDを復元する時は、以下のような感じになると思う。

f:id:ryokkie:20130323112611p:plain

複数の文書をまとめたFM-Indexを作る時は、文書境界に検索できない文字(NULLとか)を付けて巨大な文書にすると思う。このときに、文書境界に1を立てたビットベクトルを用意しておいて、検索時に文書IDを復元する。ただ、平均文書サイズが大きい場合、かなり疎なビットベクトルになるので、疎なビットベクトルに対する完備辞書が利用できると思う。特に、sbvjで使っている疎なビットベクトルに対する完備辞書は、実際のビットベクトルを保持する必要もないので、かなりサイズを小さく抑えられると思う。

この他にも多くの応用が考えられるので、完備辞書を様々な形で実現できるようにしておくのは重要だと思う。