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

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

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

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


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

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

以下は、勘違いが多かったので、修正しました。

データTがあり、その情報理論的限界、例えば“-ΣP・log P”をZとすると、

• Z+O(1)を必要とするデータ構造をimplicit data structure
  例えば、圧縮データをZ、データ長をO(1)だけ保持する構造
• Z+o(Z)を必要とするデータ構造をsuccinct data strcuture (簡潔データ構造)
  o(Z)はO(Z)未満の何か。つまりZ+Z未満、2Z未満のデータ。
  圧縮した生データ＋圧縮したインデックスだと2Zを超える。
  例えば、圧縮したインデックスで元データを展開できるような構造(と理解している)
• O(Z)を必要とするデータ構造をcompact data structure (コンパクトデータ構造)
  Z+o(Z)以上なので、Z+Z以上の何か。
  例えば、圧縮した生データ＋圧縮したインデックスを保持する構造