Blog
こんにちは、この夏はシルキードライで乗り切りたい岡野原です。
今日は最近公開したC++のオープンソースであるdag vectorについて紹介します。
ライセンスは修正BSDライセンスです。
dag vector (direct accessible gamma code vector) は値を圧縮して格納したまま任意の場所の値を高速に参照可能な配列ライブラリです。しかもデータ末尾への追記が可能です。 dag vectorはstd::vectorのように利用できます。下にいくつか例を見ていきましょう。
dag_vectorの例
#include "dag_vector.hpp" // dag_vectorは0以上の正整数の配列を扱う配列。 dag_vector dv; // 値はいつでも追加可能。追加された値は圧縮して格納される // 正整数xは2lg(x+1) - 1 bitで格納される、但しlg(t)はtの二進数のビット長さ dv.push_back(1); dv.push_back(100); ... // 任意の位置の値を定数時間でアクセス可能． assert(dv[10000] == 7777); // prefix_sum(i)はdv[0]+dv[1]+...+dv[i-1]の合計値を返す。これも定数時間 dv.prefix_sum(2) == 101
comp_vectorの例
#include "comp_vector.hpp"
// comp_vectorは任意のオブジェクトTを圧縮して格納．
// 内部では各Tを正整数に変換しdag_vectorで格納．
// Tはint operator() < (const T& t) const をサポートしている必要がある
comp_vector cv;
// 同じようにpush_backで追加可能
cv.push_back(MyObject("hogehoge"));
cv.push_back(MyObject("fugafuga"));
...
// 任意の位置の要素を定数時間でアクセス可能
assert(cv[1] == MyObject("fugafuga"));
sparse setの例
#Include "sparse_set.hpp" // sparse_setは疎な正整数の集合, U⊆[0, 1, 2, ....] を扱うことが可能． sparse_set ss; // 昇順に値を格納可能．昇順じゃない値を入れた場合の動作は保証しない． // 値の最大値がn, 格納した個数がmの時、データ構造サイズの下限に近い2m + m lg(n/m) bitで格納可能． ss.push_back(1); ss.push_back(100); ss.push_back(150); ... // []で任意の値を定数時間でアクセス可能 assert(ss[1] == 100); // その値が入っているかどうかも定数時間で参照可能 assert(ss.exist(77) == false);
まだライブラリはできたてで、インターフェースは変わる可能性があります。現在はヘッダファイルに全部かかれてますが、今後どうするか思案中です。
ライブラリの詳しい説明は、ライブラリのページに追加していきます。test/以下のコードも参考にしてみてください。
以下では内部技術について解説していきます。
背景
通常データは圧縮すると、全て復元しないと使えません。例えば1億個の整数値からなるデータを圧縮したら、 真ん中の500万番目から10個だけを参照したい場合でも、全部を復元をしてから、その10個だけを取り出す必要があります。
圧縮されたデータを任意の場所から復元することが難しい理由の一つとして、圧縮後は各要素のサイズが可変長であり、復元を開始する位置が分からないという問題があります。
これを解決するためにブロック化がよく行われます。これは、データを例えば128個ぐらいずつのブロックに分けて、それらを別々に圧縮して保存する方法です。 そして、各ブロックの先頭位置を別に記録しておきます。ある位置のデータを復元したい場合は、それが所属するブロックを全て復元し、そして欲しいデータを取り出します。
このブロック化による方法は各要素のサイズが大きいならば、先頭位置を記録している分のオーバーヘッドは 無視できるほど小さいのですが、各要素のサイズが小さい場合（例えば整数値など）は、オーバーヘッドが無視できないくらい大きくなります。 特に普通の配列と同じように１要素ずつランダムアクセスなどするのであれば、ブロックサイズ分の復元オーバーヘッドも無視できません。
フィボナッチ符号など、符号の開始位置を後からでも分かる符号もありますが、符号効率、アクセス性能はよくありません。
ライブラリの内部紹介
今回紹介するC++ライブラリdag_vectorは、圧縮したまま任意の位置へのアクセスができ、さらに要素を追加できます。 これらの処理は配列長に依存しない定数時間で実現できます。
dag_vectorは内部は既存の様々な簡潔データ構造といくつか新しいアイディアに基づいて作られています。これらについて解説していきます。
rank辞書 / rank_vector.hpp
長さnのビット配列 B[0…n-1]に対し、rank(B, i)をB[0…i-1]中に含まれる1の数と定義し、この操作を備えたデータ構造をrank辞書といいます。 Bに対して前処理を行い、任意のiについてrank(B, i)を定数時間で返すデータ構造は多く提案されています。 今回実装に利用したのは一番一般的な実装です。
今回のrank_vector.hppは、データの末尾追加もサポートしています。
ガンマ符号 / dag_vector.hpp
次に紹介するモジュールがdag_vector (direct accessible gamma vector)であり、今回紹介するライブラリ群の中核をなしています。 このdag_vectorではランダムアクセス可能なガンマ符号を実現しています。これは以下の論文で紹介されているものをガンマ符号にしたもので、wavelet木でunary符号を扱っていると 考えてもらうとよいかもしれません。
Nieves R. Brisaboa, and et. al. Directly Addressable Variable-Length Codes, SPIRE 2009 [pdf]
ガンマ符号の復習
ガンマ符号は、1以上の整数値xを次のようにして符号化します。
xを二進表記した時の長さを単進符号（yの単進符号はy回0を出力し、最後に1を出力した符号）で出力
それに続き、xの最上位bitを除き、残りを二進表記で出力
例えば、x=6の時、これを二進表記にすると001であり、長さは3です。これを単進符号で出力すると001となります。次に6の二進表記の最上位bitを除いた10を出力します。001と10をつないだ00110がx=6に対するガンマ符号です。
この他にx= 1, x=7, x=77, に対する符号はそれぞれ、1, 00111、0000001001101となります。
ガンマ符号は可変長符号であり、小さい数に対し短い符号を割り当てます。 このガンマ符号を復元する時は、最初に連続する0の数を数え、それで残りの二進符号の長さが分かるのでそれを読みこめば復元できます。 ガンマ符号は小さい値が頻出する場合に有効で、大きい値も多くでる場合は有効な符号ではありません（その場合はデルタ符号や、ライス符号などが有効でしょう）
具体的にはp(x)を正整数xが出る確率とすると、p(1)=1/2, p(2)=1/8, p(3)=1/8, p(4)=1/32, p(5)=1/32, …と非常に急激に小さくなっていく場合に最適な符号です。
このガンマ符号は前から順に復元すれば一意に復元可能ですが、それぞれの符号長が可変なのでランダムにアクセスすることができません。
ガンマ符号のランダムアクセス化
ガンマ符号は前から順番にしか復元できません。任意の位置のガンマ符号を復元できるように次のように符号を並び替えます。
まず各値の単進符号部分の1bit目をビット配列U1に順に並べます。次に、二進符号長が1以上の要素の1bit目をB1に並べます。 次に単進符号長が1以上だった要素について単進符号の2bit目をU2に並べ、また同様に、ここで値が1だった値だけに関してbinary符号の2ビット目をB2に並べます。これをU3, B3, U4, B4, …と全ての値が符号化されるまで繰り返します。
ガンマ符号を並び替えているだけなので、全体のビット配列長は元のガンマ符号の合計長と代わりません。
例として、x[0,1,2,3] = [8, 1, 3, 5]の場合を考えてみましょう。これらのガンマ符号は、0001|000, 1|, 01|1, 001|01 となります。 分かりやすいように単進符号と二進符号の境目に|を入れてあります。
まず、これらの配列の単進符号の1ビット目を並べてU1にセットすると、U1=0100となります。ここで、0であったもの（x[0], x[2], x[3])について、二進符号の1ビット目を並べてB1にセットします。B1=010となります。 次に、x[0], x[2], x[3]について、単進符号の2ビット目をU2に格納します。U2=010であり、B2 = 01となります。これを繰り返すとU3 = 01, B3 = 0, U4 = 1となります。
U1 = 0100 B1 = 010 U2 = 010 B2 = 01 U3 = 01 B3 = 0 U4 = 1
Ui, Biの配列ができたら、次にこれらの配列に対しrank辞書を構築します。これで出来上がりです。
では、このrank辞書を使ってx[2]をアクセスしてみましょう。
まずrank(U1, 2)を求めると、rank(U1, 2) = 1であり、また2番目のunary符号の最初はU1[2]=0 です。よって、x[2]の二進符号は、1bit以上であり、その位置はB1の1=rank(U1,2)の位置にあることが分かりますので、それを見るとB1[1]=1なので、最初は1です。U2の位置はU1[0…2]中の0の数であり、これは2 – rank(U1, 2)=1と分かります。次にU2[1]=1ですので、x[2]の二進符号長は1であったということが分かります。 ガンマ符号では二進符号の最上位bitは常に1であることが分かっているので2をくわえ、結果として3と復元できます。
以下にdag_vector.hpp中の実際の復元部分を引用します。
uint64_t operator[] (uint64_t ind) const{
uint64_t val = 0;
for (uint64_t shift = 0; shift < bitunaries_.size(); ++shift){
if (!bitunaries_[shift].get_bit(ind)){
return val + ((1LLU) << shift) -1;
}
ind = bitunaries_[shift].rank(ind);
val += bitvals_[shift].get_bit(ind) << shift;
}
return val + ((1LLU) << bitunaries_.size()) - 1;
}
prefix_sumの実現
さて、この符号は要素にランダムアクセスできるだけでなく、任意のiについて、prefix_sum(i) = x[0]+x[1]+ …+x[i-1]が高速に求められます。
これを実現するコードはoperator[]と殆ど同じですが、operator []とは違い、各Biにおいてrankをして合計値を桁毎に足しこんでいきます。
以下にdag_vector.hpp中のprefix_sum()の部分を引用します。
uint64_t prefix_sum(uint64_t ind) const{
uint64_t orig_ind = ind;
uint64_t ret = 0;
for (uint64_t shift = 0; shift < bitunaries_.size(); ++shift){
uint64_t ones = bitunaries_[shift].rank(ind);
ret += (ind - ones) << shift;
ret += bitvals_[shift].rank(ones) << shift;
ind = ones;
}
return ret + (ind << bitunaries_.size()) - orig_ind;
}
operator[], prefix_sumともに各ビット配列内では定数時間のrank操作で計算するので、配列長に依存しないO(log max x[i])時間で求めることができます。
select操作の実現
簡潔データ構造でrankと同様に重要なselect操作もこのdag_vectorのprefix_sumを利用して実現できます。
select操作とは、ビット配列B[0…n-1]に対し、select(B, i)はB中の(i+1)番目の1の位置を返す操作です。 select(B, i)を実現するためには、B中の1の立っている位置を並べたものをp[0], p[1], .. p[m-1]とします。mはB中の1の個数です。そして、i=0…m-1について、d[i] = p[i] – p[i-1]と定義します、但しd[0] = p[0]です。 これらd[i]をdag_vectorで保存します。するとselect(B, i) = prefix_sum(i)として求められます。このようにselect操作が内部では全てrank操作だけで求まります。
疎な集合の圧縮格納 / sparse_set.hpp
sparse_setは正整数集合U⊆[0,1,….]を効率的に格納します。
これは例えば全文検索における転置ファイルや行動履歴ログ、機械学習における特徴ベクトルとかがそれに当たります。 これも先ほどと同じようにdag_vectorで管理できますが、dag_vectorの計算量はO(log k)であり、よく扱う集合だとkが100や10000と非常に大きくなってしまい計算量が要素数に対し定数時間とは計算量が大きくなってしまいます。そこで以下のろんぶんで提案しているようにこの配列を上位bitと下位bitに分割します。
D. Okanohara and K. Sadakane, “”Practical Entropy-Compressed Rank/Select Dictionary””, ALENEX 2007
密なbit vectorの0側, 1側のselectはdag_vectorで実現します。密ベクトルの場合はそ隔が大きくなることは稀ですのでdag_vectorは高速に動作します。殆どの場合 log k = 2, 3と非常に小さな値になり高速に操作できます。
任意のオブジェクト圧縮配列 / comp_vector.hpp
最後に、任意のオブジェクト配列を圧縮できる配列です。
要素の数にばらつきがある場合、頻出する要素に対しては短い符号、そうでない要素に対しては長い符号を割り当てることで全体長を短くすることができます。
comp_vectorでは内部で要素の出現回数を管理し、出現回数が大きいものから順に0からの正整数値を割り当て、それらをdag_vectorで保存します。要素から値への割り当て部分でstd::mapを利用していますので、各オブジェクトには全順序が定義されていることが必要です。追加をしていくうちに要素の頻度情報が変わってきますので配列サイズが2倍になるたびに、新しい符号で割り当てた場合にどれだけ短くなるかをチェックし、それが設定した割合より短くなっていれば、符号を全て割り当て直します。
全部コピーするといっても、2倍毎のタイミングで発生するのでvectorのresizeと同じように均し計算量はO(1)のままです。ただ、殆どの場合、小さいサイズのうちでサイズが決まり残りは再割当ては発生しません。
その他への応用
現在、このdag_vectorを利用して、tx, uxをさらに小さくする簡潔trieを作っている他、動的な簡潔trieなども作っています。またLZ符号でランダムアクセス可能なLZEndを逐次的に処理していくものもつくりはじめています。 dag_vectorはガンマ符号を利用していますがそれ以外の符号も同じようにランダムアクセス可能な配列を作ることが可能でしょう。
今後の課題
現状の課題の一つは速度です。ランダムな配列によるperformance_testの結果、生のinteger配列と比べて、大体サイズが1/4〜1/20となりますが、速度が4倍〜20倍に遅くなることが分かっています。この高速化には、キャッシュ効率を上げることなどが必要です。
とりあえず勢いで作ってみましたがこれから地道なパフォーマンス挙げと、自分でもいろいろ使ってみて、使い勝手のよいライブラリにしたいと思っています。もし何か意見やコメントなどありましたらいただけますと幸いです。
最後に
dag_vectorは、飲み過ぎて早起きして出社した朝に作りはじめ、大江戸線の通勤時間で作っています。
Tag
