簡潔データ構造 (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)ビット必要)

一言でいうと、これまでのデータ構造はビット数まで考えると、サイズがO(n lg n)、計算量がO(lg n)だった。それに対し、サイズをO(n)に抑え、計算量もO(lg n)を保ったデータ構造を考えたという話。次の世代のデータ構造として、非常に有効だと思うので勉強していきたい。

また、透過的データ圧縮では、LZ78の辞書をsuccient data structureに置き換え、かつrank/select用のテーブルに相当するデータを用意することで、圧縮データのどこからでも定数時間内で展開する方法を提案するという感じ。詳細は、まだ勉強中。