tb_yasuの日記

文法圧縮されたテキスト上でのrank/select/accessに関する論文を公開しました。

04:09 |

文法圧縮されたテキスト上でのrank/select/accessに関する論文を公開しました。ヘルシンキ大のDjamal BelazzouguiさんとSimon Puglisiさんとの共著論文です。arXivからダウンロードできます。

Djamal Belazzougui, Simon J. Puglisi, Yasuo Tabei: Rank, select and access in grammar-compressed strings .論文へのリンク(arXiv)

内容はタイトルが示す通り文法圧縮されたテキスト上のrank/select/accessに関するものです。一般の文字列上のrank/select/access操作はFM-indexを代表とするさまざまなデータ構造を実装する際の重要なデータ構造であることは良く知られています。ご存知かもしれませんが、これらの操作を実現する代表的なデータ構造にWavele木があります。

一方、文法圧縮は反復テキストという同じ部分列を多く含むテキストのクラスに対して高い圧縮率を達成するという良い性質があり、文法圧縮されたテキスト上での効率的なrank/select/accessに関する研究は既存のデータ構造を反復テキストに対してより効率的に処理できるように改良する可能性を秘めています。これまでの研究は構文木がバランスされている場合を仮定したアルゴリズムしか提案されていませんでした。今年のSPIREに[1]があります。実用的にはこれで良いのかもしれませんが、今回はより一般的な場合である構文木がアンバランスな場合を仮定して議論を進めています。論文中では、一般的な構文木上でのrank/select/access操作の困難性を提示した後、これらに対するアルゴリズムを提案しています。

[1] Gonzalo Navarro and Alberto Ordonez: Grammar Compressed Sequences with Rank/Select Support. To appear in Proc. SPIRE'14.

ツイートする