読者です 読者をやめる 読者になる 読者になる

Javaで簡潔ビットベクトル(26)

Java

さて、sbvjで実装している定数時間のselect操作について説明してみたいと思います。

まず、rank操作とselect操作の定義を示します。
rank操作とは、ビットベクトルBとして、b=(0 or 1)がiまでに出現する数を求める操作です。
また、b=1の場合のrank操作をrank1(i)と記述します。
select操作とは、ビットベクトルBとして、b=(0 or 1)がj+1回出てくる位置の中で最小の数値を返す操作です。
今回は、b=1の場合のselect操作しか説明しないので、select1(j)と記述します。
このあたりのことは、以下の解説を参照してください。

Javaで簡潔ビットベクトル(まとめ)

さて、今までは、select操作を2分探索で求めていたため、ビットベクトルのサイズをNとすると、O(log(N))の時間がかかってしまっていました。
select操作で2分探索が必要なのは、求めたいselect値が存在するブロックを特定する部分です。
つまり、求めたいselect値が存在するブロックをO(1)で特定できれば、O(1)でselect操作が実行できることがわかります。

解説のために、以下のような8bitでブロック化したビットベクトル(B)を考えます。

+---+------0-7th------+-----8-15th------+-----16-23th-----+-----24-31th-----+
| B | 0 0 1 1 0 1 0 0 | 0 0 0 0 0 0 0 0 | 1 0 0 0 0 1 0 0 | 0 0 0 0 1 1 1 1 |
+---+-----------------+-----------------+-----------------+-----------------+

補助領域なしで、直接的にselectが求められたら最高だと思うけど、今のところ知らないので、O(1)のselectのために補助領域を作成します。

まず、ビットベクトル(B)の1のビットに対して、delimiter bit vectorというビットベクトル(D)を作成します。
ビットベクトル(D)のサイズは、ビットベクトル(B)の1のビットの数と同じになります。
ビットベクトル(B)の1の数は、9個なので、ビットベクトル(D)のサイズは、9ですね。
以下のようなイメージですね。
ちなみに、ビットベクトル(D)の添え字は、0からとします。

+---+------0-7th------+-----8-15th------+-----16-23th-----+-----24-31th-----+
| B | 0 0 1 1 0 1 0 0 | 0 0 0 0 0 0 0 0 | 1 0 0 0 0 1 0 0 | 0 0 0 0 1 1 1 1 |
+---+-----------------+-----------------+-----------------+-----------------+
| D |     0 0   0     |                 | 0         0     |         0 0 0 0 |
+---+-----------------+-----------------+-----------------+-----------------+

さて、

D(0) = 1

と定義します。
こうすると以下のようになります。

+---+------0-7th------+-----8-15th------+-----16-23th-----+-----24-31th-----+
| B | 0 0 1 1 0 1 0 0 | 0 0 0 0 0 0 0 0 | 1 0 0 0 0 1 0 0 | 0 0 0 0 1 1 1 1 |
+---+-----------------+-----------------+-----------------+-----------------+
| D |     1 0   0     |                 | 0         0     |         0 0 0 0 |
+---+-----------------+-----------------+-----------------+-----------------+

次に、ビットベクトル(B)で1である部分に注目します。
このとき、ビットベクトル(B)において、同一ブロック内にi-1番目の1とi番目の1がある場合、D(i-1)=0と定義します。
ただし、i=2以上とします。
例えば、i=2とした場合、i-1番目の1は、1番目の1なので、1番目のブロックにあります。
また、i番目の1は、2番目の1なので、1番目のブロックにあります。
このため、D(i-1)=D(1)=0となります。
ただし、同一ブロックに存在しない場合は、D(i-1)=1と定義します。
例えば、i=4とした場合、i-1番目の1は、3番目の1なので、1番目のブロックにあります。
また、i番目の1は、4番目の1なので、3番目のブロックにあります。
ブロックが異なる場合は、D(i-1)=D(3)=1となります。
このようにビットベクトル(D)を定義した場合は、以下のようになります。

+---+------0-7th------+-----8-15th------+-----16-23th-----+-----24-31th-----+
| B | 0 0 1 1 0 1 0 0 | 0 0 0 0 0 0 0 0 | 1 0 0 0 0 1 0 0 | 0 0 0 0 1 1 1 1 |
+---+-----------------+-----------------+-----------------+-----------------+
| D |     1 0   0     |                 | 1         0     |         1 0 0 0 |
+---+-----------------+-----------------+-----------------+-----------------+

さて、ここで、ビットベクトル(D)に対して、O(1)で実行できるrank操作のための補助領域を作成して、定数時間でrank操作が実行できるようにしておきます。
このビットベクトル(D)の目的は、O(1)でselectの値が含まれる目的のブロックを特定するためにあります。
2分探索版のselectの欠点は、この目的のブロックを特定する部分が2分探索であるために、O(1)にならないことです。
なので、O(1)でselect操作を実行するためには、目的のブロックをO(1)で特定できる必要があります。
ただし、ビットベクトル(D)だけでは、目的のブロックを完全に特定することができません。
例えば、ビットベクトル(B)に対して、4番目の位置を求めるselect1_B(3)を実行したとします。
ビットベクトル(D)のrank1の操作を使って、rank1(4)を実行して、目的の2ブロック目にあることがわかります。
ただし、この2ブロック目というのは、ブロック内に1つでも1が現れているブロックの中で2ブロック目というだけです。
ビットベクトル(B)のように、2ブロック目に1が一つも現れていないブロックが存在すると、ビットベクトル(D)のrank1の操作だけでは、目的のブロックを特定することができません。

このような理由から、もう一つcontracted bit vectorというビットベクトル(C)を考えます。
このビットベクトルを利用して、ブロック内に1が一つも現れていないブロックの数を管理します。
ビットベクトル(C)は、以下のような感じです。

+---+-----------------+-----------------+-----------------+-----------------+
| C |       1         |       0         |        1        |        1        |
+---+------0-7th------+-----8-15th------+-----16-23th-----+-----24-31th-----+
| B | 0 0 1 1 0 1 0 0 | 0 0 0 0 0 0 0 0 | 1 0 0 0 0 1 0 0 | 0 0 0 0 1 1 1 1 |
+---+-----------------+-----------------+-----------------+-----------------+
| D |     1 0   0     |                 | 1         0     |         1 0 0 0 |
+---+-----------------+-----------------+-----------------+-----------------+

ビットベクトル(C)は、ビットベクトル(B)に対して、ブロック内に1が一つでも現れていれば1とし、そうでなければ0としたビットベクトルです。
さて、このビットベクトル(C)とビットベクトル(D)を使えば、ビットベクトル(B)に対するselect1の操作において、目的のブロックを特定することは簡単にできます。
例えば、さきほどと同じように、ビットベクトル(B)に対して、4番目の位置を求めるselectを実行したとします。
その場合は、以下のようにすることで、目的のブロックを特定することができます。

select1_C( rank1_D(4) - 1 ) = select1_C( 1 ) = 2
(ただし、ビットベクトルの添え字は、0から開始しているとする。)

つまり、ビットベクトル(C)に対するselectを使うことで、3番目のブロックが目的のブロックということがわかります。
このことから、ビットベクトル(C)に対するselect操作が、O(1)で実行できれば、目的のブロックをO(1)で特定することができそうです。
このため、ビットベクトル(C)の1のビットに対して、clump delimiter bit vectorというビットベクトル(R)を定義します。
ビットベクトル(R)のサイズは、ビットベクトル(C)の1のビットの数と同じなので、この場合は、3となります。
ビットベクトル(R)は、C(0)=1の場合は、R(0)=0とします。
また、ビットベクトル(C)のi-1番目の1とi番目の1が隣接していれば、R(i-1)=0とし、そうでなければ、R(i-1)=1とします。
このことから、ビットベクトル(R)は、以下のようになります。

+---+-----------------+-----------------+-----------------+-----------------+
| R |       0         |                 |        1        |        0        |
+---+-----------------+-----------------+-----------------+-----------------+
| C |       1         |       0         |        1        |        1        |
+---+------0-7th------+-----8-15th------+-----16-23th-----+-----24-31th-----+
| B | 0 0 1 1 0 1 0 0 | 0 0 0 0 0 0 0 0 | 1 0 0 0 0 1 0 0 | 0 0 0 0 1 1 1 1 |
+---+-----------------+-----------------+-----------------+-----------------+
| D |     1 0   0     |                 | 1         0     |         1 0 0 0 |
+---+-----------------+-----------------+-----------------+-----------------+

また、ビットベクトル(R)もO(1)で、rank操作が実行できるようにしておきます。

さらに、clump arrayという配列(S)を定義します。
この配列は、ビットベクトル(C)の0の累積値を保持する配列です。
まず、ビットベクトル(C)は、1番目の1が出現するまでに0は出現していないので、配列(S)は以下のようになります。

+---------------+---+
| 添え字        | 0 |
+---------------+---+
| 0の数の累積値 | 0 |
+---------------+---+

次に、2番目の1が出現するまでに0は、1つ出現しているので、配列(S)は以下のようになります。

+---------------+---+---+
| 添え字        | 0 | 1 |
+---------------+---+---+
| 0の数の累積値 | 0 | 1 |
+---------------+---+---+

さて、これで、ビットベクトル(C)に対して、以下のようにすることで、O(1)で、select1の操作が実行できます。

select1_C( i ) = (i + 1) + S[ rank( i + 1 ) ]

例えば、ビットベクトル(C)に対するselect1_C( 1 )は、ビットベクトル(R)に対して、rank1_R( 2 )を実行することで、配列(S)の添え字を特定することができます。
これにより、S[1]=1を得ることができます。
つまり、select1_C( 1 ) = 2 + 1 = 3となります。
簡単ですね。

さて、気づいている人は気づいていると思いますが、select1_C( i )を求めるのに、ビットベクトル(C)を全く使っていないので、ビットベクトル(C)を保持する必要はないです。
このことから、保持すべき情報は、以下のビットベクトルと配列Sということがわかります。

+---+-----------------+-----------------+-----------------+-----------------+
| R |       0         |                 |        1        |        0        |
+---+------0-7th------+-----8-15th------+-----16-23th-----+-----24-31th-----+
| B | 0 0 1 1 0 1 0 0 | 0 0 0 0 0 0 0 0 | 1 0 0 0 0 1 0 0 | 0 0 0 0 1 1 1 1 |
+---+-----------------+-----------------+-----------------+-----------------+
| D |     1 0   0     |                 | 1         0     |         1 0 0 0 |
+---+-----------------+-----------------+-----------------+-----------------+

では、任意のiに対して、select1_B( i )を実行してみましょう。
まず、求めたいiが含まれているブロックを特定します。

u = select1_C( rank1_D(i + 1) - 1 )

とすることで特定できます。
例えば、i=5とした場合は、u=4となり、4番目のブロックが目的のブロックということがわかります。
そして、このuの値を利用して、目的のブロックまでに出現した1の数を特定し、目的のブロックに対して1の数を表引きします。
表引きは、2分探索版のselectで使っているものと同じやり方を利用することとします。
さて、目的のブロックまでに出現した1の数は、以下のようにして求めることができます。

r = rank1_B( (u - 1) × 8 ) )

つまり、i=5で、u=4の場合は、r=5となります。
このことから、目的のブロック内から位置を特定したい1の数は、

s = i + 1 - r

であるため、s=1となります。
結局、select1_B( i )は、

select1_B( i ) = (u - 1) × 8 + SELECT_TABLE[u - 1][s]

となります。
i=5の場合は、

select1_B( 5 ) = 3 × 8 + SELECT_TABLE[3][1] = 24 + 4 = 28

となります。

さて、これで、O(1)のselect1の操作の解説を終わります。
O(1)のselect0の操作は、同様の構造を逆にして作れば可能です。