簡潔データ構造 (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以上の何か。
  例えば、圧縮した生データ＋圧縮したインデックスを保持する構造

要は、Inverted Indexなんかの技法がcompact data strcutureで、その次の世代の技法としてsuccinct data structureが実用化されつつあるという話。

このsuccinct data structureの入力をunstructuredデータとし、データ構造の圧縮を頑張ることによって、必要データ量を、Z+o(Z)から極限までZに近づけて、かつ定数時間で展開できるようにすると、上述の透過的データ圧縮となる。というのは勘違いかな。勘違いかも。勘違いだったよう。

提案されている手法は、LZ78の辞書をsuccient data structureに置き換え、定数時間内で展開する方法を提案するという感じでした。succient data structureだけだと高次圧縮できないから、他の手法と組み合わせたほうがいいか。

補足、上ではo(Z)はZ未満の何かといっているが、o(Z)の定義では任意のkについてkO(Z)以下。なのでZ以下の方が意味的には正しいはず。とはいえ、ニュアンス的に、未満の方が説明しやすかったので、上では未満としている。