簡潔データ構造 (succinct data structure) 修正版

先日書いた簡潔データ構造の説明に色々勘違いが混ざってたので修正版

最近、簡潔データ構造が気になってる。

きっかけは、2年位前の国立情報学研究所(NII)のオープンハウスに行って、定兼さんの透過的データ圧縮の話を聞いてからだ。すぐにでもOSSとしてライブラリをリリースするという話だったが、2年経っても公開されていない。

なので、ぼちぼちと自分で調べたことや理解したことなどメモしていってみようと思う。


まず、透過的データ圧縮で使う簡潔データ構造とは何か？
G. Jacobson, "Space-efficient Static Trees and Graphs", IEEE 1989が元ネタ。
簡単に言うと、新しいデータ構造。

データ構造には大きく分けて以下の3つがある。
簡潔データ構造 on Wiki

データTがあり、それを表現するのに必要なビット数をZとおく。

• Z+O(1)を必要とするデータ構造をimplicit data structureと呼ぶ
  データそのものに対し、追加でO(1)～O(lg Z)のデータを必要とするデータ構造
  例えばHeapがこの一種。具体的には、以下の図の通り
• Z+o(Z)を必要とするデータ構造をsuccinct data strcuture (簡潔データ構造)と呼ぶ
  データそのものに対し、追加でO(lg Z)～O(Z)のデータを必要とするデータ構造
  例えば、上記論文(Jacob, 1989)に出てくるlevel-ordered bitmapがこの一種
• O(Z)を必要とするデータ構造をcompact data structure (コンパクトデータ構造)と呼ぶ
  これが何を指しているかが、wikiでは明確でない
  例えば、suffix arrayがこの一種 (と理解している。suffix arrayは、理論的にはO(Z)だが実際はO(Z lg Z)ビット必要)