DEFLATE 是同時使用了 LZ77 算法和哈夫曼編碼（Huffman Coding）的一個無損數據壓縮算法。它最初由 Phil Katz 為其 PKZIP 軟件第二版所定義，後來被 RFC 1951 標準化。DEFLATE 在 zip、gzip 和 png 文件中均有應用。
引言#
DEFLATE 算法由改進的 LZ77 壓縮算法和 Huffman 編碼算法組成。改進的 LZ77 算法和 Huffman 編碼算法保留了原算法的基本原理，提高了 DEFLATE 算法的壓縮速度，增加了算法靈活度，使其具備良好的適應性。
在 DEFLATE 算法中，首先使用改進的 LZ77 算法對原始數據進行壓縮，然後使用改進的 Huffman 編碼對 LZ77 壓縮數據進行二次壓縮，最終壓縮數據為 Huffman 編碼後的 LZ77 壓縮數據。
改進 LZ77#
LZ77 壓縮算法將所有數據都處理成為一個三元組串，每個三元組至少需要 3 個字節表示，如果在動態字典中未找到匹配字符串，會將 1 個字節輸出為 3 個字節，這就導致了字節浪費。因此在 DEFLATE 算法中對其使用的 LZ77 算法進行了以下改進：
- 對匹配字符串長度小於 3 的字符串不壓縮。因為長度小於 3 的字符串，使用三元組表示，對原始數據不能起到壓縮的作用。
- 對字符串的匹配長度進行了限制，範圍為（-128~127），用 8bit 表示，滑動窗口大小為 32KB ，用 15bit 表示，將壓縮數據構造為標識 + 數據的形式，具體如表所示。該存儲方式，降低了壓縮數據的存儲空間。
- 由於只查找匹配長度大於 3 的字符串，為提高算法速度，在查找匹配字符串時，使用了哈希鏈結構搜索算法，其中哈希算法將 3 字節壓縮到 2 字節，雖然哈希鏈結構存在搜索到錯誤結果的可能，但還是大幅提高了搜索速度。
| 原始數據 | 壓縮後數據 | ||
|---|---|---|---|
| 標識(1-bit) | 數據(8-bit) | 偏移(15-bit) | |
| 匹配長度小於3 | 0 | 原始數據 | 無 |
| 匹配長度大於3 | 1 | 匹配長度 | 偏移距離 |
改進 Huffman#
經過 Huffman 編碼壓縮後的壓縮數據由碼表和編碼數據兩部分組成，在 DEFLATE 算法中使用的 Huffman 編碼算法，根據碼表的生成方式不同，分為靜態 Huffman 編碼和動態 Huffman 編碼，其中靜態 Huffman 編碼使用預先定義碼表並始終固定，無需在壓縮數據中存儲，動態 Huffman 編碼需要根據待處理數據情況，生成動態碼表，並在壓縮數據中存儲，DEFLATE 算法中主要對動態 Huffman 編碼算法進行了以下改進：
- 固定 Huffman 碼表生成規則，從 Huffman 編碼的構造可知，同樣的數據由於二叉樹的生成方式或順序不同，可以得到不同的 Huffman 碼表，通過固定二叉樹生成方式及順序，使同樣的數據得到相同的 Huffman 碼表。
- 使用碼長記錄碼表，進一步壓縮碼表佔用的存儲空間，這樣使用 1 字節就可以表示碼長為 1 到 256 的任一碼字。
- 對需要存儲的 Huffman 碼表進行了二次編碼壓縮，在 DEFLATE 算法中最終使用 3 張 Huffman 編碼表，實現了其 Huffman 編碼表的存儲。
改進後的 Huffman 編碼算法，在兼顧運算速度的情況下，有效減少了壓縮數據的存儲空間。
DEFLATE 處理流程#
DEFLATE 將所有待壓縮的數據都看成二進制數據流，最基本的處理元素為字節，其中 Huffman 編碼算法採用動態或靜態編碼由 DEFLATE 算法根據壓縮比進行自動選擇。其中採用動態 Huffman 編碼的 DEFLATE 算法具體處理流程如圖 1 所示。首先將原始數據進行 LZ77 壓縮處理，對應表中的數據構成，得到 “標識 + 數據” 和 “偏移” 兩部分數據；然後使用 Huffman 編碼算法對兩部分數據分別進行壓縮，得到 “碼表 1 ” 和 “碼表 2 ”，以及使用兩張碼表編碼壓縮的 “壓縮數據 1 ” 和 “壓縮數據 2 ”；最後繼續使用 Huffman 編碼對 “碼表 1” 和 “碼表 2 ” 進行壓縮，得到 “碼表 3 ” 和 “壓縮數據 3 ”。
經過上述處理，原始數據經過壓縮後，採用靜態 Huffman 編碼的 DEFLATE 算法需要存儲的數據為 “壓縮數據 1” 和 “壓縮數據 2 ”；採用動態 Huffman 編碼的 DEFLATE 算法需要存儲的數據為 “壓縮數據 1 ”、“壓縮數據 2 ”、“壓縮數據 3 ” 和 “碼表 3 ”，解壓縮為壓縮過程的逆運算。