文法圧縮
文法圧縮（ぶんぽうあっしゅく、grammar-based codes、grammar compression）とは、入力文字列データから文脈自由文法（context-free grammar、CFG）を構築する圧縮法の総称である。可逆圧縮。
概要
文法圧縮の枠組みはJ. C. KiefferとE. -H. Yang[1]によって示された。 その基本的な考え方は、データ中に頻出する共通部分を一つの生成規則として集約することによってデータの縮小化を狙うことである。これまでに多種多様な文法変換アルゴリズムが提案されているが、与えられた文字列を導出する最小サイズのCFGを計算する最適化問題はNP困難であることが知られている[2]。通常、変換された文法データは算術符号などのエントロピー符号を用いて更に圧縮される。
Highly-repetitive textと呼ばれる冗長性の高いデータ類に対して特に強力な圧縮性能を持っており、近年盛んに研究が進められている圧縮法の一つである。 例えば、個体遺伝子データ集合やバージョン管理レポジトリの履歴データの圧縮に適している。
実用的な文法圧縮
文法圧縮アルゴリズムは理論的な目的で作られたものが多いが、実用的アルゴリズムもいくつか提案されている。圧縮プログラムはアルゴリズムの提案者らによって公開されており、外部リンク先から入手可能である。
- Sequitur[3] 文法圧縮の中でも初期に提案されたアルゴリズム。逐次的に文字列を読み込みながらCFGを構築する。算術符号と組み合わせた実装となっている。
- Re-Pair[4] 頻出する隣接した二文字を再帰的に置き換えるアルゴリズム。高い圧縮性能を持つ反面、高速に動作させるためには多くの主記憶領域を必要とする。
参考文献
- ^ Kieffer, J. C.; Yang, E.-H. (2000), “Grammar-based codes: A new class of universal lossless source codes”, IEEE Trans. Inform. Theory 46 (3): 737–754, doi:10.1109/18.841160
- ^ Charikar, M.; Lehman, E.; Liu, D.; Panigrapy, R.; Prabharakan, M.; Sahai, A.; Shelat, A. (2005), “The Smallest Grammar Problem”, IEEE Trans. Inform. Theory 51 (7): 2554-2576
- ^ Nevill-Manning, C. G.; Witten, I. H. (1997), “Identifying Hierarchical Structure in Sequences: A linear-time algorithm”, Journal of Artificial Intelligence Research 7 (4): 67-82, doi:10.1109/18.850665
- ^ Larsson, N. J.; Moffat, A. (2000), “Offline Dictionary-Based Compression”, IEEE 88 (11): 1722-1732
外部リンク
- repetitiveコーパス highly-repetitive textを集めたコーパス。
- Sequiturのプログラム
- Re-Pairのプログラム オリジナルに近い実装。
- Re-Pairのプログラム Gonzalo Navarro版。文法変換機能のみ。