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

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

Java

簡潔ビットベクトルとは、最近よく使われるようになってきたデータ構造です。

ここまで紹介してきたビットベクトルに付加的な情報を付与して、rank操作とselect操作という操作をサポートしたデータ構造です。
ここでは、以下の書籍の情報を基本にして、簡潔ビットベクトルをJavaで実装してみようと思います。

日本語入力を支える技術 ?変わり続けるコンピュータと言葉の世界 (WEB+DB PRESS plus)

日本語入力を支える技術 ?変わり続けるコンピュータと言葉の世界 (WEB+DB PRESS plus)

まず、簡潔ビットベクトルとは、以下の2つの操作を行うことができるビットベクトルのことです。

  • rank操作
  • select操作

操作自体は、本やブログなどで説明されているので、あまり説明しませんが、実装に必要なので、簡単にまとめておきます。

まず、rank操作を以下のように定義します。

rank(B, pos, b)

rank操作とは、ビットベクトルBとして、b=(0 or 1)がposまでに出現する数を求める操作です。

例えば、要素が10個のビットベクトルに対して、rank操作を適用した場合のイメージを示します。

f:id:ryokkie:20120218141712p:plain

次に、select操作を以下のように定義します。

select(B, count, b)

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

例えば、要素が10個のビットベクトルに対して、select操作を適用した場合のイメージを示します。

f:id:ryokkie:20120218143651p:plain

上記のようなrank操作とselect操作を可能とするビットベクトルが簡潔ビットベクトルです。

次回は、前回までに作成したビットベクトルに対して、rank操作とselect操作を実装して簡潔ビットベクトルを作成してみます。