共有辞書を用いた効率の良い圧縮アルゴリズム

概要

論文の詳細を見る
1999 年に Larsson と Moffat らによって提案された Re-Pair アルゴリズムは,単純なヒューリスティックに基づいた,非常に高い圧縮率を達成する文法圧縮の一つである.しかしながら, Re-Pair アルゴリズムはオフラインのアルゴリズムであり,また,線形サイズではあるものの多くのメモリを使用する.したがって,巨大なテキスト上でアルゴリズムを実行するためには,テキスト全体をいくつかのブロックに分割し,ブロック毎に圧縮を行う必要がある.このような状況において,圧縮時に用いる辞書の一部をブロック間で共有することは,圧縮パフォーマンスの向上に有効であると考えられる.本稿では,ブロック毎に Re-Pair アルゴリズムを行い,辞書式圧縮の辞書に相当する生成規則の一部をブロック間で共有する手法について論じる.ここでは,抽出された文法の符号化には固定長の符号化を用いている.圧縮パフォーマンスを決定する 3 つのパラメータ (ブロックサイズ,辞書サイズ,辞書における共有辞書の割合) の変化によって,圧縮時間と圧縮率がどのように変化するのかを実験的に示し,その傾向について議論する.
2012-12-05