簡潔データ構造超入門 〜つくって学ぶ簡潔ビットベクトル〜

計算機科学

簡潔データ構造は各種操作を高速に保ったままでデータサイズを情報理論的な下限近くまで圧縮できる。大規模データを扱うことの多くなってきた現在、特に注目を集めている技術である(※個人的な見解です)。
しかし有用性とは裏腹にまとまった教科書等がないこともあり入門者に対して敷居が高いようにも感じられる。そこで本記事では簡潔データ構造の基本であるビットベクトルに対する簡潔構造の実装方法をC/C++のコードを交えて解説してみる。
ビットベクトルに対する簡潔構造は、単純には疎ベクトルを表現するのに利用することができる。よって本記事でも簡潔ビットベクトルを実装し、疎ベクトルを実現してみようと思う。


今回は疎ベクトルとして値がint(4byte)の256次元のベクトルを考える。ただし疎ベクトルなので256次元のうちいくつかの次元にしか値が入っていないものを仮定する。例えば

v[5]     = 10
v[100] = 20
v[180] = 30

v[i] = 0;  i != 5, 100, 180

のようなものを考えると良い。
このときサイズが256の配列で疎ベクトルを表現しようとすると4byte*256=1KBのデータサイズになる。値を持っている次元は3つしかないので、これでは効率が悪い。
そこでビットベクトルを使う。具体的には

00000100 00000000 00000000 00000000
00000000 00000000 00000000 00000000

00000000 00000000 00000000 00000000
00001000 00000000 00000000 00000000

00000000 00000000 00000000 00000000
00000000 00000000 00001000 00000000

00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000

のように値が入っている次元だけビットが立っているようなものを考える。このビットベクトルは256次元分のビットがあればよいので256bit=32byte必要となる。このような疎ベクトル(より一般には集合)を表したビットベクトルを簡潔ビットベクトルという。
簡潔ビットベクトルに対してはrank()およびselect()と呼ばれる操作が定義される。具体的には

rank(x)  : x番目のビット以前(xの位置を含む)の立っているビットの数
select(i): i番目に立っているビットの位置

という操作を指す。これらの操作は逆関数の関係にあるので一方(例えばrank)を定数時間で実現して、もう一方(例えばselect)を2分探索で実現する事が多い。今回の例ではrank()だけしか使わないのでrank()の定数時間での実装を解説する。
さて話を戻すと疎ベクトルを効率的に実現したいという話だった。これは簡潔ビットベクトルのrank()を使うことで可能となる。
具体的には、まず疎ベクトルで値を持っている次元の値を次元の昇順で並べた密ベクトルを作る。つまり

v[0] = 10
v[1] = 20
v[2] = 30

とする。これには4byte*3=12byte必要となる。そして前述の簡潔ビットベクトルでどの次元に要素が入っているかを表現する。これにはすでに述べたように32byte必要。
ここでrank()を使うことで次元が指定されたときに密ベクトルのどの要素を見れば良いのかが計算できる。どういうことかというとrank(x)は「x番目のビット以前(xの位置を含む)の立っているビットの数」なので疎ベクトルの「x番目の次元までで値をもっている次元の数」を表している。
なので例えばrank(5)=1なので5番目の次元までに値を持っている次元は1つということになる。ということは密ベクトルの0番目の要素v[0]の値である10が5番目の次元のもつ値だということがわかる。
今回のrank()の実装では詳しくは後述するが4byteの予備領域を使う。よって密ベクトルの12byte、簡潔ビットベクトルの32byteと合わせて48byteで疎ベクトルが実現できたことになる。これは元の疎ベクトルのサイズ1KBに比べて大幅に省メモリであることがわかる。


さて。簡潔ビットベクトルの有用性がわかったところで、ここからは実装の解説をする。まずは簡潔ビットベクトルのクラスsbvの概要を示す。

typedef unsigned long long ull;    // 8byte
typedef unsigned char      uc;    // 1byte

class sbv {
  ull B_[4];    // 32byte
  uc  r_[4];    // 4byte

public:
  sbv();
  void set(int i);
  bool get(int i) const;
  void build();
  int rank(int i) const;
};

B_とr_はそれぞれビットベクトル、rank()のための予備領域をもたせる変数。sbv()はコンストラクタ。set()はi番目のビットを立たせる。get()はi番目のビットが立っているかどうかを返す。build()はrank()のための前準備を行いr_に値をセットする。rank()は前述のとおり。
まずはコンストラクタから。ここは単純に値の初期化をする。256bitのビットベクトルは8byteのunsigned long long型を4つ並べて表現する。

sbv() {
  for (int i = 0; i < 4; i++) {
    this->B_[i] = 0x0ULL;
    this->r_[i] = 0;
  }
}

次にset()とget()。これはビット演算を使って特定のビットの値を変更したり取り出したりする。

void set(int i) {
  ull b = 0x1ULL << (i % 64);
  this->B_[i / 64] |= b;
}
bool get(int i) const {
  ull m = 0x1ULL << (i % 64);
  return this->B_[i / 64] & m;
}

build()では予備領域r_に値をセットする。r_[0]は0が、r_[1]は最初の64bitで立っているものの数が、r_[2]は最初の128bitで立っているものの数が、r_[3]は最初の192bitで立っているものの数が、それぞれセットされる。この値を事前に計算しておくことでrank(i)を計算する際にはB_[i /64]の最初の(i % 64 + 1)bitでいくつビットが立っているかだけを調べてr_[i /64]の値を足せばよくなる。B_の要素は64bitなのでpopcount64()という操作で定数時間で立っているビットの数が計算できる。popcount64()については基本的にはコードをコピペで良いと思う。詳細を知りたい方は

TAKESAKO @ Yet another Cybozu Labs: Binary Hacks と 64bit popCount 問題

を参照されると良い。話を戻すとbuild()、rank()、popcount64()のコードは以下のようになる。少々複雑なのでじっくり考えると良い。

void build() {
  this->r_[0] = 0;
  for (int i = 0; i < 3; i++) {
    this->r_[i + 1] = this->r_[i] + popcount64(this->B_[i]);
  }
}
int rank(int i) const {
  ull m = -1;
  if (i % 64 < 63) { m = (0x1ULL << (i % 64 + 1)) - 1; }
  return this->r_[i / 64] + popcount64(this->B_[i / 64] & m);
}

ull popcount64(ull x) {
  x = ((x & 0xaaaaaaaaaaaaaaaaULL) >> 1)
    +  (x & 0x5555555555555555ULL);
  x = ((x & 0xccccccccccccccccULL) >> 2)
    +  (x & 0x3333333333333333ULL);
  x = ((x & 0xf0f0f0f0f0f0f0f0ULL) >> 4)
    +  (x & 0x0f0f0f0f0f0f0f0fULL);
  x = ((x & 0xff00ff00ff00ff00ULL) >> 8)
    +  (x & 0x00ff00ff00ff00ffULL);
  x = ((x & 0xffff0000ffff0000ULL) >> 16)
    +  (x & 0x0000ffff0000ffffULL);
  x = ((x & 0xffffffff00000000ULL) >> 32)
    +  (x & 0x00000000ffffffffULL);
  return x;
}

以上でsbvクラスの実装は終わり。あとはこのクラスを使って疎ベクトルを実現してみる。

#include <iostream>
#include <vector>
using namespace std;

(ここにsbvクラスのコードを書く)

int get_value(const sbv &b, const vector<int> &v, int i) {
  if (b.get(i) == false) { return 0; }
  return v[b.rank(i) - 1];
}

int main() {
  sbv         b;
  vector<int> v;

  b.set(5); v.push_back(10);
  b.set(100); v.push_back(20);
  b.set(180); v.push_back(30);
  b.build();

  cout << "5: " << get_value(b, v, 5) << endl;
  cout << "100: " << get_value(b, v, 100) << endl;
  cout << "180: " << get_value(b, v, 180) << endl;
  cout << "200: " << get_value(b, v, 200) << endl;
  return 0;
}

これをコンパイルして実行すると以下のような結果が得られる。

$$ ./a.out
5: 10
100: 20
180: 30
200: 0

以上で解説は終わり。興味のある方はより大きな簡潔ビットベクトル作ってみたり、簡潔構造を使わない疎ベクトルとの要素アクセスの速度比較をしてみたりすると良い気がする。また今回は解説の簡単さのために予備領域を1段階にしたが通常は予備領域は2段階にして持たせる事が多い。この辺りも興味があれば調べてみると良い。
簡潔データ構造に関する資料は以下を参考にすると良いかも。

簡潔データ構造(Succinct Data Structure)で最初に読むと良さそうな論文 - EchizenBlog-Zwei