2013年度の文法圧縮の進展

年が明けて2014年の1月ももう半分まで来てしまいましたが、調度良い時期ですので, 2013年の振り返り記事の代わりに2013年の文法圧縮の進展を振り返ってみたいと思います。

はじめに文法圧縮を簡単におさらいすると, 文法圧縮とは入力となるテキストのみを表現する小さいCFGを構築する圧縮方式です. ゲノム配列, バージョン管理されたテキスト, リポジトリー上でのソースコードなど反復する部分列を多く含むテキストに対して高い圧縮率を達成することができます. これらのテキストは反復テキストと呼ばれ, 次世代シーケンサー技術やバージョン管理ソフトの発展により文法圧縮は今後ますます重要な技術と言えます.

文法圧縮には2つの問題があります。一つ目は入力テキストを表現する小さいCFGをどのように構築するかという問題です。最小化問題はNP-hardとして知られていて, 現在までにさまざまな近似アルゴリズムが提案されてきました. 代表的な手法にRePairというGreedyアルゴリズムがあります。, RePairは入力文字列の各2文字ペアーに着目し, 再頻出ペアーを新しい非終端記号に置き換えるという操作を収束するまで繰り返します。オンラインアルゴリズムにはLCAと呼ばれるアルゴリズムがあります.

2つ目の問題は, 構築したCFGをいかに符号化するかという問題で, CPM2013の論文ではCFGの符号化に関する情報理論的下限を示しました.
論文とスライドを以下に置きます.

Yasuo Tabei, Yoshimasa Takabatake, Hiroshi Sakamoto: A Succinct Grammar Compression, 24th Annual Symposium on Combinatorial Pattern Matching (CPM), 2013. 論文(PDF)

さらにSPIRE2013では, 入力文字列読みつつオンラインでCFGを構築し, 直接簡潔表現にエンコードする完備オンライン文法圧縮法を提案しました. この手法における簡潔表現はCPM2013で提示したCFGの簡潔表現の情報論的下限に漸近的に一致します.

Shirou Maruyama, Yasuo Tabei, Hiroshi Sakamoto, Kunihiko Sadakane: Fully-Online Grammar Compression, 20th String Processing and Information Retrieval Symposium (SPIRE), 2013.

今年のDCC2014では, この完備オンライン文法圧縮を定数領域で動くように改良しました. これにより巨大文字列に対しても, 予め決めたメモリーで文法圧縮することができます.
Shirou Maruyama and Yasuo Tabei: Fully-Online Grammar Compression in Constant Space, Data Compression Conference (DCC), 2014. (論文準備中)

2014/1/22更新
DCC2014論文をarXivにアップしました。
http://arxiv.org/abs/1401.5143