你手里有一个 10MB 的日志文件想发给同事结果聊天工具直接拒绝上传。你无奈地右键压缩几秒钟后得到一个 300KB 的.zip。整个过程行云流水但如果你停下来问一句那个文件到底是怎么变小的能变多小为什么有的文件压完几乎没变化——大部分人就开始支支吾吾了。这篇“压缩原理笔记”就是奔着这些追问来的。我会从信息论最底层的冗余概念讲起拆开 Huffman、LZ、BWT 这些你在 gzip、bzip2、zstd 里反复见到却又说不出所以然的名字再聊到 JPEG、MP3 这类有损压缩的感知模型最后落到工程选型上。适合后端开发、存储运维、嵌入式工程师以及所有想搞明白“文件体积这回事”的人。不追求数学上的严谨但保证每个结论都能对应到实际效果。1. 文件变小之前先搞清楚它凭什么能变小1.1 冗余才是压缩的原材料压缩不是魔法它解决的问题只有一个数据里有太多“不该有的部分”。这里说的“不该有”专业一点叫冗余通俗一点叫重复和规律。任何一个真实文件无论是日志、代码还是图片充斥着的都是排列有序、概率不均、前后相关的信息而压缩要做的事情就是把这些规律榨出来换一种密度更高的表达方式。我先用一个最简单的例子说明。假设你有一段字符串AAAAAABBBBBBAAAAAABBBBBB如果原样存下来这是 24 个字符。但你稍微观察一下它无非是“6个A6个B”重复了两遍。你完全可以把它记成2×(6A6B)这就是压缩最原始的形态——提取重复结构。当然真实文件里的规律要隐蔽得多但逻辑是一样的压缩器本质上是在寻找一种更短的描述使得给定这个描述你能精确还原出原始数据。这引出压缩领域的第一个重要分类无损压缩与有损压缩。日志、代码、数据库文件一个 bit 都不能丢必须用无损方案图片、音乐、视频人眼人耳察觉不到的细节是可以扔掉的于是有了有损方案。两者的分界线不是技术壁垒而是“人类感知的容忍度”。1.2 香农熵一切压缩器的理论天花板既然压缩是在找更短的描述那自然会有一个问题一个文件最短能短到什么程度有没有一个绝对下限有。这个下限由克劳德·香农在 1948 年奠定他提出了“信息熵”的概念。熵的定义是H(X) -Σ p(x) × log2 p(x)其中 p(x) 是符号 x 在文件中出现的概率单位是比特。熵的含义是表示这个数据源的每个符号平均至少需要多少个二进制位。任何无损压缩算法不管设计得多精巧都不可能低于这个下限更严格的说法是接近下限但不可能在有限长度下稳定突破。我用一个具体场景算一遍。假如一个数据源只产生 A、B、C、D 四个符号概率分别占 1/2、1/4、1/8、1/8那么这个数据源的熵就是H -0.5×log2(0.5) - 0.25×log2(0.25) - 0.125×log2(0.125) - 0.125×log2(0.125) 0.5 0.5 0.375 0.375 1.75 比特意思是这个源产生的每个符号理论上平均至少需要 1.75 个 bit 来表示。如果你不管三七二十一用固定的 2 个 bit 存 A/B/C/D00、01、10、11那每个符号花了 2 bit压缩空间就是 2 减 1.75约 12.5% 的冗余率。看起来不多但在大数据量下很可观。熵这个概念最重要的价值不是算出某个文件的理论极限而是改变你看待压缩的眼光压缩率不是由文件大小决定而是由数据源的内在概率分布决定。一个全英文的技术文档字符分布高度不均匀e 出现极多z 极少它的熵比一个完全随机的二进制流要低得多于是前者能压得很狠后者几乎压不动。这也是我在笔记里最先写下的结论你永远压不动真正的随机数据。如果你在压缩一个文件之后发现体积几乎没变不用怀疑算法有问题应该怀疑这份数据本身是不是已经接近均匀分布了。2. 熵编码三兄弟Huffman、算术编码与 ANS2.1 Huffman 编码用最短的码喂给最常出现的符号知道了理论下限接下来一个重要问题就是怎么用一套具体规则去逼近这个下限。最广为人知的答案就是 Huffman 编码。它的出发点很朴素符号出现的概率越高就给越短的码字概率越低给越长的码字。问题在于怎么构造这样一套前缀不冲突的变长码。Huffman 的构造过程可以理解成一个自底向上的合并过程。以 A(0.5)、B(0.25)、C(0.125)、D(0.125) 这四个符号为例把每个符号看作一个叶子节点权重就是它的概率。每次取出概率最小的两个节点合并成一个新节点新节点的概率是两者之和。重复直到所有节点合并成一颗树。从根节点往下左边标 0右边标 1每个叶子收到的路径就是该符号的编码。按这个流程走一遍你会得到类似这样的码表A0B10C110D111。平均码长是0.5×1 0.25×2 0.125×3 0.125×3 1.75 bit恰好等于熵。当然这是因为这四个符号的概率是 2 的负整数次幂刚好适配 Huffman 那种“整数比特分配”的策略。真实文件里符号概率大多是 0.3、0.17 这种尴尬值Huffman 的结果通常会离熵有 5%~10% 的差距。这个差距的来源很本质Huffman 给每个符号分配的码长必须是整数个 bit。C 理论上应该用 2.6 个 bit现实里你只能给它 2 个或 3 个这中间的 0.4 bit 就是浪费。2.2 算术编码把整个文件映射成一个小数为了弥补整数比特的浪费算术编码出现了。它的核心思想很反直觉不再给每个符号单独编码而是把整个待压缩的数据看成一个 0 到 1 之间的小数每次读入一个符号就把当前区间按符号概率比例缩小最后输出这个区间内任意一个最短的二进制小数。我写一个直观的例子。三个符号 A、B、C概率分别为 0.5、0.3、0.2初始区间是 [0, 1)。读入 A区间变成 [0, 0.5)再读入 C在 [0, 0.5) 内按概率切分C 是第三个符号对应区间是 [0.4, 0.5)继续读入 B区间变成 [0.4, 0.43)。最终只要输出这个区间里的一个二进制小数比如 0.1001二进制就能完整还原整个符号序列。你注意看整个过程里没有“每个符号对应一个码”的概念而是把概率切分的精度一路累加。这意味着符号多到一定程度输出的长度可以无限逼近熵的下限不再受整数比特的约束。算术编码的问题在于它是个串行的过程而且每一轮都要做高精度的小数运算硬件实现上很麻烦历史上算得也慢。所以很长一段时间里它只在各种学术项目和少数压缩器如早期的 LZMA里有存在感直到 ANS非对称数字系统出现。2.3 ANS让现代压缩器跑得更快更狠的隐藏功臣ANS 是 Jarek Duda 在 2009 年前后提出的编码方案它结合了 Huffman 的速度和算术编码的压缩率核心思路是不用区间而是用一张状态表来完成符号到状态值的映射。理解 ANS 最好的方式是和 Huffman 做对比。Huffman 的码长是整数ANS 则允许一个符号映射到多个状态值状态值一多就意味着描述同一个符号的平均 bit 数可以是分数。但 ANS 不需要像算术编码那样维护一个高精度小数它只需要维护一个整数状态并且通过查表完成状态转移和符号解码。这个特性让 ANS 非常适应现代 CPU 的并行化设计存储和缓存也友好。Facebook 开源的Zstandardzstd能同时做到高压缩率和极快速度底层用的就是有限状态熵FSE也就是 ANS 的一种优化实现。在我实测的压缩对比里相同压缩级别下 zstd 的压缩率能逼近甚至略超 xz但压缩速度能快出好几倍。这背后很大一部分功劳要记在 ANS 头上。3. 字典压缩与滑动窗口gzip、LZ4 的看家本领3.1 LZ77与其重复编码不如直接说“指回去”熵编码解决的是符号概率不均的问题但它没有利用数据里的另一种冗余前后重复。日志里反复出现的”ERROR: connection timeout“、代码里一模一样的字段声明、数据库导出里不断重复的列名——这种重复不是你改一下概率分布就能解决的它天然需要一种跨位置的引用机制。1977 年两位以色列研究者 Jacob Ziv 和 Abraham Lempel 提出了 LZ77 算法。它的核心操作可以概括为压缩器维护一个滑动窗口窗口里存着最近看过的一段数据当遇到一段和窗口里已有内容匹配的字符串时不重复输出这段字符串而是输出一个三元组(距离, 长度, 下一个字符)意思是“你往回找多少字节拷贝多长然后跟上下一个字符”。我用一段实际数据来说明。假设原始数据是abcabcabcxyz压缩器滑过前 6 个字符abcabc时看到第 7~9 个字符abc已经在窗口里出现过就可以输出(6, 3, x)表示“距离当前 6 个字节的位置有一串 abc拷贝 3 个字节然后再接一个 x”。如果每个字符原本占 1 字节这个三元组可能只占 1~2 字节省下来的空间就是收益。LZ77 的思路看起来简单但它有一个关键的工程难点怎么快速找到最长的匹配。朴素做法是挨个试慢得让人崩溃。现代实现——比如 gzip 和 zlib——普遍使用哈希表先把窗口里每 3 字节不同实现选 K 不同算出一个哈希值存进哈希表然后查哈希表寻找候选匹配位置。zstd 更进一步引入了哈希链和多种匹配策略在小窗口内能极快地找到足够长的重复片段。3.2 DEFLATEgzip 和 PNG 都在用的标准组合拳如果你看过 gzip 的源码或者相关 RFC会注意到 gzip 用的算法叫 DEFLATE它是 LZ77 加上 Huffman 编码的组合先用 LZ77 把重复内容替换成匹配引用再用 Huffman 对输出结果包括字面量、距离、长度做一次熵编码。这个组合的逻辑非常清晰LZ77 负责消除长距离重复Huffman 负责消除符号概率不均。两者各管一段配合起来效果远超单打独斗。这也是为什么 gzip 出来快 30 年了今天还在各种 HTTP 传输、日志存储、容器镜像场景里端着稳稳的位置——不是它有多先进而是它在压缩率、内存和速度三者的平衡上做到了足够好。DEFLATE 的实现细节里有个值得注意的参数叫“窗口大小”gzip 里默认是 32KB。这不是拍脑袋定的而是 LZ77 匹配距离的编码上限。窗口越大能找到的重复就越远压缩率理论上越高但哈希表的内存占用和搜索耗时也会显著上升。所以你看到gzip -9比gzip -1压得更狠原因不只是算法迭代更久还有窗口大小的差异。3.3 LZ4把“快”当成第一优先级如果说 gzip 是在压缩率和速度之间找平衡那 LZ4 就是旗帜鲜明地把速度放在第一优先级。它同样脱胎于 LZ77但做了几件简化不做熵编码只保留 LZ 替换匹配搜索的阈值设得很高只找足够长的匹配输出格式也设计得很聪明——直接用(token, 长度, 距离)的结构让解码器只需要一次内存拷贝就能完成还原。这种设计思路的后果非常明显LZ4 的压缩速度能以 GB/s 计解压速度甚至能到 5~10GB/s但压缩率只有 gzip 的几分之一。那它有什么用用到你正在读取这些文字的电脑上——Linux 内核的 zram 页交换、很多日志采集器的实时压缩、还有 Redis 在磁盘持久化时的 RDB 压缩用的都是 LZ4 或者它的近亲。这些场景的共同特征是数据量大、CPU 有限、要的是不拖后腿而不是极限压榨。我在做数据管道的时候用过一段时间的 LZ4一个 16 核的服务器上用 LZ4 压缩采集日志几乎感受不到 CPU 上涨换成 gzip 之后立刻能观察到采集延迟从 2ms 跳到 40ms。选哪种压缩器从来不是一个”最好“的问题而是一个”在什么场景下最合适“的问题。4. BWT 与 MTF给那些毫无规律的数据换个活法4.1 BWT 不是压缩算法它是压缩算法的前处理你打开一个人类可读的文本文件里面有很多地方看起来“像是有规律”但规律不是紧挨着的重复。比如英文里字母h后面经常出现t但你没法用几字节的滑动窗口把它们拉到一起。LZ77 在这里会显得力不从心gzip 压这种文本的比率可能不太理想。Burrows-Wheeler TransformBWT解决的问题就是这个它能把一段数据里“局部不明显但全局有规律”的上下文重排成连续重复度更高的形式。注意BWT 本身不压缩任何东西——它的输出长度和输入完全一致只是内容被重新排列了。怎么做到的我把每一步展开来讲。假设你有一串原始文本banana$其中$是一个虚拟的终止符且比所有字符都小。第一步把这个字符串的所有循环移位全部列出来banana$ anana$b nana$ba ana$ban na$bana a$banan $banana第二步把这些行按字典序排序$banana a$banan ana$ban anana$b banana$ na$bana nana$ba第三步记下排序后的最后一列字符也就是a$nnaaan这串东西——这就是 BWT 的输出。你可能觉得这很莫名其妙。但从最后一列里你其实能看出端倪n和a大量聚堆。原本在文本里相隔甚远的目标模式重排之后很多变成了连续或近邻的重复。这种经过 BWT 处理后的序列配合接下来要说的 MTF 和 RLE会让熵编码的效果大幅提升。4.2 MTF 和 RLE把重复转化为小数字BWT 输出后字符确实聚集了但还不足以直接扔给 Huffman。此时要上场的是 Move-to-FrontMTF变换。它的逻辑是维护一张按最近使用顺序排列的字符表每读入一个字符就输出它在表中的位置然后把这个字符挪到表头。我举个例子。假设表初始是abcdefgh待变换序列是banana读入b它在表中位置是 1输出 1表头变b...。读入a输出 1因为表现在是bacdefgha 在位置1表头变ab...。读入n它不在前几位输出 6表头变nab...。读入a此时它在表里位置已经是 1 了输出 1。依此类推。你会看到只要一个字符最近被用过、马上又出现MTF 输出的数字就会很小。大量输出集中在 0、1、2 这几个小值上这又让下一步的熵编码占了大便宜。bzip2 的整个链条就是这样BWT 变换 → MTF → RLE → Huffman。这也是为什么 bzip2 压文本文件往往比 gzip 压得更狠因为它的前处理更擅长挖掘长距离的统计规律。4.3 bzip2 的代价bzip2 的压缩率确实好但代价也摆在明面上内存和速度。BWT 需要对整个输入块做循环移位的排序排序复杂度接近 O(n log n)块越大越吃内存。默认 900KB 块大小的情况下bzip2 压一个 1GB 的文件内存峰值能到 10MB 级别压缩速度比 gzip 慢好几倍。在今天动辄 TB 级数据的场景里bzip2 已经慢慢被挤出主流工具链它的位置很大程度上被 xz 和 zstd 取代了。但理解 BWT 依然很有价值因为它是理解现代化压缩器 Bernstein 和 Brotli 某些设计思路的基础——Brotli 在 LZ77 之外就融合了上下文建模思想脉络和 BWT 的全局重排是一脉相承的进阶。5. 有损压缩允许丢弃之后压缩率被彻底放飞5.1 人的感知就是最大的冗余无损压缩折腾了半天核心逻辑都绕不开熵的下限。但 JPEG、MP3、H.264 这些有损格式根本懒得理这个下限——它们面对的是人眼和人耳而人类感知系统本身就有大量宽容度。砍掉那些感知不到的部分压缩率可以瞬间提升一个数量级。以 JPEG 为例一张 1920×1080 的 24 位位图原始大小约 6.2MB用高质量 JPEG质量因子 90压完只有 200~400KB压缩率超过 95%。这个数字远超任何无损方案能做到的程度靠的正是“细微的高频细节被丢弃掉人眼根本注意不到”。JPEG 的流程大致是这样先把图像按 8×8 分块对每块做离散余弦变换DCT把空间域的像素值转换成频率域的系数然后用一张人眼对亮度、色彩敏感度的量化表去整除这些系数——高频系数被量化得很粗很多直接归零接着做 zigzag 扫描把大量零值聚在一起最后上 Huffman 编码。整个过程里量化这一步就是有损的源头它决定了压缩率和画质的平衡点。5.2 音频压缩里的心理声学模型MP3 和 AAC 的思路类似只是把感知模型换成心理声学。人耳有一个特性叫听觉掩蔽当某个频率上存在一个响度足够大的声音时附近频率上较弱的声音会被“盖住”人耳完全听不见。编码器在分析窗口内计算出每个频段的掩蔽阈值然后把阈值以下的频谱能量直接扔掉再把剩下部分用 Huffman 之类的熵编码处理。这套机制解释了为什么 128kbps 的 MP3 听起来“还不错”——它并不是忠实还原了原始波形而是精确地保留了人类能感知到的部分把听不到的全扔了。我用过一个音频编辑项目里的波形文件一段 3 分钟的 WAV 是 30MB 左右压成 192kbps 的 AAC 只剩 2.8MB。如果压成无损格式 FLAC大概 18MB。对绝大多数播放场景来说2.8MB 和 18MB 的听感差异微乎其微这就是有损压缩的威力。5.3 有损和无损不是二元对立是连续谱工程里常见一个误解有损压缩就是“低质量”无损压缩就是“高质量”。实际上它们是一条连续谱。JPEG 的质量参数从 1 到 100MP3 比特率从 64kbps 到 320kbps都在同一个压缩器里换来不同的感知体验。选型逻辑应该基于实际用途存档原图、医疗影像、法律证据这类要求像素级还原的用无损流媒体、缩略图、语音通话这类人看的大胆用有损。同一个项目里两者完全可以并存我在做图片服务时原图走无损存档对外分发走 WebP 有损CDN 流量降了七成用户根本感知不到区别。6. 现代压缩器选型gzip、bzip2、xz、zstd、lz4 怎么挑6.1 一张实测对比表我把常见压缩器在相同机器上的表现整理一下数据来自我手头一个 38MB 的混合文本JSON 日志文件压缩级别取各工具的默认值。速度单位相对值只做同一机器上的横向对比。压缩器压缩后大小压缩速度解压速度内存占用典型场景gzip -6~4.1MB~45MB/s~210MB/s低几百KBHTTP传输、日志轮转bzip2 -9~2.9MB~3.5MB/s~80MB/s较高约10MB极少用了历史兼容xz -6~2.2MB~2.1MB/s~60MB/s很高约100MB软件发布包、冷存储zstd -3~2.6MB~210MB/s~430MB/s中约2MB日志管道、容器镜像zstd -19~2.1MB~1.8MB/s~380MB/s高约300MB极限归档、冷数据lz4 -1~9.5MB~820MB/s~3200MB/s低约1MB实时压缩、热数据上表能看出很多有意思的结论。zstd -3 的压缩率已经非常接近 bzip2但压缩速度快了六十倍。zstd -19 的压缩率能超过 xz解压速度更是碾压。lz4 压出来的文件比原始数据小了 75%但和 zstd 比还是有明显差距不过它的速度是无可替代的。6.2 别只看压缩率要看你愿意为它付出什么我在一个真实项目里踩过这个坑。当时做冷数据归档存储成本吃紧我看 xz 的压缩率最好就无脑把全量日志用xz -9压了。结果到了数据回溯的时候傻眼了——用户要查半年前的日志我们解压一个 10GB 的 xz 文件花了三四分钟。查询集群的 CPU 被解压任务占满其他业务跟着遭殃。后来我把方案改成冷数据落盘时用 zstd -19 压数据一旦进入回溯队列先用 zstd 解压成裸文本再喂给查询引擎。zstd -19 的压缩率只比 xz -9 低 3% 左右但解压速度快了五六倍。代价是内存占用变高可这台机器内存本来就不紧张CPU 瓶颈才是核心矛盾。这个经验后来我总结成一个选型心法评估压缩方案时先问自己是“写多读少”还是“写少读多”。写多读少的日志归档场景压缩速度优先读一次的成本分摊到长期存储收益里很划算写少读多的发布包、软件分发场景解压速度直接关系到用户体验必须给足权重。zstd 在这些维度上提供了很多档位选择这也是它近几年快速普及的根本原因。6.3 压缩参数里的几个实用细节如果你要动手压自己的数据有几个参数层面的细节值得记住。关于gzip -1到-9前者最快但压缩率最差后者最慢但压缩率最好。很多人以为压缩效果是线性递增的其实-6到-9的收益通常只有 2%~3%但时间可能翻倍。默认的-6是性价比最合适的点除非你时间不要钱否则不必追求-9。关于 zstd 的分级zstd 有从-1到-22共 22 个压缩级别但和 gzip 不同它的低级别也能保持相当高的压缩率。官方建议日常用-3归档用-19。如果你拿不准直接用默认级别就行zstd 的默认值已经足够均衡。另外 zstd 有几个不好找的选项值得关注--long可以启用大窗口匹配——把窗口从默认的几MB推到 128MB对某些重复跨度大的数据能显著提升压缩率但内存占用会飙升自己要权衡。关于多线程gzip 系列默认是单线程的压大文件时 CPU 利用率提不上去。zstd 和 xz 都支持-T0自动用满所有核心。对一个 20 核的机器来说zstd -T0 能把压缩 1GB 文件的时间从几十秒拉低到几秒压缩率几乎不受影响。这是我建议所有日志管道接入 zstd 的第一个理由。7. 纸上得来终觉浅用一段真实数据验证全部理论写到这里理论链条似乎完整了但如果不动手验证一下笔记还是缺了最关键的一环。我拿了一份真实环境的数据来验证一个包含 1 万行结构化 JSON 日志的文件大小 8.7MB。内容里大约 70% 是重复的字段名和固定文案剩下的才是变化的时间戳和数据值。先用 gzip 默认级别压得到 1.1MB压缩率约 87%。然后用 LZ4 压得到 3.2MB压缩率约 63%。再用 zstd -3 压得到 0.9MB压缩率约 90%。最后用 xz -6 压得到 0.8MB压缩率约 91%。这个结果印证了前面的理论LZ4 速度快但压缩率明显差一截gzip 是个稳健的基本盘zstd 用更少的时间做到了比 gzip 更好的压缩率xz 虽然压得最狠但慢得让人没脾气。如果在真实业务里让我选日志管道我一定选 zstd -3冷数据归档选 zstd -19热数据缓存用 LZ4。如果你也想自己验证压缩率与理论熵的关系可以做一个几十行的小实验取一个文本文件统计每个字符出现的频率套用公式算出熵再乘以文件长度得到一个理论最小字节数。然后分别用 gzip、bzip2、xz 去压这个文件把实际压缩后的字节数和理论值对比。你会发现两者的差距通常不超过 10%而且 zstd -19 离理论值的距离已经非常接近了。8. 压缩不止于文件它是一套通用的系统思维学压缩原理有个意想不到的收获它训练你看问题的视角。香农熵告诉你任何信息表达都有成本下限LZ77 告诉你善于引用过去能省大量重复劳动BWT 告诉你换个排列顺序原来很难处理的数据会变得温顺有损压缩告诉你一刀切地追求无损有时是为了一个用户感知不到的细节付出十倍代价。在实际工作中我开始不自觉地应用这些思想。设计日志规范时我会刻意减少无意义的输出字段让数据更接近高熵状态从而提升后续压缩收益设计接口返回结构时我会把高频共享字段和低频独有字段分离方便传输层做预测压缩评估某个存储方案的时候我会计算压缩可能带来的 IO 节省和 CPU 开销而不是只看单条数据多占了几 KB。说白了压缩原理讲的不只是怎么把文件变小。它回答的是一个更本质的问题在信息世界里如何用最小的代价表达足够的信息。这个能力在任何领域都用得上。这套笔记写到这里其实也是我把自己对信息系统的理解重新整理了一遍。下一次当你再右键压缩一个文件的时候希望你能想起窗口、熵、变换这些老朋友——它们一直在那里只是平时你感觉不到。
