文法圧縮 (Edit Sensitive Parsing (ESP))を実装してみた
ALSIPの時に聴いて気になっていた文法圧縮法Edit Sensitive Parsing (ESP)を実装しました。
文法圧縮とは、与えられた文章から曖昧でない文脈自由文法*1をもとめることにより圧縮する手法です。文脈自由文法のサイズは、導出規則の右辺の終端記号と非終端記号の個数の総和として求められますが、サイズ最小の文脈自由文法を求める問題はNP-Hardとして知られています。これまで近似解を求める手法が提案されてきましたが、文書長 n に線形なメモリが必要で実用的ではありませんでした。例えば、有名な文法圧縮法の一つであるRePairはおおよそ5nのメモリが必要です[1]。2002年にCormodeら[2]が、文書長に依存しないメモリーで文脈自由文法を求める手法(Edit Sensitive Parsing (ESP))を提案しました。必要なメモリーは、文脈自由文法のサイズをgとしたときO(g log g)です。最近、ESPは主に九工大のグループにより圧縮文書検索や頻出部分文字列マイニングに拡張されています[3][4]。
※ 2012/2/5 追記 T.Kuboyama先生からコメントをコメントをいただきました。Cormodeらが文法圧縮法を提案したと書いてしまいましたが、彼らが提案したのは文字列ブロック分割法して文字列移動つき編集距離を効率的に計算する手法で、ブロック分割法を文法圧縮に応用したのは九工大の坂本先生でした。T.Kuboyama先生、ご指摘ありがとうございました。ESPは深い歴史があるようですので、詳しくはT.Kuboyama先生のコメントをご参照ください。
http://d.hatena.ne.jp/tb_yasu/comment?date=20120204§ion=1328357959#c
とても有望そうということで、今回は、ESPをC++で実装し圧縮率や時間を調べて見ました。使用したデータは、pizza & chili corpusのdnaとexglishテキストです。下の２つのテーブルは圧縮した際のサイズと実行時間です。サイズは、データ表現に依存しないように、入力の文字数と文法サイズを掲載しています。
| original (#characters) | ESP (size) | ratio | ||
| DNA | 209714087 | 54547245 | 0.26 | |
| English | 205627755 | 60021662 | 0.29 |
| time (sec) | ||
| DNA | 67 | |
| English | 85 |
文字種類数の少ないDNAの方が文法サイズは小さくなるようです (予想はついていましたが)。
[1] N.J. Larsson and J. A. Moffat. Offline Dictionary-Based Compression. Proc. of the IEEE, 88:1722–1732, 2000.
[2] G.Cormode and S.Muthukrishnan, The String Edit Distance Matching Problem with Moves, Proc of SODA, 2002.
[3] S.Maruyama, M.Nakahara, N.Kishiue, H.Sakamoto, ESP-Index: A Compressed Index Based on Edit-Sensitive Parsing, 18th International Symposium on String Processing and Information Retrieval (SPIRE2011), 398-409.
[4] M.Nakahara, S.Maruyama, T.Kuboyama, H.Sakamoto, Scalable Detection of Frequent Substrings by Grammar-Based Compression, Proceedings of the 14th international conference on Discovery science, 2011
*1:文脈自由文法の解説は以下の本がおすすめ。学部生のとき、ボロボロになるまで何回も読んだ思い入れのある本。
