疎なbit arrayに対する現実的なRank/Selectデータ構造 - DO++

久しぶりに研究紹介。 最近書いた論文です。 "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つの違ったデータ構造で実現したというものです。 このデータ構

[odz]

あとで(論文を)読む

[k_ryu]

研究材料