簡潔データ構造第2.5回: ビットベクトルに対する簡潔データ構造 (select編)

こんにちは。レトリバのリサーチャーの木村@big_wingです。前回の2回目の記事ではビットベクトルに対するrank演算を実現する簡潔データ構造を紹介しましたが、今回はselect演算を実現する簡潔データ構造を紹介します。 1回目の記事はこちらです。 2回目の記事はこちらです。

簡潔データ構造をさらに詳しく知りたい方向けの紹介として、Navarro氏の本、日本語で書かれたものとしては定兼氏の本と岡野原氏の本があります。

ビットベクトルに対するselect演算
select演算を実現する簡潔データ構造
- selectの実現: 2種類の大ブロックによる分割
  - 疎ブロックに対するデータ構造
  - 密ブロックに対するデータ構造
- selectの実現: 計算方法
まとめ

ビットベクトルに対するselect演算

第2回の記事の流用になりますが、今回対象となるselect演算を確認します。今、 $B[1,n]$ , $B[i] \in \{0,1\}$ を長さ $n$ のビットベクトルとします。またこれ以降 $\rm{lg} \it{n} = \rm{log}_2 \it{n}$ とします。このビットベクトルに対しselect演算を、

select $_b$ $(B,i)$ : $B$ の先頭から見て $i$ 番目に出現する $b \in \{0,1\}$ の位置を返す

と定義します。添字が多くてぱっと見理解しにくいので、具体例で確認してみましょう。下の図において、上段がビットベクトル $B$ の位置を表すインデックスで、下段がビットベクトルの要素です。

i: 1 2 3 4 5 6 7 8 9 
B: 0 1 1 1 0 1 0 0 1

今、select $_ 1$ $(B,2)$ という演算について見てみましょう。これはselectの定義から $B$ の先頭から見て2番目に出現する1の位置です。図を見てみると $B$ の先頭から見て2番目に出現する1の位置は3となるので、select $_ 1$ $(B,2)=3$ となります。同様にselect $_ 1$ $(B,5)=9$ 、select $_ 0$ $(B,3)=7$ となります。

select演算を実現する簡潔データ構造

これからビットベクトルに対する情報理論的下限である $n + \rm{o}(\it{n} \rm{)}$ ビットの空間領域で、select $_ 1$ $(B,i)$ 演算を定数時間で実現するデータ構造を説明します。紹介するデータ構造は提案者らの名前にちなんでRRRと呼ばれています (論文)。(RRRはselect演算のみを実現するものではなく、前回紹介したrank演算などを含めたデータ構造です。)

selectの実現: 2種類の大ブロックによる分割

select $_ 1$ $(B,i)$ 演算ための最初のステップとして、 $B[1,n]$ を大ブロックに分割し、それぞれの大ブロックを長さによって2種類に区別します。

今 $l =$ $(\rm{lg}$ $n )^{2}$ として、各大ブロックに含まれる1の数が $l$ となるように $B[1,n]$ を分割します。(最後の大ブロックに含まれる1の数は $l$ 以下となります。) このように分割することによって、一般に各大ブロックの長さは異なります。それぞれの大ブロックを長さによって疎ブロックと密ブロックと区別します。

疎ブロック: 長さが $(\rm{lg}$ $n )^{4}$ 以上の大ブロック
密ブロック: 長さが $(\rm{lg}$ $n )^{4}$ 未満の大ブロック

この疎、密という表現ですが、大ブロックの分割ルールから各大ブロックに含まれる1の数は $l$ です。そのため、1があまり出現しない部分では大ブロックの長さが長くなり (=疎ブロック)、1が頻繁に出現する部分では大ブロックの長さが短くなります (=密ブロック)。具体例を見てみましょう。

f:id:big_wing_ik:20200925141924p:plain — ビットベクトルの大ブロック分割の例: l = 2

上の図はビットベクトルを $l = 2$ 、 $(\rm{lg}$ $n )^{4} = 4$ として分割した例になります。内部にちょうど $l = 2$ 個の1を含むように大ブロックとして分割し、その長さが $(\rm{lg}$ $n )^{4} = 4$ 以上のものを疎ブロック、そうでないものを密ブロックとします。また最後の大ブロックについては1を1個のみ含みます。

次にselect $_ 1$ $(B,i)$ の値の計算のために、分割した各大ブロックに付随するデータ構造を用意します。各大ブロックが疎か密であるかによって付随するデータ構造の種類が異なります。

これら各大ブロックに付随するデータ構造へのポインタのサイズは、大ブロックの個数が高々 $n/l$ であることから $\rm{O}$ $(\rm{lg}$ $n \times$ $(n/l)) =$ $\rm{O}$ $(n/ \rm{lg}$ $n ) =$ $\rm{o}(\it{n} \rm{)}$ ビットです。また各大ブロックが疎であるか密であるかは、 $\ n/l =$ $n/(\rm{lg}$ $n )^{2} =$ $\rm{o}(\it{n} \rm{)}$ のサイズのビットベクトルで判断することができます。

疎ブロックに対するデータ構造

疎ブロックに対するデータ構造は簡単で、各疎ブロックにおいて内部の1の出現する位置をそのまま保持します。

疎ブロックの長さは $(\rm{lg}$ $n )^{4}$ 以上なので、疎ブロックの個数は高々 $n/(\rm{lg}$ $n )^{4}$ 個です。また1の出現位置を表現するには全体のビットベクトルの長さが $n$ であることから $\rm{lg}$ $n$ ビット必要です。疎ブロックに含まれる1の数は $l =$ $(\rm{lg}$ $n )^{2}$ であることから、疎ブロック対するデータ構造の空間計算量はビットベクトル全体で $\rm{O}$ $( (n/(\rm{lg}$ $n )^{4})$ $\times$ $(\rm{lg}$ $n )^{2}$ $\times$ $\rm{lg}$ $n )=$ $\rm{O}$ $( n/ \rm{lg}$ $n )$ $= \rm{o}(\it{n} \rm{)}$ ビットです。

密ブロックに対するデータ構造

密ブロックに対しては、まず各密ブロックを $s = \frac{1}{2}$ $\rm{lg}$ $n$ の長さの小ブロックに分割します。密ブロックの長さは最大で $(\rm{lg}$ $n )^{4}$ なので、小ブロックの個数は高々 $(\rm{lg}$ $n )^{4}/s =$ $2(\rm{lg}$ $n )^{3}$ 個です。

次に天下り的ですが、これら高々 $2(\rm{lg}$ $n )^{3}$ 個の小ブロックを葉に対応させた完全 $\sqrt{\rm{lg}\it n}$ 木を構築します。葉ノードには対応する小ブロックに含まれる1の数を持たせ、内部ノードにはそのノードの子孫に含まれる1の数の和を持たせます。また重要な点として、完全 $\sqrt{\rm{lg}\it n}$ 木であることから陽にポインタを持つことなく、これらの各ノードに対する値は幅優先探索順に連続したメモリに保持することができます。さらに葉の数が高々 $2(\rm{lg}$ $n )^{3}$ 個であることからこの木の高さは定数となります。具体例を見てみましょう。

f:id:big_wing_ik:20200925233208p:plain — 密ブロックに対するデータ構造の例. 仮想的にs=3, 完全3分木とする

上図は仮想的に、ある密ブロックが011010000111001000000100000、 $s = 3$ 、 $\sqrt{\rm{lg}\it n} = 3$ とした例です。密ブロックを $s=3$ の長さの小ブロックで分割し、各小ブロックに含まれる1の数を葉ノードに割り当てます。上図の例では1番目の小ブロック011に含まれる1の数は2個なので、左端の葉には2を割り当てます。また上図の例では完全 $\sqrt{\rm{lg}\it n} = 3$ 分木となり、内部ノードには子孫のノードに含まれる1の数の和を保持させます。例えば左端の内部ノードの子孫に含まれる1の数は3個なので、左端の内部ノードには3を割り当てます。これら各ノードの値を幅優先探索順に連続したメモリに保持させます。この例の場合は341 210 310 010といった順に保持します。

この完全 $\sqrt{\rm{lg}\it n}$ 木の空間計算量についてビットベクトル全体で考えてみましょう。まず葉ノードについて考えます。各小ブロックの長さは $s = \frac{1}{2}$ $\rm{lg}$ $n$ であることから小ブロック内に含まれる1の数は高々 $s$ となり、各葉ノードを表現するには $\rm{lg}$ $(s+1)$ ビット必要です。葉ノードの数はビットベクトル全体で $\rm{O}$ $(n/s)$ 個であることから、葉ノードに必要な空間計算量はビットベクトル全体で $\rm{O}$ $(\rm{lg}$ $(s+1) \times$ $n/s)=$ $\rm{O}($ $n \rm{lglg}$ $n/ \rm{lg}$ $n) = \rm{o}(\it{n} \rm{)}$ ビットです。次に内部ノードについて考えます。大ブロックに含まれる1の個数は $l =$ $(\rm{lg}$ $n )^{2}$ であることから、内部ノードに割り当てられる数は $\rm{O}$ $(\rm{lg}$ $(l+1))=$ $\rm{O}$ $(\rm{lglg}$ $n)$ ビットで表現することができます。また内部ノードの数は $\rm{O}$ $(n/s)$ 個であることから、内部ノードに必要な空間計算量は $\rm{O}$ $(n/s \times (\rm{lglg}$ $n))=$ $\rm{O}($ $n \rm{lglg}$ $n/ \rm{lg}$ $n)$ $= \rm{o}(\it{n} \rm{)}$ ビットです。よってからビットベクトル全体で密ブロックに対するデータ構造の空間計算量は $\rm{o}(\it{n} \rm{)}$ ビットとなります。

以上から疎ブロックと密ブロックに付随するデータ構造の空間計算量は $\rm{o}(\it{n} \rm{)}$ ビットとなります。また以前説明したようにこれらのデータ構造へのポインタと、各大ブロックの疎密を判断するための補助的なデータ構造の空間計算量はいずれも $\rm{o}(\it{n} \rm{)}$ ビットとなります。

selectの実現: 計算方法

最後にこれまで紹介したデータ構造を用いてselect $_ 1$ $(B,i)$ をどのように計算するか見てみましょう。今、各大ブロックはちょうど $l$ 個の1を含むので $i$ 番目の1が属する大ブロックは $\lceil \ i/l \ \rceil$ で得ることができます。またこの大ブロックが疎であるか密であるかは補助的なデータ構造を用いて定数時間で得ることができます。今、 $i$ が $k$ 番目の大ブロックに属するとしましょう。 $i$ 番目の1はこの番目の大ブロックの $i - l(k-1)$ 番目の1となります。

この大ブロックが疎の場合は、答えがそのまま保持されているので答えを定数時間で得ることができます。

この大ブロックが密の場合は、対応する完全 $\sqrt{\rm{lg}\it n}$ 木を根から葉に向かって答えとなる1の属する葉ノードを求めます。まず根から子の $\sqrt{\rm{lg}\it n}$ 個のノードを読み込みます。密ブロックに対するデータ構造でみたようにこれらは幅優先順にメモリに連続した箇所にあり、かつそのビット数は $\rm{O}($ $\sqrt{\rm{lg} \it{n}} \rm{lglg}$ $n)$ $= \rm{o}(lg \it{n} \rm{)}$ となり、連続する $\rm{lg}\it{n}$ ビットのメモリを定数時間で読み込むことができるというWord RAMモデルの仮定から定数時間で読み込むことができます。この読み込んだ値と $i - l(k-1)$ というクエリの2つを用いて答えの1が属するノードを2次元の表引きによって定数時間で得ることができます。以下に表の例を示します。あらかじめ読み込んだ値とクエリの全パターンに対して1が属する子ノードを答えとして用意しておきます。計算が煩雑になるために詳細は省略しますが、このような表のサイズは $\rm{o}(\it{n} \rm{)}$ ビットとなります。この操作を葉ノードに達するまで再帰的に繰り返します。葉ノードにおいては、答えとなる1の位置は同様な表引きによって得ることができます。木の高さが定数であることから上記の一連の操作は定数時間で行うことができます。以上よりselect $_ 1$ $(B,i)$ を定数時間で行うことができます。

具体例を見て確認してみましょう。

f:id:big_wing_ik:20200927161048p:plain — 表の例. 表の値は次に進むべき子ノードを表す.

f:id:big_wing_ik:20200927141218p:plain — 再掲: 密ブロックに対するデータ構造の例.

以前の図の再掲となりますが、今答えとなる1が属する大ブロックが上図のような密ブロックとします。この密ブロックにおいて5番目に出現する1の位置を求めるselect $_ 1$ $(B,5)$ を計算する流れを見てみましょう。上の図においては5番目の1は4番目の小ブロックの黒字の1となり、select $_ 1$ $(B,5) = 11$ となります。

まず根の子ノードとなる341を定数時間で読み込みます。この読み込んだ値とクエリの5をもとに表引によって答えの属する子ノードを定数時間で得ることができます。この場合は表の赤字となっている2番目のノードが答えです。さらに2番目より左のノードには1が3個含まれるので、子孫では新たなクエリとして $5 -3 = 2$ 番目に出現する1の位置を探索します。このあるノードより左の1の個数を得る計算も表引きによって定数時間で行うことができます。

次に2番目のノードに移動し、その子ノードとなる310を定数時間で読み込みます。この読み込んだ値と新たなクエリである2をもとに表引きによって答えの属する子ノードを定数時間で得ることができます。この場合は1番目のノードです。左端のノードのためクエリは2のままです。

最後に1番目ノードに移動して葉ノードに到達しました。ここで答えの属する小ブロックが4番目の小ブロックであることがわかりました。この小ブロックにおいて2番目に出現する1の位置をやはり同様に表引きによってよって定数時間で得ることができ、最終的な答えであるselect $_ 1$ $(B,5) = 11$ を得ます。

まとめ

簡潔データ構造の紹介の2.5回目である今回は、ビットベクトルに対するselect演算を実現する簡潔データ構造について紹介しました。 rank演算に比べるとだいぶ複雑です。今回はselect $_ 1$ 演算について説明しましたが、select $_ 0$ 演算の場合もビットベクトルを反転させたものに対して同様のデータ構造を作成することで実現できます。また今回は理論的な側面を紹介しましたが実際の実装になると注意すべき点や工夫すべき点が様々あります。実装の一つとして様々な種類の簡潔データ構造が実装されているライブラリがあります。より深く知りたい方はこちらの実装や最初に紹介した本に触れてみてください！次回はビットベクトルの拡張となる一般の文字列に対する簡潔データ構造か木構造に対する簡潔データ構造について紹介する予定です。