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

文法圧縮(2)

NLP

休みは長かったけど、家の用事も多かったので、あまり論文を読むことができなかった。ただ、以前から少しずつ調査しているRe-Pairに関する論文を1本だけ読んだ。

A fully linear-time approximation algorithm for grammar-based compression
Hiroshi Sakamoto, Journal of Discrete Algorithms, 2005.

http://www.sciencedirect.com/science/article/pii/S1570866704000632

線形時間で、Re-Pair圧縮が可能なアルゴリズムである。Re-Pairの辞書の簡潔データ構造は、Navarro神らのチームが提案してくれていて、DAGベースの簡潔データ構造で実現できる。しかし、構築の方は、論文数もあまりなさそうで、上記の論文の手法が現状のベストプラクティスだと思われる。

Re-Pairの本家の論文よりも読みやすく、疑似コードと例もある。データ構造も本家より良いものが提案されている。

Re-Pairの理解と実装

現状、Re-Pairを勉強するなら、以下の流れが良いと思う。

  1. 「高速文字列解析の世界」を読む。Re-Pairの直接的な記述もあるし、その他の重要な圧縮についても記述してある。LZ77やLZ78やLZ-Endについては読んでおいた方が良い。著者の圧縮に対する愛を感じることができる。
  2. リンク先のスライドでRe-Pairに対するイメージを固めておいた方が良い。5ページ目のスライドがわかりやすい。
  3. Re-Pairに対するイメージができたら、本家の論文をさらっと読む。p.95-101に、Re-Pairの実装に対する記述があります。図もあるので、理解しやすいです。
  4. 本家の論文を読んだ後、今回紹介した坂本先生の論文を読むと良いと思います。利用しているデータ構造も本家と似ているので、理解しやすくなります。

さらに、簡潔ビットベクトルに適用したい場合は、以下の論文を読むと良いです。

Re-Pairの辞書の簡潔データ構造

DAGベースの簡潔データ構造についての提案です。p.6-7に記述があります。

Compressed Text Indexes with Fast Locate
Rodrigo Gonzalez, CPM'07, 2007.

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

Re-Pairを利用した簡潔ビットベクトル

ビットベクトルをRe-Pairで圧縮し、Re-Pairの辞書の簡潔データ構造を利用している。また、rankとselectは、サンプリングしたデータ構造を利用し、圧縮部分を部分的に復元しながら計算する。RRRとかに比べれば低速ですが、同じビットベクトルが繰り返されるような場合に圧縮されやすいようです。

Practical Compressed Document Retrieval, Gonzalo Navarro
SEA'11, 2011.

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

まとめ

アルゴリズムの単純さから想像するほど、実装は自明でなく、難しいので、段階的に理解する方が良いと思います。ただ、私は、文法圧縮の専門家でもアルゴリズムの専門家でもなく、趣味としてやっている程度なので、もっと良いやり方があるかもしれません。そのへんは、ご理解頂きたいと思います。

実際に実装すると、より理解が深まるので、sbvjに実装できるように進めていきます。

広告を非表示にする