資料壓縮/基於語法壓縮
< 資料壓縮
基於語法壓縮在 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