SPIRE2012の効率的な文法圧縮のための可変長コードに関する論文とオンライン文法圧縮のソフトウェアー (olca++)を公開しました。

SPIRE2012で発表したメモリー効率の良い文法圧縮のための可変長コードに関する論文を公開しました。
Y.Takabatake, Y.Tabei, H.Sakamoto: Variable-Length Codes for Space-Efficient Grammar-Based Compression, Symposium on String Processing and Information Retrieval (SPIRE), Cartagena, Colombia, 2012. Link to the PDF

上記の論文に基づくオンライ文法圧縮(online LCA)のC++による実装(olca++)を公開しました。
下のサイトからダウンロードできます。

https://code.google.com/p/olca-plus-plus/

文法圧縮のアルゴリズムは@marugorithmさんが開発したonline LCA[1]に基づいています。online LCAは、入力文字列からそれを一意に復元可能な文脈自由文法の生成規則を作成することで文字列を圧縮します。online LCAは名前から想像できる通り、入力文字列を一文字づつ読みつつ生成規則を作成するので入力文字列自体をメモリーに保つ必要はありません。
文法圧縮アルゴリズムを実装する上でメモリーは、(1)入力文字列、(2)文法の生成規則を格納する辞書と呼ばれる配列、(2)ハッシュテーブルで消費されますが、online LCAでは(2)辞書と(3)ハッシュテーブルでほとんどのメモリーが消費されます。一般的にハッシュテーブルは生成規則を逆引きするために使用され、衝突を解消するためにキーと値の両方を保持する必要があります。 文法圧縮の場合、衝突が起こった場合でも辞書を参照すれば衝突を解消することができるのでキーをメモリーに保持する必要はありません。そのため、文法圧縮では(2)辞書によりほとんどのメモリーが消費されることになります。
そこで、今年のSPIREでメモリー効率良く文法圧縮を実装するために可変長コードから辞書を提案しました。関連研究として、ガンマ符号に基づく可変長コードからなる配列[2]と、[2][4]に基づく@hillbigさんによるライブラリーdag_vector[3]があります。しかし、ガンマ符号は小さい値を表現するには有効ですが、大きい値を表現した場合その値は固定長ビットを超えることがあります。例えば、65536(=2^16)以上の値をガンマ符号で表現すると32ビットを超えます。そのため、これらの配列は文法圧縮での応用には有効な手法ではありませんでした。提案手法はこの点を克服しています。online LCAと組み合わせることにより、従来のarrayや[2]の配列を使った実装よりもおおよそ1/3のメモリーで文法を構築することができます。

[1] S. Maruyama, H. Sakamoto, M. Takeda, An Online Algorithm for Lightweight Grammar-Based Compression, Algorithms 5(2):214-235, 2012.
[2] N.R.Brisaboa, S.Ladra, and G.Navarro, Directly addressable variable-length codes in SPIRE, pages122-130, 2009.
[3] https://github.com/pfi/dag_vector
[4] http://lbd.udc.es/research/DACS/

下はコロンビアの写真