为何gzip无法识别两段相同的2^23字节数据？压缩异常咨询

先看你的代码和输出结果：

#include "zlib.h" 
unsigned char dst[1<<26]; 
unsigned char src[1<<24]; 
int main() { 
    unsigned long dstlen = 1<<26; 
    srand (12345); 
    for (int i=0; i<1<<23; i++) 
        src[i] = src[i | 1<<23] = rand(); 
    compress(dst,&dstlen,src,1<<24); 
    printf ("%d/%d = %f\n", dstlen, 1<<24, dstlen / double(1<<24)); 
}

输出：

16782342/16777216 = 1.000306

这种看似高度重复的数据没被有效压缩，核心原因在于zlib默认使用的DEFLATE压缩算法的滑动窗口大小限制，具体拆解如下：

• **DEFLATE的滑动窗口只有32KB（2^{15字节）**：DEFLATE压缩的核心逻辑是靠滑动窗口记录最近处理过的数据，当遇到重复字节块时，用「距离+长度」的引用替代原始数据来节省空间。但这个窗口的默认最大尺寸只有32768字节，而你的重复块是2}23字节（8MB），远大于窗口大小。当压缩到后8MB的内容时，前8MB的数据早已经滑出了滑动窗口，算法根本看不到前面还有一段完全相同的数据，自然没法用重复引用的方式压缩。

• 伪随机数据的局部无重复性：你用rand()生成的是伪随机字节，虽然前后两块整体完全相同，但每一段32KB以内的数据几乎没有重复（伪随机的特性）。处理前8MB时，算法找不到足够的重复块来压缩，只能以接近原始的方式存储；处理后8MB时，窗口里只保留了前8MB的最后32KB，和后8MB的开头内容不重复，同样只能原始存储。再加上zlib的压缩头部和少量元数据，最终压缩后的大小甚至比原数据略大一点。

如果想验证这个结论，你可以把重复块的大小改成32KB以内（比如把循环条件改成i<1<<14），再运行代码，就能看到明显的压缩率下降——因为此时重复块在滑动窗口的覆盖范围内，算法能识别到重复并进行有效压缩。

内容的提问来源于stack exchange，提问作者l4m2