数据压缩/基于语法压缩
< 数据压缩
基于语法压缩在 2000 年被提出。[1]
几种数据压缩方法可以被视为基于语法压缩
- Sequitur 数据压缩算法使用上下文无关语法来表示字符串，例如数据文件。它速度相对较快（线性时间编码和线性时间解码）。[2]
- 最长匹配
- 最常见双字母组
- Sequential 数据压缩算法是 Sequitur 的改进。[3]
- 虽然它早于基于语法压缩，但 LZ78 和 LZW（但不是 LZ77）可以被解释为一种语法。[3]
- 已经证明，“结构化语法”比“不可约语法”提供更好的压缩效果。[4]
当使用零阶熵编码器（如零阶算术编码器）压缩语法转换的输出时，语法压缩优于 Unix Compress 和 Gzip 算法。[1]
Re-Pair 算法是一种基于语法的压缩算法。它的解码器按如下方式工作：[5]
FIXME：补充细节。
- ↑ a b En-hui Yang 和 John C. Kieffer。 "基于贪婪顺序语法转换的有效通用无损数据压缩算法 - 第一部分：无上下文模型". 2000.
- ↑ Richard Ladner。 "Sequitur" p. 56. 2007.
- ↑ a b Eric Lehman 和 Abhi Shelat。 "基于语法的压缩的近似算法". "基于语法的压缩的近似算法". 2002.
- ↑ John Kieffer 和 En-hui Yang。 "用于通用无损数据压缩的结构化语法代码". 2002.
- ↑ Matej Mežik。 "使用上下文无关语法压缩". 2011.
- Re-Store 是一个基于 Re-Pair 压缩算法的短语浏览系统。[1]
- ↑ Wan, R., Re-Store 软件, 存档于 原始位置 2015-07-21