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

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

Java

疎なビットベクトルに対する完備辞書を利用できる場合について、さらに考えてみた。
メモしておく。

f:id:ryokkie:20130326003936p:plain

こんな感じで、一文字だけUCS-2の範囲を超えた文字が存在すると、上位ビットのビットベクトルはかなり無駄なので、こういう時に疎なビットベクトルに対する完備辞書が利用できると思う。もちろん、自分で文字に整数を割り当てて、内部管理すれば、このような状況にはならない。ただ、Unicodeのコードポイントをそのまま利用してFM-Indexを作成する場合は、このような状況も想定していないといけない。

偏りのあるビットベクトルを利用する場合についても考えたが、それこそBWTしたテキストをウェーブレット行列で表現する時に利用するべきだと思う。BWTによって似たような文字が連続して出現しやすくなるのだから、ビットベクトルの1と0も偏るはずである。なので、偏りのあるビットベクトルに向いている完備辞書であるRRRとかを使えば良いと思う。なので、sbvjでは、RRRの完備辞書の実装を進めています。