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

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

Java

今回も引き続きselectの実装を進めていきます。

前回までで、8bitのselectの値を高速に取得できる表を作成しました。

今回は、高速なselect操作(2分探索版)を実現できるメソッドを作ってみます。

まず、BitVectorクラスに以下のメソッドを定義します。

public long getSelectUsingBinarySearch( final long pCount, final int pBit ) {
...
}

このメソッドは2分探索でselect操作を実現するメソッドです。

さて、実装は、前回の記事までで説明した通りですが、ざっくりまとめると以下のような流れとなります。

  1. LB内を2分探索して、求めるselect値が含まれるLBを特定する。
  2. 特定したLB内のSB内を線形探索して、求めるselect値が含まれるSBを特定する。
  3. 特定したSB内を8bit単位で表引きして、select値を求める。

そんなに難しくないですよね。
手順としては簡単です。
私は以下のように実装しました。

public long getSelectUsingBinarySearch( final long pCount, final int pBit ) {
	
	// selectの値
	long select = 0;
	long targetCount = pCount + 1;
	
	// 引数チェックを行う。
	checkArgsBit(pBit);
	checkArgsCountAndBit(targetCount, pBit);
	
	// LB配列を2分探索する。
	int min = 0;
	int max = this.mLBArray.length - 1;
	int lbIndex = 0;
	long value = 0;
	if ( 0 != max ) {
		while ( min < max ) {
			int mid = (min + max) / 2;
			if ( 1 == pBit ) {
				// 1のrank値を求める場合は、1のrank値を取り出す。
				value = this.mLBArray[ mid ];
			} else {
				// 0のrank値を求める場合は、0のrank値を取り出す。
				value = ((long) mid * LB_BIT_SIZE) - this.mLBArray[mid];
			}
			if ( value >= targetCount ) {
				max = mid;
			} else {
				min = mid + 1;
			}
		}
		lbIndex = min - 1;
	}
	
	// SB配列を線形探索する。
	// 探索開始位置を取得する。
	int sbIndexStart = (lbIndex * (int) LB_BIT_SIZE) / (int) SB_BIT_SIZE;
	// 探索終了位置を取得する。
	int sbIndexEnd = sbIndexStart + (int) (LB_BIT_SIZE / SB_BIT_SIZE);
	if ( this.mSBArray.length <= sbIndexEnd ) {
		sbIndexEnd = this.mSBArray.length - 1;
	}
	
	// 特定したLB内のselectの値を計算する。
	int restTargetCount = 0;
	if ( 1 == pBit ) {
		// 1の数の残りを取り出す。
		restTargetCount = (int) (targetCount - this.mLBArray[lbIndex]);
	} else {
		// 0の数の残りを取り出す。
		restTargetCount = (int) (targetCount - ( ( lbIndex * LB_BIT_SIZE ) - this.mLBArray[lbIndex] ));
	}
	
	// SB配列の線形探索を開始する。
	int sbIndex = sbIndexStart;
	while ( sbIndex < sbIndexEnd - 1 ) {
		int sbValue = 0;
		int sbValueNext = 0;
		if ( 1 == pBit ) {
			sbValue = getUnsignedByteValue(this.mSBArray[sbIndex]);
			sbValueNext = getUnsignedByteValue(this.mSBArray[sbIndex + 1]);
		} else {
			int sbTotal = (sbIndex - sbIndexStart) * (int) SB_BIT_SIZE;
			int sbTotalNext = ((sbIndex - sbIndexStart) + 1) * (int) SB_BIT_SIZE;
			sbValue = sbTotal - getUnsignedByteValue(this.mSBArray[sbIndex]);
			sbValueNext = sbTotalNext - getUnsignedByteValue(this.mSBArray[sbIndex + 1]);
		}
		if ( restTargetCount > sbValue && restTargetCount <= sbValueNext ) {
			// 該当のselect値が存在するブロックを発見した。
			break;
		}
		sbIndex++;
	}
	
	// 特定したSB内のselectの値を計算する。
	int wordRestTargetCount = 0;
	if ( 1 == pBit ) {
		wordRestTargetCount = restTargetCount - this.mSBArray[sbIndex];
	} else {
		wordRestTargetCount = restTargetCount - ((sbIndex * (int) SB_BIT_SIZE) - this.mSBArray[sbIndex]);
	}
	
	// ここまでの位置を合計する。
	select += lbIndex * (int) LB_BIT_SIZE;
	select += (sbIndex - sbIndexStart) * SB_BIT_SIZE;
	
	// SB内のselectの値は表引きで求める。
	if ( 1 == pBit ) {
		select += getWordSelect(this.mBitVector[sbIndex], wordRestTargetCount);
	} else {
		select += getWordSelect(~(this.mBitVector[sbIndex]), wordRestTargetCount);
	}
	
	return select;
		
}

ここで重要なのは、1のrank値を保持した表しかないということです。
直接的には、0のrank値を知ることはできないですが、1と0の2bitしかないので、1のrank値がわかれば0のrank値は簡単に計算できます。
これは、rankを実装した時にも同じように実現したので、問題ないと思います。
selectの表引きも1のselect値を求める表しかないですが、ビットを反転すれば、0のselect値を求める表になります。
どういうことかを詳しく説明します。
まず、最後の表引きの処理が該当するのは、メソッドの以下の部分です。

// SB内のselectの値は表引きで求める。
if ( 1 == pBit ) {
	select += getWordSelect(this.mBitVector[sbIndex], wordRestTargetCount);
} else {
	select += getWordSelect(~(this.mBitVector[sbIndex]), wordRestTargetCount);
}

ビットが1の場合と0の場合に分けているのは、ビットを反転させて求めるためです。
ビットを反転させる理由は、1のselect値を求める表を0のselect値を求める時にも使うためです。
例えば、「161=10100001」というビットベクトルBに対して、select(B, 1, 0)を表引きで求めたいとします。
161の1のselect値の表を以下に示します。

SELECT_TABLE[161][0] = 1
SELECT_TABLE[161][1] = 6
SELECT_TABLE[161][2] = 8
SELECT_TABLE[161][3] = 0
SELECT_TABLE[161][4] = 0
SELECT_TABLE[161][5] = 0
SELECT_TABLE[161][6] = 0
SELECT_TABLE[161][7] = 0

このとき、1のselect値であれば、この表を使うことで、select(B, 1, 1) = 6と簡単に求めることができます。
これに対して、select(B, 1, 0) = 3は、この表から求めることができません。
0を1と解釈できれば、1のselect値を使って、0のselect値を求めることができそうです。
つまり、「161=10100001」のビットを反転させて「94=01011110」とすれば、「161=10100001」の時に0だった部分が1に変更されています。
この新しいビットベクトルである「94=01011110」をB'とすると、1のselect値の表を使って、select(B', 1, 1) = 3と簡単に求めることができます。

さて、最後にgetWordSelectメソッドについて説明しようと思いましたが、疲れたので次回にしようと思います。
次回は、getWordSelectを実装して、2分探索でselectを実現するgetSelectUsingBinarySearchメソッドを完成させようと思います。