Vertical Codeはunary符号の6倍すごい

Vertical Codeを実装してみたらunary符号のときよりデータサイズが1/6になった。とても感動したので、この気持ちを伝えるため記事を書いてみるよ。

Vertical Codeを使うことになった経緯は↓を参照
Vertical Codeを調べたよ - EchizenBlog-Zwei

Vertical Codeはその名の通り、データをVerticalに持っておく符号形式。デルタ符号くらいのデータサイズで収まる。だったらデルタ符号でいいじゃんと思うのだが、Vertical Codeにはselect()、rank()という操作が簡単に実装できるメリットがある。
select(pos)とはpos番目のデータ値の累計値を求める操作。rank(value)とは累計値がvalue以上になるはじめてのposを求める操作。互いに逆関数の関係にある。(unary符号を用いたときとrank()、select()の意味が逆なので注意。符号化によらずデータに対してrank()、select()が同じものを返すようにするとこうなるはず。ちょっとrank()、select()の名前の使い方に自信ないので気になる人は自分で調べてね。酷。)
話を戻すとVertical Codeはselect()つまりデータの指定位置までの累計値を求める操作が頻発するときに活躍する。例えば検索エンジンのインデックスを差分値で保持したい場合、最終的にほしいのは開始地点のインデックス値からクエリにヒットした差分値までの累計値になる。
Vertical Codeにデータを追加していく様子を説明する。最初にブロックサイズを決める。プログラミングする言語のデータ型に合わせると便利。ここではchar型(8bit)を想定しブロックサイズを8にする。

i      0 1 2 3 4 5 6 7
V[0]:  0 0 0 0 0 0 0 0

↑のように最初はゼロ初期化をしておく。

早速データを追加する。上記のインデックスの例でいうと最初のインデックス値が2だったとする。すると2を二進表記した10を縦(Vertical)にして以下のように配列に入れる。(配列の要素が足りないのでサイズを増やす)

i      0 1 2 3 4 5 6 7
V[0]:  0 0 0 0 0 0 0 0
V[1]:  1 0 0 0 0 0 0 0

次のインデックス値が3だったとする。すると差分が1なので二進表記して1を配列に入れる。

i      0 1 2 3 4 5 6 7
V[0]:  0 1 0 0 0 0 0 0
V[1]:  1 0 0 0 0 0 0 0

次のインデックス値が8だったとする。すると差分が5なので二進表記して101を配列に入れる。(配列の要素が足りないのでサイズを増やす)

i      0 1 2 3 4 5 6 7
V[0]:  0 1 1 0 0 0 0 0
V[1]:  1 0 0 0 0 0 0 0
V[2]:  0 0 1 0 0 0 0 0

同様にインデックスを足していくと8個たまった時点で

i      0 1 2 3 4 5 6 7
V[0]:  0 1 1 0 1 1 0 1
V[1]:  1 0 0 1 1 0 1 0
V[2]:  0 0 1 0 0 1 1 0

といった感じになる。このようにデータを保持するとデータサイズは横方向には1で固定なので一般的な符号化のようにデータ境界を判別するための仕組みがいらなくなり簡素になる。また配列Vの大きさについてはブロックごとに最も大きいデータを表現するのに必要なビット数分でよいので、普通の固定長データのように全データに32bit使うといった非効率を回避できる。
次にselect()操作について。select(i)はiまでの累計値を計算する。まず、i=7のとき、つまりブロック内の累計値を求める方法を。
各々のデータについて二進表記したときにV[0]が一桁目、V[1]が二桁目、V[2]が三桁目・・・となっている。よって一桁目の値を全部足し、二桁目の値を二倍したものを全部足し、三桁目の値を四倍したものを全部足し・・・とすればよい。
各桁の合計値はchar型変数のビットのうち1が立っているものの個数と同じになる。これはpopcountという方法で高速に求まる。これについては前回記事を参照。よって

rank(7) = Σ_k {popcount(V[k]) << k}

となる。
次にiが任意の場合。iが7より大きい場合はそこまでのブロック全体の累計値を↑の方法で計算できるので、最後のブロックのj = i mod 8 までの累計値をそれに足せば良い。
具体的には(1 << j) - 1でV[k]をマスクしてあげれば良い。例えばj=3なら、

 00000001 << 3      → 00001000
(00000001 << 3) - 1 → 00001000 - 1 = 00000111

となるのでandをとればV[k]の下3桁が取得できる。
rank()についてはselect()の逆演算なので二分探索してあげれば良い。なおCSAのΨVectorにVertical Codeを使う場合はselect()操作しか使わない。これは簡単。すばらしい。
というわけでVertical Codeのすばらしさがちょっとでも伝わったらうれしいな☆