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

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

Java

さて、今回からselectの実装に取り組んでいきます。

selectの実装はrankに比べると多少厄介です。
ただし、rankの時と基本方針は同じです。
ナイーブに実装すると性能が悪くて使いものになりません。
なので、rankと同じように補助的なデータ構造を利用することとします。

まず、select操作の定義を行います。
select操作とは、以下のような操作です。

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

今回、改めて、select操作の定義を見返していて、重大なことに気づきました・・・。
間違ってますやん。*1

いや、正確には間違っていないとも言えるんですが。

Jacobson(ロシア人?)さんのrank操作とselect操作の論文を読みました。
ほんとは博士論文を読みたかったけど、どうがんばっても見つけることができなかったので以下の論文にしました。

Space-efficient Static Trees and Graphs
Guy Jacobson, SFCS '89 Proceedings of the 30th Annual Symposium on Foundations of Computer Science, 1989.

1989年とは古いですねぇ〜。

この論文の2章の部分にrank操作とselect操作の定義があります。
rank操作で紹介したtwo-levelブロック(LBとSB)を使った方法もこの人が考えていたとかいなかったとか。
(博士論文を読んでいないので詳しいところはわからないです。)

さて、何が間違っていたかというと、rank操作とselect操作は、逆関数の関係にあるということを知りませんでした。
最近知りました。はい。

逆関数ってあれですよね。以下みたいなやつですよね。

y = f(x)
x = f'(y)

出力yに対してただ一つの入力xが存在する時に、その逆を求めることができる関数ですよね。
なので、y=x^2とかは、x >= 0としないと逆関数を定義できない。
x = 2 or -2でもy=4だしね。

このことを考えると、rank操作とselect操作は、rank(B, select(B, 3, 1), 1) = 3とか、select(B, rank(B, 3, 1), 1) = 3という関係になるわけですよ。

つまり、この時に書いた定義は、逆関数にならないわけですよ。

今まで、rank操作を以下のように定義したので、

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

select操作は、以下のように定義しないといけないわけです。

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

count + 1回がポイントですね。
こうするとちゃんと逆関数になります。

例えば、以下のようなビットベクトルを考えます。

0 1 0 0 0 0 1 1 0 0 1

論文での定義では、ビットベクトルの添え字は、添え字1から始まっていますが、実装を考慮して0から始めます。
rankの定義で、posを含まないようにしているのは、添え字を0から始めているからです。

まず、以下のようなselectを考えます。

select(B, 2, 1) = 7

このとき、

select(B, rank(B, 7, 1), 1) = 7

となります。

また、

rank(B, select(B, 2, 1), 1) = 2

となります。

きちんと逆関数の関係になっています。

ただし、普通のビットベクトルは、正確には、逆関数の関係を満たしていないです。

例えば、先ほどの例の場合だと、

select(B, rank(B, 9, 1), 1) = 10

とかになります。

これは、rank操作が複数の入力に対して同じ値を出力するためです。
y=x^2の場合と同じですね。
なので、いつでも逆関数の関係を成り立たせようと思ったら、ビットベクトルの要素がすべて1かすべて0の場合を考えないといけないはずです。

では、次回は、select操作を実装するための戦略を説明しようと思います。

*1:もうめんどいんで気が向かない限り前の記事は直さないです。