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

文法圧縮(1)

NLP

ビットベクトルの完備辞書のさらなる圧縮のために、文法圧縮について調べている。かなり奥が深いようだ。自分のメモとして、調査したことをしばらく書いていく。

Re-Pair(is the recursive replacements of all pairs)を応用した完備辞書を実装しようと思った関係上、Re-Pairについて調べている。Re-Pairの概要はとても簡単で、誰でも理解できる。テキスト上に最頻出するバイグラム(2文字)をテキスト中に出現しない文字で置き換えるということを繰り返し、その変換ルールと変換した文字列を保存することで圧縮するアルゴリズムである。

以下に例を示す。

Text:
aaabacaaabccaaab

1. 「D -> aa」というルールを適用する。

Text:
DabacDabccDab

2. 「E -> Da」というルールを適用する。

Text:
EbacEbccEb

3. 「F -> Eb」というルールを適用する。

Text:
FacFccF

4. 「G -> cF」というルールを適用する。

Text:
FaGcG

最終的に、Re-Pairは、以下のようなデータを保存する。

Text:
FaGcG

Dictionary:
D -> aa
E -> Da
F -> Eb
G -> cF

このように、Re-Pair自体はとても理解しやすいが、うまい実装というのはそれなりにやっかいである。

まず、以下の論文を読んでみたが、例がないので、Implementationの部分がなかなかイメージできなかった。

http://www.larsson.dogma.net/dcc99.pdf

ただ、著者の博士論文の方には、図があり、理解しやすい。

http://www.larsson.dogma.net/thesis.pdf

p.95-100ぐらいに説明があります。

実装しようとしているが、要領が悪く、まだできていない。

ちなみに、Re-Pairは、構築時にはそれなりにメモリが必要なことが知られている。ただし、構築後の辞書部分は、簡潔に表現することができるようだ。

http://www.dcc.uchile.cl/~gnavarro/workshop07/gnavarro.pdf

う~ん、奥が深い。

広告を非表示にする