Vertical Codeを調べたよ

計算機科学

故あってCompressed Suffix Array(CSA)を実装していたのだがΨ Vectorのデータ構造にunary符号を採用したら圧縮前よりもサイズが大きくなるという惨事が発生。
これに対処するため急遽データ構造をVertical Codeに変更した。デルタ符号(δ符号)並の圧縮率で、しかも高速らしい。


例えば

index:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
value:  0  1  0  1  0  1  0  1  0  1  2  3  0  1  2  3

というデータを考える。

Vertical Codeはデータを固定サイズM毎にブロックとして扱う。ここではM=8とする。また値はビット列に置き換え縦に並べる。すると最初のブロックは

index:  0  1  2  3  4  5  6  7
value:  0  1  0  1  0  1  0  1
bit  :  0  1  0  1  0  1  0  1
MSB  :  1
d    :  4

次のブロックは

index:  8  9 10 11 12 13 14 15
value:  0  1  2  3  0  1  2  3
bit  :  0  1  0  1  0  1  0  1
        0  0  1  1  0  0  1  1
MSB  :  2
d    : 12

となる。MSBとdの意味は後ほど説明する。
ここで作られたサイズM=8のbitを横に並べたものを一つのデータVとする。サイズ8なのでchar型で保持できる。通常はM=32、64などを使う。
ここで最初のブロックは0から1までの値しかとらないのでVが1つで済むが、二つ目のブロックは0から3までの値を取るのでVを2つ使っている。ブロックごとにいくつVを使っているかをMBSと呼び別途保存する。最初のブロックはMSB=1、次のブロックはMSB=2となる。ブロックのサイズを小さくすればビットの無駄が減るが保持すべきMSBは増える。
Compressed Suffix Arrayでは指定されたindexまでの値の合計(select)を取得する演算が必要になる。これを実現するためにブロックごとに値の合計値dを事前計算しておく。最後ブロックはpopcountという処理を使えば定数時間で合計値を取得できる。
例えばindex11までの値の合計を知りたいとする。
index11は二つ目のブロックに属するので、それ以前のd値をまず合計する。最初のブロックはd=4なので、まず

rank = 4

とする。次に、Vのうち一番小さいものV[0]はそのブロックのデータのbit列の下一桁なので、これを全部足す。これには単純にV[0]をビットマスクして下3桁だけ取り出し、そのうち1が立ってるものを合計すればよく、これはpopcountという処理で実現できる。popcountについては参考文献↓のtakesako氏のものが詳しい。
V[1]も同様に計算。具体的なpopcount値の取得は以下の通り。

index:  8  9 10 11
bit  :  0  1  0  1 => popcount[0]=1
        0  0  1  1 => popcount[1]=2

ここでV[1]はデータのbit列の下から2桁目なので実際の値にするには2倍する必要がある。従って2倍してからV[0]のpopcount値に足す。

select = 4 + popcount[0] + (popcount[1] * 2)
       = 4 + 1 + (2 * 2)
       = 9

従ってindex11までのデータの値の合計値(select値)は9となる。これが合っていることは記事冒頭のデータを手で数えてみればわかる。
Vertical Codeはその名の通りデータを縦に並べているだけだが、縦に並べたことで桁ごとの累計値をpopcountで計算できるため、あとは桁ごとの累計値を桁ごとにビットシフト(2n倍)すれば簡単にselect値が計算できること。またブロックごとに最大のbit数だけ保持していればいいので全データを固定bitで表現するより効率が良いこと(かつデルタ符号のようにデータ間のセパレータビットが不要)。の2つがポイント。
うまくできてるな、と思った。

参考文献: