sucBVの使い方
sucBV
は、固定のbit vectorに対し構築されるので、自由に変更できるbit vectorを最初に用意してから、そのbit vectorを基にしてsucBV
を構築する形になっています。sucBV
は「sucBV.hpp」中のclass sucBV
として提供されています。利用する場合、はじめに利用したいbit array情報が含まれたbit vectorを用意します。bit vector
は「bv.hpp」中のclass bitVector
を使います。bitVector
は最初全て0のbit列です。bitVector
は次のメソッドが用意されています。
メソッド | 説明 |
bitVector(unsigend int size) | Bit Array B[0...size-1] = 00...0 を構築する。 |
setBit(unsigned int pos) | B[pos] を1にsetする。 |
次にbit vectorをsucBV
のコンストラクタに渡してsucBV
を構築します。上のB[0...9] = 0101000111
の例に対するsucBV
の構築の流れは次の通りです。
#include "bv.hpp" using namespace cs; ... bitVector bv(10); //B[0...9] = 0000000000 bv.setBit(1); bv.setBit(3); bv.setBit(7); bv.setBit(8); bv.setBit(9); //B[0...9] = 0101000111 sucBV opb(bv);
実際にrank
、select
を利用する場合は、sucBV
のメンバ関数であるrank()
、select()
を呼び出します。以下では、上述の例のrank
、select
を実際に求めています。
printf("rank(5,0)=%d rank(5,1)=%d select(2,1)=%d select(2,0)=%d\n",
opb.rank(5,0),opb.rank(5,1),opb.select(2,1),opb.select(2,0));
sucBV
を構築、利用する一連の流れのサンプルは「sucBV_unitTest.cpp」にあります。このコードでは最初にランダムなbit vector列を生成した後、それからsucBV
を構築します。その後、実際直接rank
、select
を求めた場合と値をチェックした後、速度計測をしています。
sucBV
は圧縮率の高い整数集合コンテナとしても利用できますが、その真価を発揮するのは圧縮索引などで利用する場合です。これらのデータ構造での使用例については、今後の記事を参考にしてください。
sucBVの応用
sucBV
は圧縮索引以外にそのままbit配列として使うこともできます。例えば、整数集合{i|i∈[0...N-1]}のデータを扱う場合を考えて見ます。この集合情報は、長さNのbit vector B[0...N-1]
を用意し、B[i]
をi
が集合に含まれている場合1、そうでない場合0とすることで表現できます。このbit vectorに対しsucBV
を構築することにより、集合中の要素を順に列挙できる他、前から順番にindexを与えることができます。これはgoogle-sparse hashで使われているのと同様の方法です。このsucBV
の性能を評価するために、同様の操作が可能なSTLのset<unsigned int>
を使って集合を表現した場合と比較してみます。[0...100M)中の整数からなる集合をsucBV
、set<unsigend int>
を利用して保持した場合、またそれらを前から順に列挙した時の実験結果が以下の通りです。集合中のエントリ数を1/100、1/10、1/2に変えています。括弧内が一回のエントリーの列挙にかかる時間です。
集合中のエントリ数 | set<unsigned int> | sucBV |
1M | 32.9MB(0.07 us) | 36.7MB(0.07us) |
10M | 382MB(0.07 us) | 35.1MB(0.07us) |
50M | 1908MB(0.06 us) | 34.7MB(0.06us) |
set<unsigend int>
の場合、要素を前から順にiteratorを使って列挙しているので計算量がO(logN)ではなく、O(1)に近くなっています(最悪O(logN))。この比較は二つのデータ構造がサポートする操作が違う点、例えばsucBV
がi番目の要素を直接指定できることや、0側のselect
もサポートしている点など、完全に公平な比較ではないですが、sucBV
が500万エントリといった大規模なデータに対しても、作業領域は50Mで十分扱えることがわかります。
技術解説
sucBV
が基にしているのは [1] の論文中の5.2章の内容です。sucBV
はrank
を実現するために、bit arrayを一定長ずつのブロックに分割し、それぞれのrank
の結果をテーブルで保持しておきます。rank
を求める場合にはこの表引きを組み合わせて求めます。また、select
を実現するために、rank
と同様にbit arrayを一定長ずつのブロックに分割しておき、rank
と比べ複雑な手続きになりますが同様に表引きで求めます。高速化の一つのポイントは全ての操作をバイト単位(8bit)、もしくはワード単位(32bit)で処理をし、bit単位の処理をしていないことです。さらに、作業領域量を減らすため、rank
やselect
でデータを共有する工夫をしています。詳しくは[1]、または「sucBV.hpp」を参照してください。
この実装ではselect
を、select(p,1)
とselect(p,0)
の2つの別のデータ構造で保持しています。これらを共有させることで、さらに作業領域量を減らすことができる可能性があります。
また、rank
もしくはselect(p,1)
のみを使う場合には、作業領域をさらに減らすことができます。
まとめ
今回紹介したデータ構造sucBV
は、rank
、select
という非常に基本的ながら、そのまま実装すると作業領域量が大きくなってしまうものを、元のbit vectorの約2倍の作業領域量で定数時間操作をサポートしています。このデータ構造は元々圧縮索引やSuccinct Data Structureのために提案されたものですが、その他の応用用途も考えられます。例えば、途中での追加、削除はできませんが、google-sparse hashの要素の有/無を保持している部分をこのsucBV
に置き換えることで、iteratorの遷移などの部分で高速化を図ることができます。
参考資料
- WEA 2005 『Efficient Implementation of Rank and Select Functions for Succinct Representation』
- google-sparsehash