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

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

Java

さて、今回は、selectの表引きについて、検討します。

まず、rankの表引きについて復習します。
rankの表引きは、以下のような1の数を取り出すためのテーブルを用意するのでした。

RANK_TABLE[ 0 ] = 00000000 = 0
RANK_TABLE[ 1 ] = 00000001 = 1
RANK_TABLE[ 2 ] = 00000010 = 1
RANK_TABLE[ 3 ] = 00000011 = 2
...
RANK_TABLE[ 255 ] = 11111111 = 8

このようにRANK_TABLEは、添え字に対応する値を2進数で表現した時の1の数を保持するテーブルです。
もちろん、32bitの値をすべて覚えるテーブルを作ることもできますが、容量が大きくなってしまう(2^32個の要素が必要)ので、8bitで表現できる数値のみを扱います。
8bitで表現できる数値が0-255なので、RANK_TABLEのサイズは、256個となります。

さて、selectの場合は、1の数ではなく、1の位置を返す必要があります。
例えば、ビットベクトルに対して、rank操作用のブロックを2分探索して、ブロックを特定し、8bitの領域まで絞り込んだとして、この8bitの領域から求める1の位置が欲しいとします。

ここで、対象とする8bitは、以下のような8bitとします。
(右から0bit目が始まるとしています。)

添え字: 7 6 5 4 3 2 1 0
値:     1 0 1 0 0 0 0 1

これの1の位置を求めるテーブルは、以下のような2次元配列を使えば求めることができます。
10100001は、161なので、161の添え字の要素に、1番目の1の位置、2番目の1の位置、...、8番目の1の位置を持つ配列を持たせます。
具体的には、以下のような2次元配列です。

f:id:ryokkie:20120311144524p:plain

これを使えば、例えば、10100001の1番目の1の位置は、

SELECT_TABLE[161=10100001][1] = 0

として、求めることができます。

また、2番目と3番目も同様に、以下のようにして求めることができます。

SELECT_TABLE[161=10100001][2] = 5
SELECT_TABLE[161=10100001][3] = 7

つまり、256個の値すべてに8種類の1の位置が対応するので、256×8の2次元配列があれば良いということになります。

さて、次回は、このselect操作用のテーブルを使って、実際に表引きによって、1の位置を求めます。