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

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

Java

さて、selectを実装する戦略を考えます。

まずは、復習としてselectの定義から始めます。
selectの定義は以下でした。

select(B, count, b)

また、select操作とは、以下のような内容でした。

ビットベクトルBとして、b=(0 or 1)がcount + 1回出てくる位置の中で最小の数値を返す操作

selectをナイーブに実装した場合、先頭から順にビットをチェックして実装するのが普通だと思うのですが、これだとrankと同様にまったく性能的に持たないです。
なので、selectの高速な実装もrankの高速な実装と同じで、何らかの補助データを使って高速化を考えます。

まず、以下のようなビットベクトルBが存在する場合を考えます。

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

分かりやすいように8bit単位でブロックを作りました。
また、ビットベクトルの添え字は、0から始まるとしました。

このとき、以下のselect操作は、

select(B, 8, 1) = 31

となりますが、ナイーブな実装の場合は、先頭から順にビットをチェックして、32回目のアクセスで、結果を返すことできます。

このとき、0-23までの3つアクセスは完全に無駄です。
なぜなら、1の数は6個しかないため、8+1=9番目の1は、これら3つのブロックに絶対に存在しないからです。
なので、このビットベクトルにrankの時に使った1の数の累積値を保持する補助データであるブロック配列(BLOCK)を付与してみます。

+-------0th-------+-------1th-------+-------2th-------+-------3th-------+
|        0        |        2        |        6        |        6        |
+------0-7th------+-----8-15th------+-----16-23th-----+-----24-31th-----+
| 0 0 1 0 0 0 0 1 | 0 0 0 0 1 1 1 1 | 0 0 0 0 0 0 0 0 | 1 0 1 0 0 0 0 1 |
+-----------------+-----------------+-----------------+-----------------+

このブロックを使えば、ナイーブな実装よりも高速にselectの値を求めることができます。
まずは、求めたいcount+1の値がどのブロックに属しているかを求めます。
これは、rankの時のようにダイレクトに求めることができないので、ブロックの値を2分探索して特定します。*1
2分探索を行ってブロックを特定するため、探索性能は、O(log(ブロック数))となります。
ただし、rank用の領域を利用しているので、補助データ構造は、rankのためのものだけで済みます。
つまり、select用に特別なデータ構造は必要ないです。

では、試しに2分探索を行ってみましょう。

要求されているselect操作は、

select(B, 3, 1) = 13

なので、3 + 1の4が含まれている領域を特定する必要があります。
ブロック配列の最小の添え字が0なので、min=0とし、最大の添え字が3なので、+1して、max=4とします。

mid = (min + max) / 2

とし、mid = 2を求めます。
BLOCK[mid] = 6であるため、BLOCK[mid] > 4となります。
このため、max = mid = 2とし、再度同様の操作を行います。

mid = (min + max) / 2

とし、mid = 1を求めます。小数点は切り捨てます。
BLOCK[mid] = 2であるため、BLOCK[mid] < 4となります。
このため、min = mid + 1 = 2なので、min < maxを満たさないため、index = min - 1 = 1を見つけ、探索を終了します。
このような操作により最終的に、対象とするブロックであるBLOCK[index] = BLOCK[1]を発見することができます。
最後は、BLOCK[1]内をナイーブに探索して、select操作の結果を求めます。

ただ、ブロック内をナイーブに探索する部分をrankと同様に表引きすることでより高速にできそうです。

次回は、select操作の表引きについて検討したいと思います。

*1:ダイレクトに求めることができない理由は、ビットベクトルの1の配分がどうなっているかがこのブロックの値にアクセスするまでわからないためです。つまり、ブロックの値を使って、高速にブロックを絞り込む必要があるため、2分探索を行います。逆に、ダイレクトに1の配分がわかれば、select操作をより高速に実行することができます。