高速かつ省メモリなbit vector「sucBV」を作る

大規模データを効率的に扱う操作付きbit vectorライブラリの実装

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の構築の流れは次の通りです。

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を実際に求めています。

sucBVの利用

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の遷移などの部分で高速化を図ることができます。

参考資料

1. WEA 2005 『Efficient Implementation of Rank and Select Functions for Succinct Representation』
Dong Kyue Kim・Joong Chae Na・Ji Eun Kim・Kunsoo Park 著
2. google-sparsehash