こんにちは。レトリバのリサーチャーの木村@big_wingです。COVID-19の影響でテレワークが推進されていますが、現在私も奈良県の生駒市からフルリモートで業務を行っています。今回は簡潔データ構造について2回目の記事で、あらゆる簡潔データ構造の基本となるビットベクトルに対する簡潔データ構造を紹介します。 1回目の記事はこちらです。

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

ビットベクトルに対する簡潔データ構造

ビットベクトルに対する簡潔データ構造

最初にビットベクトルに対する簡潔データ構造を扱うモチベーションについて簡単に説明します。簡潔データ構造の枠組みにおいて文字列、木、グラフなど様々な離散データ構造はまず、0,1のビットベクトルとしてエンコードされます。その後エンコードされたビットベクトル上で演算を行うことで、例えば木であれば親ノードにアクセスしたり、子ノードにアクセスしたりといった演算を実現します。このように複雑な離散構造やそれに対する演算もビットベクトル上の演算に還元されるため、ビットベクトルに対する簡潔データ構造はあらゆる簡潔データ構造の基本となっており、とても重要です。

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

今、 $B[1,n]$ , $B[i] \in \{0,1\}$ を長さ $n$ のビットベクトルとします。このビットベクトルに対して、

access $(B,i)$ : $B[i]$ を返す
rank $_b$ $(B,i)$ : $B[1,i]$ の中に含まれる $b \in \{0,1\}$ の数を返す
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

accessの例

まず最も簡単なaccessについて見てみましょう。accessは位置に対応するビットベクトルの要素を返す演算なので上の図においては、access $(B,4)=1$ 、access $(B,7)=0$ となります。

rankの例

次にrankです。今、rank $_ 1$ $(B,5)$ という演算について見てみましょう。これはrankの定義から $B[1,5]$ の中に含まれる1の数となります。 $B[1,5]$ においては $B[2]$ 、 $B[3]$ 、 $B[4]$ が1となり、 $B[1,5]$ の中に含まれる1の数は3個です。よって rank $_ 1$ $(B,5)=3$ となります。

同様にrank $_0$ $(B,6)$ という演算について見てみましょう。これはrankの定義から $B[1,6]$ の中に含まれる0の数となります。 $B[1,6]$ においては $B[1]$ 、 $B[5]$ が0となり、 $B[1,6]$ の中に含まれる0の数は2個です。よって rank $_ 0$ $(B,6)=2$ となります。

また少し考えてみるとrank $_ 0$ $(B,i)$ とrank $_ 1$ $(B,i)$ の間にはrank $_ 0$ $(B,i)+$ rank $_ 1$ $(B,i)= i$ の関係が成り立っていることがわかります。これによってrank $_ 0$ $(B,i)$ とrank $_ 1$ $(B,i)$ のうち片方の値が得られればもう一方の値も直ちに得ることができます。

selectの例

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

ビットベクトルの情報理論的下限

1回目の記事の復習となりますが、簡潔データ構造を定量的に定義するにあたって必要な情報理論的下限をビットベクトルに対して考えてみましょう。今、要素数が $S$ である集合に対して情報理論的下限 $L$ は $L = \rm{lg} \lceil \it{S} \rceil$ ビットと定義されます( $\rm{lg} \it{n} = \rm{log}_2 \it{n}$ )。

長さ $n$ のビットベクトルは各要素が2通りの値を取るため、この集合の要素数は $2^{n}$ です。そのため情報理論的下限は $L = \rm{lg} 2^{\it{n}} = \it{n}$ ビットとなります。

よって上記に漸近する $n + \rm{o}(\it{n} \rm{)}$ ビットの空間領域でaccess、rank、selectの演算を高速に行うデータ構造を得ることが目標です。

ビットベクトルに対する簡潔データ構造の実現

最初に結論を述べると、長さ $n$ のビットベクトルに対して $n + \rm{o}(\it{n} \rm{)}$ ビットの空間領域で、access、rank、selectの演算を定数時間で実現するデータ構造が存在します(論文)。

accessは $n$ ビットのビットベクトルそのものを保持すれば自明に定数時間で行うことができます。残りはrankとselectですが、selectはrankに比べてデータ構造が非常に複雑となるため、今回はrankのみ扱います。また先に述べたようにrank $_ 0$ $(B,i)+$ rank $_ 1$ $(B,i)= i$ の関係が成り立つため、以降では $n + \rm{o}(\it{n} \rm{)}$ ビットの空間領域でrank $_ 1$ 演算を定数時間で実現するデータ構造について紹介します。

rankの実現: 着想

具体的なデータ構造の説明の前に、以下のような2つの極端な状況を考えてみましょう。

ビットベクトル以外に補助的なデータ構造を何も持たない
ビットベクトルのすべての位置に対してrank $_ 1$ の値を保存する

まず1. の状況です。この場合ビットベクトル以外に何も持たないことから、データ構造のサイズは全体で $n$ ビットです。しかし補助的な情報が何もないため、rank $_ 1$ $(B,i)$ を計算する際にはビットベクトルを先頭から $i$ 番目まで読み込む必要があり、時間計算量は $\rm{O}(\it{n} \rm{)}$ となってしまい、定数時間で演算を行うことができません。

次に2. の状況です。この場合はすべての位置に対してrankの値を保持しているので、rank $_ 1$ $(B,i)$ の値は定数時間で得ることができます。一方で $0 \leq$ rank $_ 1$ $(B,i) \leq n$ であることから、一つのrank $_ 1$ $(B,i)$ の値を表現するには $\rm{lg}$ $(n+1)$ ビットが必要となります。そのため2. の場合に補助的に必要となる空間計算量は $\rm{O}$ $(n \times$ $\rm{lg}$ $(n+1))=$ $\rm{O}$ $(n$ $\rm{lg}$ $n)$ ビットとなってしまい、情報理論的下限を大きく超えるメモリを必要とします。

つまりrank $_ 1$ $(B,i)$ の値を全く保持しない方針や全て保持する極端な方針では、時間計算量と空間計算量のいずれかで問題が発生します。そこでrank $_ 1$ $(B,i)$ の値をほどほどに保持すればよいのではないか？という気持ちになり、実際にそのような方針で所望のデータ構造が実現できます。

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

rank $_ 1$ $(B,i)$ の値をほどほどに保持するために、大ブロックとそれをさらに分割した小ブロックの2つを用いてビットベクトル $B[1,n]$ を分割します。

大ブロック: 長さ $l$ 、 $j$ 番目( $0 \leq j \le n/l$ )の大ブロックは $B[l(j-1)+1, lj ]$ に対応
小ブロック: 長さ $s$ 、 $B[i]$ を含む小ブロックの番号は $y=$ $\lceil \ i/s \rceil$ で、 $B[s(y-1)+1, sy ]$ に対応

ここで具体的な $l, s$ の値はひとまずおいておきます。この $l, s$ の設定が空間計算量に大きな影響を与えますが、説明の都合上具体的な値は最後の方で述べます。文字で見るとぱっと見よくわかりませんので具体例で見てみましょう。

f:id:big_wing_ik:20200729062540p:plain — ビットベクトル分割の例: l = 12, s = 3

上の図はビットベクトルを $l = 12, s =3$ として分割した例になります。まず全体を $l = 12$ の長さで大ブロックに分割し、各大ブロックを $s = 3$ の長さで小ブロックに分割します。

次にrank $_ 1$ $(B,i)$ の値の計算のために、分割した大ブロックと小ブロックに付随した2つの配列 $R _ L$ と $R _ S$ を用意します。

$R _ L[j]$ : 先頭から $j-1$ 番目までの大ブロックに含まれる1の数を保持する
$R _ S[y]$ : $y$ 番目の小ブロックが属する大ブロックにおいて、属する大ブロックの先頭から $y-1$ 番目の小ブロックまでに含まれる1の数を保持する

こちらも具体例を見てみましょう。

f:id:big_wing_ik:20200729062751p:plain — 2つの配列R_LとR_Sの例. l = 12, s= 3

上の図は先程の例において具体的に $R _ L$ と $R _ S$ を求めたものになります。

$R _ L[1]$ は0番目の大ブロックまでに含まれる1の数ですが、0番目のブロックは存在しないので $R _ L[1] = 0$ となります。 $R _ L[2]$ は $2-1 = 1$ 番目の大ブロックまでに含まれる1の数です。1番目の大ブロックの中の1の数を数えると5個なので $R _ L[2] = 5$ となります。

$R _ S$ についても確認してみましょう。 $R _ S[3]$ は1番目の大ブロックに属します。1番目の大ブロックの先頭から $3-1 = 2$ 番目の小ブロックまでに含まれる1の数は3個なので $R _ S[3] = 3$ となります。また同様に $R _ S[7]$ は2番目の大ブロックに属します。2番目の大ブロックの先頭から $7-1 = 6$ 番目の小ブロックまでに含まれる1の数は2個なので $R _ S[7] = 2$ となります。

さてこれら2つの配列 $R _ L$ と $R _ S$ を用いることでrank $_ 1$ $(B,i)$ を定数時間かつ $n + \rm{o}(\it{n} \rm{)}$ ビットの空間領域で求めることができます。計算の方針は

rank $_ 1$ $(B,i)$ = 自身の属する大ブロックまでの累積和 + 大ブロックの先頭から自身の属する直前の小ブロックまでの累積和 + 自身の属する小ブロックの先頭からの残り

です。ここで自身の属する大ブロックまでの累積和が $R _ L$ に、直前の小ブロックまでの累積和が $R _ S$ に対応しています。また自身の属する小ブロックは $y=$ $\lceil \ i/s \rceil$ 、自身の属する大ブロックは $x=$ $\lceil \ y/(l/s) \rceil$ で求めることができ、上の計算式は、

rank $_ 1$ $(B,i) = R _ L [x] + R _ S [y] +$ 自身の属する小ブロックの先頭からの残り

と書くことができます。今、図のビットベクトルにおいてrank $_ 1$ $(B,17)$ を上記の式で求めてみましょう。図において位置17は $y = \lceil \ 17/3 \rceil = 6$ 番目の小ブロック、 $x = \lceil \ 6/(12/3) \rceil = 2$ 番目の大ブロック、6番目の小ブロックの先頭から2ビット目に該当します。まず2番目の大ブロックまでの累積和は $R _ L$ の定義から $R _ L[2] = 5$ です。次に2番目の大ブロックの先頭から直前の $6-1 = 5$ 番目の小ブロックまでの累積和は $R _ S$ の定義から $R _ S[6] = 1$ です。最後に自身の属する6番目の小ブロックの先頭から位置17までの1の数は1個です。以上から、

rank $_ 1$ $(B,17) = 5 + 1 + 1 = 7$

と計算することができます。これでなんとなくrank $_ 1$ $(B,i)$ を定数時間で計算できる気持ちになってもらえたでしょうか？具体的な計算を優先したため、計算式の残りの部分の計算が定数時間で実行できるのか？といったところや、 $R _ L$ と $R _ S$ の空間計算量が $\rm{o}(\it{n} \rm{)}$ ビットなのか？というところはあやふやにしてきました。そこで最後に途中お茶を濁した大ブロックと小ブロックの長さ $l, s$ を具体的に設定することにより、上記の方針でrank $_ 1$ $(B,i)$ を定数時間かつ $n + \rm{o}(\it{n} \rm{)}$ ビットの空間領域で計算できることを示します。

rankの実現: 時間計算量と空間計算量

いきなり天下り的ですが、

$l =$ $(\rm{lg}$ $n )^{2}$
$s = \frac{1}{2}$ $\rm{lg}$ $n$

と設定して解析を行います。

最初に時間計算量です。rank $_ 1$ $(B,i)$ の計算式の自身の属する小ブロックの先頭からの残りの部分の時間計算量ですが、これは定数時間で行うことができます。なぜならば今 $s = \frac{1}{2}$ $\rm{lg}$ $n$ と設定したため、小ブロックの先頭からの残りの長さは高々 $s = \frac{1}{2}$ $\rm{lg}$ $n$ です。これはWord RAMモデルの仮定から定数時間で読み込むことができ、かつビット演算も定数時間で実行でき、POPCOUNTというCPU命令を使うことで高速に定数時間で残りの1の数を計算できます。よって $R _ L、 R _ S$ の加算と合わせてrank $_ 1$ $(B,i)$ は定数時間で計算することができます。

次に空間計算量です。まず $R _ L$ について考えます。今 $0 \leq R_ L \leq n$ であることから、各 $R _ L$ を表現するには $\rm{lg}$ $(n+1)$ ビットが必要となります。また $l =$ $(\rm{lg}$ $n )^{2}$ と設定したことから配列 $R _ L$ の要素数は $\lceil \$ $n/(\rm{lg}$ $n )^{2}$ $\rceil$ となり、 $R _ L$ の空間計算量は $\rm{O}$ $(\rm{lg}$ $(n+1) \times$ $(n/(\rm{lg}$ $n )^{2}) =$ $\rm{O}$ $(n/ \rm{lg}$ $n )$ ビットです。

次に $R _ S$ について考えます。今 $0 \leq R_ S \leq l-s$ であることから、各 $R _ S$ を表現するには $\rm{lg}$ $(l-s+1)$ ビットが必要となります。また配列 $R _ S$ の要素数は $\lceil \ n/s \rceil$ となり、設定した $l$ と $s$ を代入することにより $R _ S$ の空間計算量は $\rm{O}$ $(\rm{lg}$ $(l - s + 1) \times$ $(n/s)) =$ $\rm{O}($ $n$ $\rm{lg}$ $\rm{lg}$ $n/ \rm{lg}$ $n )$ ビットです。

したがって $R _ L$ と $R _ S$ を合わせた空間計算量には $\rm{O}($ $n$ $\rm{lg}$ $\rm{lg}$ $n/ \rm{lg}$ $n ) =$ $\rm{o}(\it{n} \rm{)}$ ビットです。以上から $n + \rm{o}(\it{n} \rm{)}$ ビットの空間領域でrank $_ 1$ 演算を定数時間で実現するデータ構造を実現することができました、お疲れさまでした。

まとめ

簡潔データ構造の紹介の2回目である今回は、ビットベクトルに対する簡潔データ構造について紹介しました。ビットベクトルに対する簡潔データ構造はあらゆる簡潔データ構造の基本となり、とても重要です。今回はrank演算についてのみ紹介しましたが、select演算を実現するためのデータ構造や、あるいはビットベクトルが非常にスパースな場合のより効率的なデータ構造の話など奥深い話はまだまだたくさんあります。また今回は理論的な側面を紹介しましたが実際の実装になると注意すべき点や工夫すべき点が様々あります。実装の一つとして様々な種類の簡潔データ構造が実装されているライブラリを紹介します。興味のある方は最初に紹介した本や、最後に紹介した実装などに触れてみてください！次回はビットベクトルの拡張となる一般の文字列に対する簡潔データ構造について紹介する予定です。

Retrieva TECH BLOG

簡潔データ構造第2回: ビットベクトルに対する簡潔データ構造