selectだけで実現できるLOUDS

ふと思い立って、LOUDSってビット列上の位置は不要で子ノードのIDだけわかればいいのでは、という気がした。この場合LOUDSの各種操作はselect()だけで良くなりrank()を使わなくなる。通常、簡潔ビットベクトルではselect()のほうが遅いのであまり効果は無いかもしれないが、それでも少しでも速いほうがいいはず。ってことで試してみた。

というわけでコードを置いておく。要望があればあとで解説を書く。
拙作のshellinfordライブラリの簡潔ビットベクトルを使ったが、他のライブラリでも同じように実装できるはず。

shellinford - shellinford: succinct document retrieval library - Google Project Hosting

#include <iostream>
#include "shellinford_bit_vector.h"

using namespace std;
using namespace shellinford;

// 親ノードIDを得る
uint64_t parent(const bit_vector &bv, uint64_t id) {
  if (id == 0) { return bv.size(true); }
  uint64_t s = bv.select(id, false);
  uint64_t n = s - id;
  return n;
}
// i番目の子ノードIDを得る
uint64_t ith_child(const bit_vector &bv, uint64_t id, uint64_t i) {
  uint64_t s = 0;
  if (id > 0) { s = bv.select(id - 1, true); }
  uint64_t n = s - id + i + 1;
  if (bv.get(s + 1)) { n = 0; }
  return n;
}
// 子ノード数を得る
uint64_t degree(const bit_vector &bv, uint64_t id) {
  uint64_t d = bv.select(id, true) - 1;
  if (id > 0) { d -= bv.select(id - 1, true); }
  return d;
}

int main() {
  try {
    // 以下の木をLOUDSで表現する
    cout << "0 => {1}"       << endl;
    cout << "1 => {2, 3, 4}" << endl;
    cout << "2 => {5, 6}"    << endl;
    cout << "4 => {7}"       << endl;

    // 各ノードの子ノード数をLevel-Orderで並べたもの
    vector<uint64_t> tree;
    tree.push_back(1);
    tree.push_back(3);
    tree.push_back(2);
    tree.push_back(0);
    tree.push_back(1);
    tree.push_back(0);
    tree.push_back(0);
    tree.push_back(0);

    // Jacobson's LOUDS
    uint64_t cur = 0;
    bit_vector louds;
    vector<uint64_t>::iterator it;
    for (it = tree.begin(); it != tree.end(); it++) {
      cur += (*it + 1);
      louds.set(cur);
    }
    louds.build();

    // 各種操作をテスト。いずれもselect()を定数回呼ぶだけでOK。
    for (uint64_t i = 0; i < tree.size(); i++) {
      cout << "parent(" << i << ") = "
           << parent(louds, i) << "\t";
      cout << "1st child(" << i << ") = "
           << ith_child(louds, i, 0) << "\t";
      cout << "degree(" << i << ") = "
           << degree(louds, i) << endl;
    }

  } catch (const char *err) {
    cerr << "ERR: " << err << endl;
    return 1;
  }
  return 0;
}

これをlouds.ccとして保存。実行結果は以下のとおり。

$$ g++ louds.cc -lshellinford
$$ ./a.out
0 => {1}
1 => {2, 3, 4}
2 => {5, 6}
4 => {7}
parent(0) = 8	1st child(0) = 1	degree(0) = 1
parent(1) = 0	1st child(1) = 2	degree(1) = 3
parent(2) = 1	1st child(2) = 5	degree(2) = 2
parent(3) = 1	1st child(3) = 0	degree(3) = 0
parent(4) = 1	1st child(4) = 7	degree(4) = 1
parent(5) = 2	1st child(5) = 0	degree(5) = 0
parent(6) = 2	1st child(6) = 0	degree(6) = 0
parent(7) = 4	1st child(7) = 0	degree(7) = 0