簡潔データ構造超入門II 〜ちょっとだけ実用的な簡潔ビットベクトル〜
簡潔データ構造(Succinct Data Structure)の魅力を紹介する本シリーズ。前回の記事では疎ベクトルを簡潔データ構造を使って効率的に実装する方法を紹介した。
前回の実装ではビットベクトルのサイズの上限が256だった。今回はこれを拡張して任意の大きさを扱える簡潔ビットベクトルの実装例を紹介する。
また前回はrank()を定数時間で実現する方法を紹介した。今回はこれを使ってselect()を二分探索(O(logN))で実装する。
以上の2つの改善によってビットベクトルのサイズに制限がなくrank()/select()の双方を備えた、実用性のある簡潔ビットベクトルが実現できる。
サイズに制限のないビットベクトルは前回実装した簡潔ビットベクトルのsbvクラスを用いて実装することができる。まずはsbvクラスをリネームしてtiny_sbvとする(sbvという名前は今回実装する実用版にとっておきたかったので)。
typedef unsigned long long ull; // 8byte
typedef unsigned char uc; // 1byte
class tiny_sbv {
ull B_[4]; // 32byte
uc r_[4]; // 4byte
public:
tiny_sbv();
void set(int i);
bool get(int i) const;
void build();
int rank(int i) const;
};さて具体的にサイズに制限のないビットベクトルをどうやって作るか。これは単純に考えるとtiny_sbvクラスのvectorで管理すれば良い。ただtiny_sbvを並べただけだとrank()の計算ができなくなる。そこでtiny_sbvとrank()の値のオフセットをペアにして持たせておいてrank()の計算に利用する。詳しくは後述することにしてまずは実用版のsbvクラスの外観を示す。
#include <map>
#include <vector>
typedef std::pair<tiny_sbv, int> tsbv_pair;
class sbv {
std::vector<tsbv_pair> tsbv_;
public:
void set(int i);
bool get(int i) const;
void build();
int rank(int i) const;
int select(int i) const;
};tiny_sbvとint(rank()のオフセット用)のpairのvectorでデータ全体を管理している点とselect()が新規で追加されている点に注意。以降、各関数の詳細を見ていく。
まずset()とget()は以下のようになる。
void set(int i) {
int q = i / 256;
int r = i % 256;
while (q >= this->tsbv_.size()) {
this->tsbv_.push_back(tsbv_pair(tiny_sbv(), 0));
}
this->tsbv_[q].first.set(r);
}
bool get(int i) const {
int q = i / 256;
int r = i % 256;
if (q >= this->tsbv_.size()) { return false; }
return this->tsbv_[q].first.get(r);
}各tiny_sbvが256個のビットを管理できるので指定されたビットの位置iを256で割った商(i / 256)で何番目のtiny_sbvを使うかが、余り(i % 256)でtiny_sbvの何番目のビットにアクセスすればよいかがわかる。またset()については現在のtiny_sbvで管理できる最大のビットより大きい位置を指定された場合は、該当ビットを保持できるまでpush_back()してvectorを拡張している。
次にbuild()。これは各tiny_sbvのbuild()を実行することと、直前のtiny_sbvまでのrank()の累計値を持たせること、の2つをすれば良い。具体的には以下の通り。
void build() {
std::vector<tsbv_pair>::iterator i = this->tsbv_.begin();
std::vector<tsbv_pair>::iterator e = this->tsbv_.end();
ull sum = 0;
while (i != e) {
i->first.build();
i->second = sum;
sum += i->first.rank(255);
i++;
}
}そして肝心のrank()。
int rank(int i) const {
int q = i / 256;
int r = i % 256;
tsbv_pair t;
int j;
if (q >= this->tsbv_.size()) {
t = this->tsbv_.back();
j = t.second + t.first.rank(255);
} else {
t = this->tsbv_[q];
j = t.second + t.first.rank(r);
}
return j;
}これはset()やget()と同様に、iをtiny_sbvのサイズ256で割った商と余りでアクセスするtiny_sbvと位置を決める。直前のtiny_sbvまでのrank()オフセットに現在のtiny_sbvでのrank()を足してあげれば全体での正しいrank()を得ることができる。
ここまでで実装した実用版ビットベクトルを使うことで256次元以上の疎ベクトルを実現できる。
int main() {
sbv b;
vector<int> v;
b.set(400); v.push_back(10);
b.set(1000); v.push_back(20);
b.build();
cout << "400: " << get_value(b, v, 400) << endl;
cout << "1000: " << get_value(b, v, 1000) << endl;
return 0;
}結果は以下のとおり。
$$ ./a.out 400: 10 1000: 20
ここまでで任意サイズを扱える簡潔ビットベクトルが実現できた。ここからはもうひとつのトピックであるselect()の実装例について紹介する。
まず復習のためrank()とselect()の定義を再掲する。
rank(x) : x番目のビット以前(xの位置を含む)の立っているビットの数 select(i): i番目に立っているビットの位置
前回の記事でこれらは逆関数の関係にあると説明した。これを具体例を用いて解説する。まず以下のビットベクトルを考える。
01001001
これに対してrank()は以下のようになる。
rank(0)=0 rank(1)=1 rank(2)=1 rank(3)=1 rank(4)=2 rank(5)=2 rank(6)=2 rank(7)=3
ここでrank()は単調増加関数であることに注意する。またselect()は以下のようになる。
select(1)=1 select(2)=4 select(3)=7
ビットベクトルでビットが立っている位置(1,4,7)についてはselect(rank(i))=iとなっていることがわかる。
単調増加する関数の逆関数は二分探索で実現できる。以下これについて説明する。例えばselect(1)を計算したいとする。これにはrank(i)=1となるiを見つければ良い。まずビットベクトルの真ん中の位置i=4についてrank()を計算する。するとrank(4)=2なので真ん中よりは前方に正解があることがわかる。つまり以下の通り。
rank(0)=0 rank(1)=1 rank(2)=1 こっちに正解がある rank(3)=1 rank(4)=2 < いまここ rank(5)=2 rank(6)=2 こっちに正解はない rank(7)=3
次に0から3までの部分の真ん中の位置i=2についてrank()を計算する。するとrank(2)=1なので問題の位置が見つかったことがわかる。が。すでにお気づきのようにrank()は同じ値を持つものが幾つか並んでいる。ではどの位置が正解なのかというとビットベクトルでビットが立っている位置が正解(ビットが立っている位置について逆関数になっていることは上で説明した。)。
よって二分探索で見つけた位置からビットが立っている位置までビットベクトルを遡る。するとi=1の位置でビットが立っていることがわかる。つまり以下の通り。
ビット rank 0 rank(0)=0 1 rank(1)=1 < ビットが立っているここまで遡る 0 rank(2)=1 < 二分探索でここまできた 0 rank(3)=1 1 rank(4)=2 0 rank(5)=2 0 rank(6)=2 1 rank(7)=3
以上のことをコードに落とすと以下のようになる。
int select(int i) const {
int l = 0;
int r = this->tsbv_.size() * 256;
// 二分探索
while (l < r) {
int p = (l + r) / 2;
int j = this->rank(p);
if (i < j) { r = p; }
else if (i > j) { l = p + 1; }
else {
// 二分探索に成功したのでビットが立っている位置まで遡る
while (this->get(p) == false) { p--; }
return p;
}
}
return -1;
}select()を使うことで密ベクトルから対応した次元を見つけることができる。
int main() {
sbv b;
vector<int> v;
b.set(400); v.push_back(10);
b.set(1000); v.push_back(20);
b.build();
cout << "select(1): " << b.select(1) << endl;
cout << "select(2): " << b.select(2) << endl;
return 0;
}結果は以下のとおり。
$$ ./a.out select(1): 400 select(2): 1000
以上で任意サイズのデータとrank()/select()が完備された簡潔ビットベクトルを実装することができた。rank()/select()を備えたビットベクトルを使うことで部分和をO(logN)で計算できるデータ列を実装することができたりする。これについては別の機会に紹介したい。
