簡潔データ構造（succinct data structure）
おっ久しぶりです。最近全然ブログ書いてませんでしたね（汗）。今日は頑張って書いてみましたっ！。
先週のゼミ発表にて先生から「簡潔データ構造についてもっと詳しく説明してくれ」と言われたので、その前哨戦？としてそれに関するエントリを書いてみます。“簡潔データ構造”でググると、主に定兼先生と岡野原さん＠東大によって書かれた（凄い情報密度な）良資料がたくさんヒットします。が、私のように情報理論に詳しくない人だと？？な部分もいくつかありまして、それについて自分なりに考え出したことをツラツラと述べてみます。勘違いなどあると思いますので、コメントで優しく指摘を頂けると嬉しいです。
[2009/12/16 追記]簡潔データ構造の説明があまり正確じゃないので後で記事を書きなおします。
簡潔データ構造（succinct data structure）とは何か？
『簡潔データ構造』というのは「いくつかの操作を定数時間で実行可能な、圧縮されたデータ構造」です。一般に圧縮データに対する操作は、例えば一度全体（or一部分）を解凍する必要があるなど時間がかかるのですが、簡潔データ構造は圧縮データに補助情報を付加することで、いくつかの操作を高速に実行できます。ここでいう“高速”とは定数時間や対数時間を意味します。
簡潔データ構造を使えば、これまで扱うのが難しかった巨大なデータへの高速な部分アクセスが可能になったり、また圧縮によりデータが縮むことでオンメモリで扱うことができたりして処理速度が向上します。
これまでにビット列・文字列・ツリーを対象にした簡潔データ構造が提案されており、おいおい本ブログのエントリとして個別に解説したいと思います。肝心の「いくつかの操作」についてもデータ構造によって異なるので、各エントリで詳細に述べます。
Word RAM モデル
簡潔データ構造では『Word RAM モデル：w[bit]の計算は定数時間で実行可能』というのを仮定します。これは一般的なコンピュータの動作を理論的に定義したものです。もし「四則演算を定数時間で実行可能」とだけ仮定してしまうと、ビット長無限な演算も一度にできてしまい非現実的です。つまり Word RAM モデルはより現実に即したモデル定義というわけです。現在広く普及している32bitコンピュータの場合、32bit長（CPUのワードサイズ）の四則演算を定数時間で行うことができるので、当然ですが w=32 となります。
この w が決まれば、入力データサイズ N[bit] も実は制限を受けます。というのも、wビットコンピュータではポインタサイズが w[bit] ですから、扱えるメモリサイズは 2^w[bit] までとなります*1。すなわち N≦2^w で、最大ケースより w=lgN *2と考えるのが一般的のようです 。
ルックアップテーブル（表引き）
演算を定数時間で実現するために、簡潔データ構造ではルックアップテーブルのテクニックを使うことが多いです。ルックアップテーブルとは、予め全ての演算結果を求めてテーブルの形で保持しておき、このテーブルを参照して演算結果を知る方法です。これはただの配列参照なのでアクセスは定数時間となります。
ここで重要なのがテーブルサイズです。メモリサイズには限界がありますので、テーブルも現実的に妥当なサイズに設定する必要があります。仮に lgN[bit] の値を引数（添字）としてルックアップする場合、テーブルサイズは O(2^lgN) = O(N) となり、これはコンピュータの扱える最大のメモリサイズですので非現実的です。そこで引数を (lgN)/2[bit] の値とします。このときテーブルサイズは O(N^(1/2)) で（ギリギリ？）現実的と言えます。ここでの重要なポイントは、ブロック区切りでルックアップテーブルする場合、許容できるブロックサイズは最大で (lgN)/2[bit] である！という事実ですね。
おわりに
というわけで悪い頭なりに考察してみました。簡潔データ構造はこれまで理論的な研究がメインだったようなのですが、ここ数年間で実用レベルに達した部分もあるようです。今後の発展が楽しみですね。自分も何か貢献したいものです。
次回はビット列の簡潔データ構造について話せたらいいなぁーと思ってます。ではでは。
参考リンク
- 岡野原さんによる2007年研究発表資料(PPT)
- 見つけた資料の中では最新？だと思います。簡潔データ構造についての解説・各種実装性能比較についてです。新しいためか説明が一番洗練されてると感じました。
- 定兼先生による2006年講義資料(PPT)
- 各種簡潔データ構造とその関連分野について一通り要約してある感じです。
- 岡野原さんによる2006年研究発表資料(PPT)
- 各種簡潔データ構造とその関連分野についての要約。
