30分でわかる高性能な圧縮符号vertical code

検索エンジンの転置インデックスなどデータ列を小さいデータサイズで持たせたい、という状況がある。こういう場合圧縮符号を使うのが一般的でunary符号やgamma符号、delta符号など様々な種類がある。
圧縮符号の中でイチオシなのがvertical code(vcode)。これは岡野原(@hillbig)氏によって提案された圧縮符号で単純な仕組みでdelta符号並の性能を誇っている。
本記事ではvcodeのポイントを絞って30分でわかるように解説してみる。

vcodeは本棚に本を並べる作業を連想すると理解しやすい。本棚は予め高さが決まっているので全ての本が入るような本棚を用意する。つまり

というようなものを想像する。
この本棚は8冊の本が並んでいるが左から5冊目の本が他よりも背が高い。このため5冊目の本に合わせて背の高い本棚が必要になる。だが他の本は5冊目の本ほどに背が高くないので、5冊目がなければもっと背の低い本棚で十分だったかもしれない。
そこで本を横にして平積みにしてみる。つまり

このようにする。こうすると平積みにする冊数を調整すれば好きな高さの本棚を選択できる。また平積みにしたことで1冊の本の背の高さが影響を与える範囲は平積みにされている1段だけになるので効率的に本を並べることができる。

基本的にはvcodeはこの本棚と同じ事をしている。本棚の高さは変数型に対応している。つまりデータが取りうる最大の値が格納できるような変数型を選ぶ。例えば

というデータ列を考える。このデータ列は先程の本棚と同様に4番目の値だけ1byteで表現できる範囲を超えている。この4番目の値がなければすべてchar(1byteの変数型)で格納できるが、この4番目の変数のせいで2byte変数を使わないといけない。
ここで本棚の時の発想を使う。つまりデータの縦横をひっくり返して、各データ(をbit列にした時)の1桁目を一つ目の変数に、2桁目を2つ目の変数に、というように変数を桁ごとに入れていく。
まずはデータをbit列にする。

32(10 0000)
64(100 0000)
128(1000 0000)
256(1 0000 0000)
15(1111)
31(1 1111)
63(11 1111)
127(111 1111)

次にデータの縦横をひっくり返してみる。すると

1桁目：0000 1111
2桁目：0000 1111
3桁目：0000 1111
4桁目：0000 1111

5桁目：0000 0111
6桁目：1000 0011
7桁目：0100 0001
8桁目：0010 0000

9桁目：0001 0000

となる。これはchar型(1byte)の変数を9つ使った9byteで格納できるので、縦横をひっくり返す前は2byte型変数を8つ使った16byteで格納していたのでデータの格納効率がよくなった。
このように縦横を入れ替えると変数型のサイズに依存せずに必要な桁数だけ変数を用意すればよくなる。これは本棚の本を平積みにしたことで本棚の高さ一杯まで本を入れられるようになったことに対応する。
また各桁の値を入れる変数の数(=表現できる桁数)はデータ8つ毎に変更しても大丈夫なので、大きなデータが入ってきてもデータ全体に影響をあたえることはなく影響の範囲がデータ8つ分で済む。これは本棚の本を平積みにしたことで、背の高い本が平積みにした1段にしか影響を与えなかったことに対応する。

以上がvcodeの基本的な部分。詳細が気になる方は以下の資料を参考にされたい。

現実的な圧縮付全文索引岡野原大輔
Practical Entropy-Compressed Rank/Select Dictionary D. Okanohara, and K. Sadakane; ALENEX2007