簡潔データ構造(Succinct Data Structure)で最初に読むと良さそうな論文
最近、簡潔データ構造(Succinct Data Structure)まわりの論文を色々読んでいる。その中で良さそうなものをいくつかピックアップしてみた。まだ調査中なので他に良いものがあったら教えてもらえると嬉しいです。
(1) Space-efficient Static Trees and Graphs(link)
G. Jacobson; IEEE1989
まずはLOUDS論文。簡潔データ構造の元祖なので最初に読むと良さげ。
(2) Succinct Indexable Dictionaries with Applications to Encoding k-ary Trees and Multisets(link)
R. Raman, V. Raman, and S. S. Rao; SODA2002
簡潔ビットベクトルは通常n+o(n)なんだけど、これをnH0+o(n)にしたよ、という話。H0は0次エントロピーという量で値が2値(0/1)のときは1以下になることが保証されている。
(3) High-Order Entropy-Compressed Text Indexes(link)
R. Grossi, A. Gupta, and J. S. Vitter; SODA2003
ウェーブレット木の論文。ウェーブレット木はテキストに対する簡潔構造。
(4) Practical Entropy-Compressed Rank/Select Dictionary(link)
D. Okanohara, and K. Sadakane; ALENEX2007
Vertical Codeを含め4つの簡潔データ構造を提案。比較的読みやすい論文。最初に読んでもいいかも。
(5) Practical Rank/Select Queries over Arbitrary Sequences(link)
F. Claude and G. Navarro; SPIRE2008
(2)のRamanらの手法や、(3)のウェーブレット木を効率的に実装したよ、という論文。
ライブラリ
実際にコードを見るのが勉強になったりするので以下のライブラリのコードを見るといいかも。
