京公网安备11010502063487号“压缩比为什么能那么高”的第二层:LZ77 把重复的内容换成“往回看多远、复制多长”。这篇自己写 LZ77,看匹配有多长、离多远、窗口大小和搜索努力怎么换压缩比,并验证 LZ77 加 Huffman 就是 deflate。
b'abracadabra abracadabra': "a" "b" "r" "a" "c" "a" "d" (7,4) " " (12,11) → 解回原文一致(23 字节 → 8 个字面量 + 2 个匹配)
b'{"id":1,"id":2,"id":3}': "{" """ "i" "d" """ ":" "1" "," (7,5) "2" (7,6) "3" "}" → 解回原文一致(22 字节 → 11 个字面量 + 2 个匹配)
b'aaaaaaaaaa': "a" (1,9) → 解回原文一致(10 字节 → 1 个字面量 + 1 个匹配)
products JSON Lines 的前 300 字节:"{" """ "i" "d" """ ":" "1" "0" (1,5) "," """ "u" "r" "l" """ ":" """ "h" "t" "t" "p" "s" ":" "/" "/" "s" "h" "o" "p" "." "e" "x" "a" "m" "p" "l" "e" "." "c" "o" "m" "/" "i" "t" "e" "m" "/" (45,7) "?" "r" "e" "f" "=" "l" "i" "s" "t" "&" "p" "a" "g" "e" "=" "0" """ "," """ "t" "i" "t" "l" "e" (64,3) "w" "i" "c" "o" " " "b" "i" "w" "a" " " "w" "a" "s" "u" " " …从左到右扫描,每个位置在已经出现过的内容(窗口)里找最长的相同序列:找到就输出(距离,长度),找不到输出字面量。解码只需要按距离往回复制。距离小于长度时就是重叠复制,正好表示“同一个字节重复很多次”。
输入 131072 字节 → 14994 个 token:字面量 5351 个(占输入 4.1%),匹配 9643 个(覆盖输入的 95.9%,平均长度 13.0 字节);用时 0.3 秒;解回原文一致 匹配长度分布:3:1846、4:1548、5–8:1604、9–16:2125、17–32:1785、33–258:735 匹配距离分布:≤16:42、≤256:135、≤4096:3382、≤32768:6084
products 文本里键名、公共前缀、重复的词不断出现:128 KiB 里 95.9% 的字节被匹配覆盖,平均匹配 13.0 字节,而且多数匹配的距离在 4 KiB 以上。高压缩比的来源就是“前面有相同的内容”。
窗口 匹配覆盖输入 字面量个数 匹配个数 估算压缩后字节
256 30.5% 91131 10665 79440
1024 76.8% 30403 10291 40632
4096 89.9% 13210 12719 36355
16384 96.7% 4344 12312 31497
65536 98.3% 2180 11160 28838
131072 98.4% 2099 10816 28042
真实压缩器,pages 数据 4 MiB(每页约 13 KiB,不同页之间有相同的模板):
zlib 级别 6:windowBits 9(窗口 512 B):1271577;windowBits 11(窗口 2 KiB):1221237;windowBits 13(窗口 8 KiB):1125816;windowBits 15(窗口 32 KiB):919863
zstd 级别 3:windowLog 10(1 KiB):1537347;windowLog 12(4 KiB):1315250;windowLog 14(16 KiB):1178377;windowLog 17(128 KiB):932835;windowLog 20(1024 KiB):831923;windowLog 22(4096 KiB):837102往回看得越远,找到的匹配越多、越长。窗口 256 字节时估算 79440 字节,128 KiB 时 28042 字节;真实压缩器 zstd 的窗口从 1 KiB 加到 1 MiB,压缩后从 1537347 字节降到 831923 字节。窗口超过数据里重复出现的间隔后就没有收益了,而窗口越大,压缩和解压要的内存也越大(见第 16 篇)。
chain 懒匹配 匹配覆盖输入 token 数 估算压缩后字节 用时(秒)
1 否 97.8% 18602 36153 0.04
4 否 97.8% 15704 31825 0.05
16 否 97.8% 14495 30021 0.08
64 否 97.8% 14140 29509 0.13
256 否 97.8% 14016 29308 0.17
64 是 95.9% 14994 28234 0.31
256 是 95.9% 14897 28006 0.47
zlib 各级别(raw deflate,同样 128 KiB 输入):级别 1:34051(0.6 ms);级别 3:31358(0.8 ms);级别 6:28441(1.7 ms);级别 9:28019(2.7 ms)每个位置多看几个候选、懒匹配(先看下一个位置有没有更长的),都能找到更好的匹配,代价是时间。zlib 级别 1 到 9 压缩出 34051 到 28019 字节,时间从 0.6 ms 到 2.7 ms。压缩级别本质上就是搜索的努力程度。
输入 zlib-9 压缩比 zstd-3 压缩比 zstd-19 压缩比 lz4 压缩比
1.00KiB 17 60.2× 19 53.9× 18 56.9× 37 27.7×
16.00KiB 39 420.1× 19 862.3× 18 910.2× 98 167.2×
1.00MiB 1039 1009.2× 50 20971.5× 49 21399.5× 4340 241.6×
16.00MiB 16316 1028.3× 531 31595.5× 530 31655.1× 69140 242.7×
64.00MiB 65238 1028.7× 2067 32466.8× 2066 32482.5× 276500 242.7×
deflate 的最大匹配长度是 258 字节,所以压缩比有上限(约 1000×);zstd 的匹配长度没有这个限制deflate 的最大匹配长度是 258 字节,所以哪怕全零数据压缩比也上限约 1000×;zstd 没有这么小的限制,64 MiB 全零能压到 2067 字节(32466.8×)。lz4 的上限更低(约 242×)。
表自检:长度码(3…258)与距离码(1…32768)的范围首尾相接、没有缺口:True 贪心 chain 16:字面量/长度码 67103 位 + 距离码 44287 位 + 额外位 128775 位 = 30021 字节(估算,不含码表);zlib 级别 9 实际 28019 字节;估算是实际的 107% 懒匹配 chain 64:字面量/长度码 78140 位 + 距离码 35704 位 + 额外位 112028 位 = 28234 字节(估算,不含码表);zlib 级别 9 实际 28019 字节;估算是实际的 101%
把 LZ77 的 token 按 deflate 的长度/距离码表分类、再用 Huffman 编码,估算出来 28234 字节,zlib 级别 9 实际 28019 字节,只差 1%。gzip 就是这两步;zstd 把第二步换成了更好的熵编码(第 13 篇)。