透過的データ圧縮

可逆データ圧縮分野で、現在研究が盛んな分野の一つが、データを圧縮した状態のまま定数時間でランダムアクセスをサポートするデータ圧縮方式です（word RAMモデルでO(log n)サイズの復元が定数時間)。

これは、データをあたかも圧縮していないかのように扱えるため、透過的データ圧縮/構造と呼ばれています（英語だとまだ決まってない？)。

例えば1GBのデータを圧縮した状態で、途中300MB目から4Byteだけ復元しようというのが定数時間で実現できるわけです。これは理論的にもかなり強いことをいっていて，例えば今あるデータ構造やアルゴリズムが、O(T)時間である問題を解けるというのがあったら、それを全く同じO(T)時間のままデータ構造を圧縮し作業領域量を減らすことができます
(一応データ構造に対し読み込み操作しか無い場合。書き込みもある場合はまたちょっと面倒になる）

このデータを圧縮したまま扱う手法は古くからいろいろ試されています。一番簡単には、データを小さなブロック（例えば16KBとか)に分け，それぞれを独立に圧縮し、復元する時は関連するブロックだけ復元するという方法です。しかしこのような方法だとブロックサイズが小さくなるにつれ圧縮率は劇的に低下し、ブロック全体を復元するのもやはり大きなオーバーヘッドです。

私自身もずっと前にこの問題に取り組んだことがありました。
（2003年の未踏ユースあたりの発想でやったのがそれで、成果の一部は論文など発表しました, DCC 2005 [pdf]）
これは、データ全体から予測接頭辞木を構築し、それを利用し次の文字を予測し圧縮するものです。通常のPPM(Partially Pattern Matching)が動的に予測接頭辞木を構築するのに対し、私の方法はデータ全体を見てから構築し、予測接頭辞木は別に保存します。木を静的に持っておくのでStatic Huffman法に対応して、Static PPM法と名づけました。
同じ予測モデルをどの位置でも使えるので、ブロックサイズをかなり小さくしても圧縮率は低下しません。実際ブロックサイズが256byte程度でbzip2と同じぐらいのデータ圧縮率でした。しかしこの手法は復元時に予測接頭辞木を保持しなければならない他（データ全体の数分の一のサイズだが）、復元も実用的には速いですが定数時間は保障されてません。

また、bzip2で使われているBurrows Whleer's変換(BWT)を利用したデータ圧縮でも、ちょっと工夫することで圧縮したまま一部分を復元することが可能ですが、同様に定数時間を実現するのは難しい状態でした。BWTの場合入力時連続していた文字列が変換後はいろいろな場所に散乱してしまうので復元時に定数箇所へのアクセスで復元することが難しかったためです。

このように、圧縮率を限界まで達成して（任意のkに対しk次経験エントロピーに漸近）、定数時間でアクセス可能なデータ圧縮は達成できるのか分からない状態がずっと続いてました。

そうした中、2000年以降、圧縮索引に牽引される形で簡潔データ構造の研究が進み，それらの成果を使って透過的データ圧縮は実現できるというのが分かりました（この仕事と圧縮全文索引で定兼先生はIBM科学賞を受賞されてます）。
K. Sadakane and R. Grossi, "Squeezing Succinct Data Structures into Entropy Bounds", SODA 2006 [pdf]
これは、（すごく間単に言えば）LZ78法をベースにしており、LZ78法で抽出されたフレーズ辞書からなるTrieをを簡潔データ構造で保存し、これを長いフレーズと短いフレーズに場合分けして、参照することで定数時間アクセスでの復元を実現しています。

できるというのがわかって以降、違う手法でも透過的データ圧縮が実現できることがわかってきました（不思議なもので、できると分かったら続々と出てくる）。
Rodrigo Gonzalez and Gonzalo Navarro, "Statistical Encoding of Succinct Data Structures", CPM 2006, [ps.gz]
P. Ferragina, R. Venturini. "A simple storage scheme for strings achieving entropy bounds", SODA 2007, [ pdf]

これらは、基本的にはデータを小ブロックに分け、それらを全体の統計量を用いて圧縮し、各ブロックには簡潔データ構造などで索引をつけておくことで、定数時間でアクセスできるようにするものです。

圧縮率については入力T[1...n]のk次経験エントロピー（k-1文字前までを使って次の文字を予測した時のエントロピー）をH_kとした時、nH_k + O(n / logn) bit　ぐらいで保存できます。この第2項が実は結構厄介で、（nH_kに対し結構でかかったりします。

一般にブロックサイズがBの時にO(n/B)のオーバーヘッドでO(B)時間というトレードオフが限界だと思われていたのですが、つい最近出た、次の論文ではこの限界は破れるということが示されています。
Mihai Patrascu, "Succinter", FOCS, 2008 [pdf]
面白いことにブロック中の要素へのランダムアクセスは、ブロック毎に1bitのオーバーヘッドでは、ブロック全体を復元しないと実現できないが、2bitのオーバーヘッドならば、O(logB)時間でランダムアクセスができることが示されてます。

#（先程までの透過的データ圧縮も、一番小さいブロックサイズがO(log n)で、O(n/logn) bits作業領域量のオーバーヘッドという関係。ブロックサイズがεlogn bitだと、表引きできるので、一応定数時間）

---
次はこれらをどのように実用的なものにしていくかが面白そうです（私もやってます）。
興味がある方は是非いい実装方法を考えてみてください。