読者です 読者をやめる 読者になる 読者になる

xiangze's sparse blog

機械学習、ベイズ統計、コンピュータビジョンと関連する数学について

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圧縮率が相対的に良くないのは意外です)。しかし完備辞書として実装した場合の全文検索においてはデータサイズの小ささと展開が不要な構造により高い性能を発揮できるそうです。

 

 

高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学)

高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学)

 

 内容自体が圧縮されていますが、データ圧縮、完備辞書について解説されています。