文法圧縮

文法圧縮（ぶんぽうあっしゅく、grammar-based codes、grammar compression）とは、入力文字列データから文脈自由文法（context-free grammar、CFG）を構築する圧縮法の総称である。可逆圧縮。

概要[編集]

文法圧縮の枠組みはJ. C. KiefferとE. -H. Yang^[1]によって示された。その基本的な考え方は、データ中に頻出する共通部分を一つの生成規則として集約することによってデータの縮小化を狙うことである。これまでに多種多様な文法変換アルゴリズムが提案されているが、与えられた文字列を導出する最小サイズのCFGを計算する最適化問題はNP困難であることが知られている^[2]。通常、変換された文法データは算術符号などのエントロピー符号を用いて更に圧縮される。

脚注[編集]

^ 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

[1] 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

[2] 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

[1]

[2]

概要[編集]

関連項目[編集]

脚注[編集]