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

文法圧縮(3)

NLP

落ち着いて作業できました。

さて、前回、文法圧縮のRe-Pairを効率的に実装するのはなかなか難解だと書いたが、非常にシンプルに線形時間で実装できる論文を発見した。

An Online Algorithm for Lightweight Grammar-Based Compression.
Shirou Maruyama, Algorithms 2012, 2012.

http://www.mdpi.com/1999-4893/5/2/214

このアルゴリズムを利用すると、LZ圧縮のように入力文字列を前から参照しながら、オンラインでRe-Pair圧縮を実現することができる。しかも、入力文字列の5文字だけを見るだけというシンプルさで。かなり、感動した。こんなシンプルにできるんですね。ただ、LCAを定数時間で求める方法が勉強不足でわかっていない。調査する。

また、著者が作成したプログラムが以下にあるので、簡単に試したい場合は使ってみるのが良いと思います。

https://code.google.com/p/lcacomp/

あと、最近、Re-Pairの簡潔ビットベクトルについて、よくまとまった論文が出てたので、紹介しておく。

General Document Retrieval in Compact Space.
Gonzalo Navarro, ACM Journal of Experimental Algorihtmics, 2013.

http://www.dcc.uchile.cl/~gnavarro/ps/jea13.pdf

p.17の4章に説明と図があります。

広告を非表示にする