第3章 减重车间：源编码与压缩

第 3 章 · 减重车间：源编码与压缩

章节摘要：本章跟着一批货物走完减重流水线——先立规矩（无损压缩不可能低于熵的下界），再上工艺（霍夫曼与算术编码如何贴线作业），最后打开"允许磕碰"的新车间（速率失真理论用误差换减重）。

一条主线

发货员面对一堆包裹，想把每个都压到最轻再上路。减重的第一原则是不能摔坏货：接收端必须能一字不差地还原，这叫无损压缩。香农第一定理给这条流水线立了底线：无论编码多聪明，平均码长不可能低于信源熵——货物里"真正压不掉的重量"就是它的不确定度。这个下界既是绝望（别想压得更小了）也是希望（达到它就到头了，可以收工）。

第二条生产线允许"轻微磕碰"：图片的某个像素偏了两阶灰度、音频里人耳听不见的频率分量，丢掉它们换来更轻的包裹。速率失真理论把这笔"误差换重量"的交易画成一条曲线——愿意接受多大失真，就能换到多低的码率。整章的主线就是这两条生产规则与两代工艺的交替展开。

减重流水线全景

沿途站点

三点一 无损压缩的极限：香农第一定理。立规矩的一节：前缀码与克拉夫特不等式如何约束码长分配的合法性，香农码怎样一步到位把平均码长压到"熵加一"以内，以及为什么加大编码块能让开销消失。读完你手上会有"任何压缩软件宣称突破熵界都该被怀疑"的判据。

三点二 霍夫曼与算术编码实战：把文本放上秤盘。上工艺的一节：完整实现霍夫曼编码并用一段样本文本实测压缩比；再讲算术编码如何用一个区间的小数点位置装下整条消息，把"熵加一"的零头开销磨掉。这是全册代码密度最高的一节。

三点三 有损压缩与速率失真：接受误差换取减重。开新车间的一节：失真怎么度量、率失真函数怎么定义、二元信源的显式公式怎么算，以及量化、变换编码、感知加权这些现代有损工艺各自在曲线上摘取哪一段收益。

拐点与结论

本章的第一个拐点在三点一：压缩的本质是建模。克拉夫特不等式只管码长合法性，真正决定能压多小的，是你对信源概率分布的估计有多准——建模台的读数直接决定车间能减掉多少重量。zip 类压缩软件里的上下文建模、预测滤波，全都是"先把分布估准"的努力；模型比熵更乐观，码长就必然超出下界，超出的部分正是第 2 章的相对熵。压缩与统计推断在这里合流。

第二个拐点在三点三：失真是设计变量而不是事故。一旦把允许的误差从常数变成可调参数，压缩问题就从"压到多小"变成"在失真-码率曲线上选哪个点工作"——整部有损编码史（从电话语音到流媒体视频）都是在这条曲线上找感知上最划算的操作点。这个思维后来被机器学习整个借走：自编码器的"重建误差加隐层复杂度"目标，就是速率失真公式的可学习版本。

一条给读者的路线提示：三节按"立规矩、上工艺、开新区"排列，前两节建议连读（下界与工艺互为印证），第三节可以独立阅读；每节的代码都能独立运行，把它们串起来跑一遍，相当于亲手装配了一条微型压缩流水线。若只关心"为什么压缩软件压不了我的文件"这类日常疑问，直接从三点一的边界澄清读起也完全可行。

读完你应该

• 能用克拉夫特不等式判断一组码长是否对应合法的前缀码，并说明它与"码树叶子不重叠"的等价性；
• 能手算香农码的码长分配，验证平均码长落在熵与熵加一之间，并解释块编码为何能消除这"加一"的尾巴；
• 能从零实现霍夫曼编码，对一段真实文本算出平均码长与压缩比，并与字符熵对照；
• 能讲清算术编码"区间套小数"的原理，以及它对高阶上下文模型的天然适配性；
• 能写出二元信源汉明失真下的率失真公式，算出给定失真下最低码率，并解释"失真超过信源偏置后码率归零"的原因。

下一章的接力

包裹减到最轻，接下来的问题是路能承受多少。第 4 章把视线从车间转向道路：信道容量给出每秒可靠通过的重量上限，香农第二定理证明低于这个上限就能可靠传输。减重车间给出的最轻包裹，正好是承重检测要称的货物。