簡潔Bit Vectorの定数時間rank/select
本記事は定兼邦彦「簡潔データ構造」を元に記載しています。
はじめに
長さ$n$の01列に対して、
- $\mathrm{rank}_x(i)$: $i$番目までに出現する$x$の個数を求める
- $\mathrm{select}_x(j)$: 先頭から$j$番目の$x$のindexを求める
の2種類のクエリを考える。 本記事では、この2つのクエリを定数時間で処理し、メモリを$n + \mathrm{O}(n \lg \lg n / \lg n)$bitしか用いないデータ構造を説明する。 これは$n + \mathrm{o}(n)$なので、簡潔1な表現になっている。
計算モデルはword RAMを用い、計算機の語調を$\lg U$ビットとして、入力長$n$に対して$\lg n = \mathrm{O}(\lg U)$が成り立つものとする。
rank
$\mathrm{rank}_1(i)$が求まれば$\mathrm{rank}_0(i) = i - \mathrm{rank}_1(i)$で計算できるので、以下$\mathrm{rank}_1$の求め方を記載する。 まず、全体を長さ$\lg^2(n)$の大ブロックに分割する。 各大ブロックにはその前の大ブロックまでの先頭からの累積和を格納しておく(A)。 次に、各大ブロックを長さ$\frac{1}{2} \lg n$の小ブロックに分割する。 各小ブロックには、大ブロックの先頭から1つ前の小ブロックまでの累積和を格納する(B)。 最後に、長さ$\frac{1}{2} \lg n$の全てのビット列のパターンに対して1の登場回数を格納したlookup tableを作っておく(C)。 これらを用いると、クエリの際は大ブロック→小ブロック→lookup tableの順に見ることで答えを$\mathrm{O}(1)$で求めることができる。 最後のlookup tableのキーとなるインデックスを定数時間で求められるのは、word RAMで長さ$\frac{1}{2} \lg n$以下の連続するbit列を$\mathrm{O}(1)$で取り出すことができるためである。
メモリの確認
- Aは、各大ブロックの値のbit長が$\mathrm{O}(\lg n)$なので、全体で$\mathrm{O}(\lg n \cdot \frac{n}{\lg ^2 n}) = \mathrm{O}(n / \lg n)$。
- Bは、各小ブロックの値のbit長が$\mathrm{O}(\lg (\lg^2 n)) = \mathrm{O}(\lg \lg n)$であるので、全体で $\mathrm{O}(\lg \lg n \cdot \frac{n}{\lg n / 2}) = \mathrm{O}(n \lg \lg n / \lg n)$。
- Cは、ビットのパターン数・値のビット長の順に考えると、$\mathrm{O}(2 ^ {\lg n / 2} \cdot \lg \lg n) = \mathrm{O}(\sqrt n \lg \lg n) = \mathrm{o}(n \lg \lg n / \lg n)$。
select
$\mathrm{select}_0$は$\mathrm{select}_1$と同様に実現できるので、以下$\mathrm{select}_1$について記載する。 まず、全体を各ブロックに1をちょうど$\lg^2 n$個含むように大ブロックに分割する。 長さ$\lg ^4 n$以上の疎な大ブロックについては、その中の全ての1のインデックスを記録しておく(A)ことで$\mathrm{O}(1)$で答えを求めることができる。 それ以外の密な大ブロックの扱いを以下に述べる。 まず長さ$\frac{1}{2} \lg n$の小ブロックに分割する。 そして、1つの大ブロック内の小ブロックたちを葉に持つような完全$\sqrt{\lg n}$分木を構築する(B)。 葉の数が$\mathrm{O}(\lg^3 n)$なので、木の高さは定数である。 木のノードには、部分木内の葉に対応する小ブロックに含まれる1の数の和を格納しておく。 また、これらは木の幅優先順にメモリに載せ、各ノードの子たちが連続した領域に存在しておくようにする。 密な大ブロックないのクエリを答える際は、木のどの子に降りるべきかのlookup tableを(子たちの1の個数の分布の全パターン)$\times$(何番目の1を求めたいか)について用意しておき(C)、それをたどっていく。 最後にたどり着いた内のクエリも、別の(bitのパターン)$\times$(何番目の1を求めたいか)のlookup tableを(D)を用意しておくことで定数時間で計算することができる。
メモリの確認
- Aは、大ブロック内の1の個数・indexのbit数・大ブロックの個数の順に考えて、$\mathrm{O}(\lg^2 n \cdot \lg n \cdot \frac{n}{\lg^4 n}) = \mathrm{O}(n / \lg n)$。
- Bは、全ノードの個数が全葉の個数の定数倍で抑えられるため$\mathrm{O}(n / \frac{1}{2}\lg n)$であり、格納する値は$\lg^2 n$までなので、合わせて$\mathrm{O}(\lg (\lg^2 n) \cdot \frac{n}{\lg n}) = \mathrm{O}(n \lg \lg n / \lg n)$。
- Cは、子たちの1の個数のパターン数・何番目を求めたいかのパターン数・降りるべき子を表すbit長の順に考えて、$\mathrm{O}(\sqrt{\lg n} ^ {\sqrt{\lg n}} \lg n \cdot \lg^2 n \cdot \lg \sqrt{\lg n}) = \mathrm{o}(n \lg \lg n / \lg n)$となる。
- Dは、ビットのパターン数・何番目を求めたいかのパターン数・indexのビット長の順に考えて、$\mathrm{O}(2 ^ {\lg n / 2} \cdot \lg^2 n \cdot \lg(\lg^4 n)) = \mathrm{o}(n \lg \lg n / \lg n)$となる。
終わりに
$\mathrm{rank}$に関しては、ワード長の定数時間popcountを許して32bitや64bitごとに区切るもの(例えば$\lg n / 2$で1回だけ区切るとコンパクト2になります)が実用的かなあと思っています。 $\mathrm{select}$は、このアルゴリズムだと見た目の通り定数倍が非常に大きくなってしまって実用的ではなさそうです…。 実用的には$\mathrm{rank}$を用いて二分探索をするとしているものが多いのですが、コンパクトな表現でもいいのである程度実用的な定数時間の実装を知っている方がいたらぜひ教えて下さい。