Compressed Suffix Arrayの解説(5) -Succinct Bit Vector-

計算機科学

< Compressed Suffix Arrayの解説(4) -unary記法- < | > Compressed Suffix Arrayの解説(6) -B Vectorと Ψ Bector- >

================================================

ものすごい勢いで更新をサボっていたCSAの解説を再開。今回はSuccinct Bit Vectorというデータ構造について。
Succinct Bit Vector(簡素なビットベクトル)とは、ビット列に対してrank()、select()という操作を追加したもの。CSAではΨ VectorやB Vectorなどのビットベクトルに対してrank()、select()をガンガン使うので、しっかり抑えておきたい。


rank(pos, bit)はビットベクトルのposの位置までにbitの出てきた回数を返す関数。
例えば

pos : 0 1 2 3 4 5 6 7
bit : 0 1 0 0 1 1 0 1

というビットベクトルがあった場合

rank(0, 0)=1、rank(0,1)=0
rank(1, 0)=1、rank(1,1)=1
rank(2, 0)=2、rank(2,1)=1
rank(3, 0)=3、rank(3,1)=1
rank(4, 0)=3、rank(4,1)=2
rank(5, 0)=3、rank(5,1)=3
rank(6, 0)=4、rank(6,1)=3
rank(7, 0)=4、rank(7,1)=4

となる。
一方、select(count, bit)はbitがcount回出てくる位置を返す。つまりrank()の逆関数。select()は一意に定まらないが、実用上、該当する位置のうち最も小さい物を返すようにする。
例えば、rank()の例で使ったビットベクトルに対して

                select(0,1)=0
select(1, 0)=0、select(1,1)=1
select(2, 0)=2、select(2,1)=4
select(3, 0)=3、select(3,1)=6
select(4, 0)=6、select(4,1)=7

となる。
実装については、きちんとやる場合は岡野原さんのもの↓

http://codezine.jp/article/detail/260

を参考にするのがよい。本記事ではシンプルな実装を紹介しておく。
rank()についてはメモリ効率を無視するなら、すべての位置に対してrank()を事前計算しておけばよい。実用上は、32bitや64bitなどのブロック単位で事前計算しておいてブロックからはみ出た部分をpopcountという方法で計算する。これによって定数オーダでrank()が求まる。
popcountについては↓などを参照。

http://developer.cybozu.co.jp/takesako/2006/11/binary_hacks.html

select()はrank()の逆関数なので実装済みのrank()を使って二分探索するのが手っ取り早い。定数オーダで実装したい場合は別途工夫が必要だが、本記事はCSAの解説がメインなので詳細は触れない。
今回はここまで。俺、この戦争が終わったら次の記事を書くんだ。。。(死亡フラグ的な意味で

↓popcountとかちゃんと勉強したい人に

================================================< Compressed Suffix Arrayの解説(4) -unary記法- < | > Compressed Suffix Arrayの解説(6) -B Vectorと Ψ Bector- >