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

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

Java

簡潔ビットベクトルの圧縮タイプの実装を調べていて、以下の論文を読んだ。Re-Pair(さらっと文字列本に書いてあるよ)という文法圧縮を利用している。実際の実装は、4章にあります。場合によっては、RRRの実装よりも良いようだ。ただし、アクセス性能は良くない。

http://www.dcc.uchile.cl/~gnavarro/ps/sea11.2.pdf

論文では、ウェーブレット木の圧縮に利用している。アクセス速度はそれほど速くないようだが、Plainな実装やRRRの実装とハイブリッドすればまぁまぁになるようだ。Re-Pairを使った簡潔ビットベクトルの実装も工夫されており、Re-Pairの辞書表現を簡潔ビットベクトルを使って圧縮している。そのあたりの話が4章の後半に書いてあるのだが、あっさりしすぎていて、理解できなかった。ただ、以下の参考文献を読んだら理解できた。

http://www.dcc.uchile.cl/~gnavarro/ps/cpm07.1.pdf

2.3節に詳しく書いてあります。例が書いてあるので、ちゃんと読めばわかると思います。

ウェーブレット木(行列でも良いよ)の圧縮はとても重要で、ランダムな数値列(最悪ケースは、RRRでも圧縮できない)をウェーブレット木で表現すると、場合によってはサイズが大きい。quantile操作やrangemaxk操作やrangemink操作などは、数値列に対して行うことが多いので、実用上、サイズが大きいと嫌がられる場合もある。そんな時にRe-Pairを利用した簡潔ビットベクトルが役立つと思う。ってか、top-k操作とかintersect操作とか作ってみたけど、ウェーブレット木って凄いわ。

Re-Pairを利用した簡潔ビットベクトルをゴールデンウィーク中に実装しようと思ったが、理解するのに苦労してあまり進んでいない。。。