n番煎じマンが文法圧縮による完備辞書を写経しました(Python)。

id:echizen_tmさんによる文法圧縮を使った完備辞書(簡潔ビットベクトル)を作ったに感銘を受けたので写経しその理解を試みました。

アルゴリズムは同じくRe-pairでほとんど流れは同じです。Pythonのほうが良いという人は読んでください。

id:echizen_tmさんが書かれているようにpopcountなどのbit演算が不要なところが大きな利点ですが、スクリプト言語以外では非終端記号の表現を工夫する必要があるように思われます。buildの中間データの保管にはダブルバッファ的にメモリを確保するのが素朴な実装かと思いました。

c++で実装するには

　非終端記号をどう表現するか

compressでリストを返すようにすると明らかにメモリを無駄に使っているので節約するようにする。

個人的課題

Re-pair以外の実装

テストドリブンで書く(unittest, doctest)

Reference

文法圧縮を使った完備辞書(簡潔ビットベクトル)を作った

http://research.preferred.jp/2014/03/nlp2014_grammar/

文法圧縮について広範かつ詳細に説明されています。中盤に書かれていますが、文法圧縮はデータ圧縮手法としては既存のLZMAなどの圧縮手法と比べるとそれほど優位ではありません。むしろ劣っているかもしれません(深い構造を持つことのできるXMLの圧縮率が相対的に良くないのは意外です)。しかし完備辞書として実装した場合の全文検索においてはデータサイズの小ささと展開が不要な構造により高い性能を発揮できるそうです。