京公网安备11010502063487号压缩比到底能有多高?上限在哪里,什么数据压不动,压缩器离理论极限有多远?这篇用香农熵、条件熵和已知熵的信源把“高压缩比从哪来”的第一层讲清楚:统计上的偏斜和前后文的规律。
内容 0 阶熵 bit/字节 0 阶下限 gzip-9 zstd-3 zstd-19 xz-9 bz2-9 随机字节 8.000 1048553 1048902 1048609 1048609 1048688 1053599 随机小写字母 4.700 616094 666466 624946 625783 636464 626754 词表拼接 4.228 554220 347070 352624 310829 312360 232200 products JSON Lines 5.135 673018 214178 198156 165377 153604 113026 类 HTML 页面 4.852 635962 229223 209800 186466 175892 129572 (0 阶下限 = 熵 × 字节数 / 8。能比它小,是因为压缩器还利用了"前后文"——下一节)
香农熵衡量一个信源每个符号至少需要多少位。随机字节是 8 bit/字节,任何压缩器都压不动(1.00×)。只看字节频率(0 阶)的下限对 products 文本是 673018 字节,但真实的压缩器做到 113026–165377,因为还利用了前后文。
k 1 MiB 样本 bit/字节 对应体积下限 64 KiB 样本 bit/字节 0 5.135 673018 5.124 1 3.034 397667 3.013 2 1.780 233267 1.707 3 1.050 137612 0.915 4 0.734 96149 0.521 对照:zstd-19 实际 165377 字节 = 1.262 bit/字节;xz-9 153604 字节 = 1.172 bit/字节 (阶数越高、样本越小,经验熵越低,但那是"样本太少、每种上下文只见过几次"造成的假象,不是真的可压缩那么多)
已知前 k 个字节时下一个字节的不确定性越来越小:k=0 是 5.135 bit/字节,k=4 是 0.734。压缩器靠“前面出现过什么”预测接下来的内容。小样本上高阶熵会被严重低估(64 KiB 时 k=4 只有 0.521),因为大部分上下文只见过几次。
zlib(gzip 的 deflate) 共 165793 个:变短 0、相等 0、变长 165793;压缩 1 字节 b"a" 得到 9 字节 zstd-3 共 165793 个:变短 0、相等 0、变长 165793;压缩 1 字节 b"a" 得到 10 字节 lz4 frame 共 165793 个:变短 0、相等 0、变长 165793;压缩 1 字节 b"a" 得到 24 字节 lz4 block 共 165793 个:变短 0、相等 0、变长 165793;压缩 1 字节 b"a" 得到 2 字节 计数论证:长度 < n 的字节串共 65793 个(n=3),长度为 3 的有 16777216 个,不可能每一个都映射到一个更短的字节串
长度小于 3 的字节串只有 65793 个,长度为 3 的有 16777216 个,不可能每个都对应到一个更短的串。实验里 165793 个短字节串经 zlib、zstd、lz4 压缩,没有一个变短,全部变长。压缩是在“有规律的数据变短,别的数据变长”之间做交换。
信源 理论熵 bit/符号 理论下限 zstd-19 xz-9 bz2-9 zstd 超出 两个符号 0.5/0.5 1.0000 131072 132495 143428 162415 1.1% 两个符号 0.9/0.1 0.4690 61472 76235 75564 75187 24.0% 两个符号 0.99/0.01 0.0808 10589 17630 21252 11816 66.5% 4 个符号 均匀 2.0000 262144 263493 289524 283801 0.5% 16 个符号 均匀 4.0000 524288 525564 545408 533689 0.2% 8 个符号 0.5,0.25,…(2 的幂) 1.9844 260096 261423 295012 319823 0.5%
符号概率接近均匀时 zstd-19 离理论下限只差 0.2–1.1%;概率很偏时差距变大(0.9/0.1 差 24.0%,0.99/0.01 差 66.5%)。这说明压缩器的熵编码部分(Huffman)在偏斜的分布上浪费很多,第 13 篇讲 FSE/ANS 怎么改进。
伪随机字节(种子 1):gzip-9 1048902、zstd-19 1048609、xz-9 1048688、bz2-9 1053678 字节(原 1048576);而 Python 里生成它只要 "random.Random(1).randbytes(1 << 20)" 这 35 个字符 0,1,2,…255 循环:gzip-9 4396、zstd-19 358;i*i 取低 8 位:gzip-9 3719、zstd-19 218(周期性的规律压缩器能找到)
伪随机数生成器很短(35 个字符),但生成的数据任何通用压缩器都压不动。压缩器能找的只是重复和统计偏斜。
表示 字节 0 阶 bit/字节 2 阶 bit/字节 zstd-19 xz-9 时间戳:十进制文本 549999 3.185 1.835 34403 22556 时间戳:定长 8 字节 400000 3.838 2.300 50937 23016 时间戳:差分 varint 50004 0.819 0.818 6447 6308 价格:十进制文本 118458 3.431 2.590 44968 44320 价格:float64 160000 6.005 2.000 55822 43644 价格:整数分 varint 41136 7.658 1.480 39615 35732
同一批时间戳,差分之后压缩器能压到 6308–6447 字节,直接压十进制文本要 22556–34403。先把数据变得“有规律”再压缩,这是第 4、8 篇里差分、列存做的事。小样本上的高阶熵不能当真下限。