久しぶりに研究紹介。 最近書いた論文です。 "Practical Entropy-Compressed Rank/Select Dictionary.", Daisuke Okanohara and Kunihiko Sadakane. In the Proc. of ALENEX 2007, to appear[paper] この論文では、疎なbit array B[0...n-1]に対するrank/select操作を高速に実現するデータ構造を4つ提案しています。 rank(x)はB[0...x]中にある1の数を返し、select(x)はx番目の1の位置を返す関数です。 古典的な問題ですが、これを最小(entropyに近い限界)かつ高速(定数時間、もしくはそれに近い時間)で実現する現実的なデータ構造は存在しませんでした。これを4つの違ったデータ構造で実現したというものです。 このデータ構
![疎なbit arrayに対する現実的なRank/Selectデータ構造 - DO++](https://cdn-ak-scissors.b.st-hatena.com/image/square/a0aa051048cb3afda5716214159b2dba29aaa425/height=288;version=1;width=512/http%3A%2F%2Fhillbig.cocolog-nifty.com%2F.shared-cocolog%2Fnifty_managed%2Fimages%2Fweb%2Fogp%2Fdefault.png)