信息论如何撑起数据压缩

可视化演示

展示香农熵、信源编码与数据压缩的核心原理，通过符号概率分布和编码树直观理解信息压缩的理论基础。

压缩的本质：整理家当的第一步

蚂蚁工头第一次整理行李，发现仓库里散落着三百片完全相同的树叶。如果他给每片树叶单独装箱，那就白白浪费了 299 份“重复的劳动”。聪明的做法是把它们叠成一摞，用一个标签写上“三百片树叶”。数据压缩做的事情一模一样：找到这种重复的摆放方式，把它合并掉——在信息论里，这种重复和多余被统称为冗余。压缩率就是衡量整理效果的那把尺子：整理后的箱数相比原来少了几倍。

从蚂蚁的仓库回到计算机的世界，任何可以被压缩的文件里都藏着冗余：文本中反复出现的“the“是冗余，图片中大块相同的颜色是冗余，音频里没有声息的停顿也是冗余。无损压缩做到”箱子里一件东西都没少，解压后和原来一字不差”；有损压缩则主动丢掉感知上最不重要的东西，就像搬家时扔掉生了虫的旧木凳。两者共享同一把尺子——压缩率。

整理的第一步永远是“找重复、合并同类”。没有这一步，后面所有编码技巧都无从谈起；而一旦完成了这一步，我们就会追问一个更深刻的问题：一件家当究竟“多重”才算正常？这就是下一节的信息量。

信息量与熵：给每件家当称“稀有度”

蚂蚁情报员负责记录仓库里每件物品的价值。他发现，判断一件物品“值多少信息”，不看它本身有多大，而看它出现的概率有多低。每天都能见到的松果，看到它一点都不意外，携带的信息量几乎为零；而一块几十年一遇的琥珀，一旦出现就让所有蚂蚁围过来——它的信息量极高。情报员把这个“意外程度”量化成一个公式：概率越低，意外程度越高，信息量越大。

单件物品的意外程度只是起点。蚁后真正关心的，是整间仓库平均每件物品的意外程度——如果把仓库里所有符号的“信息量”按概率加权平均，就得到熵。熵的单位同样是比特，它表示“平均每个符号最少需要多少比特才能无损表达”。仓库里的物品种类越均匀、越没有规律，熵就越大，打包也就越困难。

熵的大小直接决定了搬家难度：全是树叶的仓库熵接近 0，一个标签就能打包；而什么都有、比例平均的仓库熵就大，必须为每种物品单独准备编码。蚂蚁们现在有了“家当混乱度”的尺子，下一步要问：最好的打包师到底能做到多小？

信源编码定理：打包师的天花板

蚁后听说有“理论体积”这回事后不服气，请来了全森林最聪明的打包师：“你是不是箱子不够小，才说什么极限？”打包师摇头：“任何无损打包，平均每件物品占用的标签长度都一定不小于熵。这不是手艺问题，是数学上的能量守恒。”这句“打包界的能量守恒”，就是信息论里最著名的信源编码定理，也叫香农第一定理。

定理说的是两件事：第一，任何无失真的编码方案，平均码长 $L$ 都不可能低于信源熵 $H(S)$；第二，只要算法足够聪明，就总能把平均码长压到比熵多不到 1 比特的范围内。换句话说，熵是地板，而“比地板高 1 比特”是聪明打包师能摸到的天花板。

这条定理让搬家公司从此有了预算表：先算熵，再定 KPI。ZIP 压完的文件再大，也不会小过熵给出的极限；如果有一天你发现某个算法把数据压得比熵还小，那只有两种可能——要么概率模型估错了，要么压缩其实是有损的。理解了这个天花板，我们才能欣赏接下来两代打包术的各自高明之处。

霍夫曼编码：贪心打包法

工头听完定理，决定亲手设计一套打包方案。他的思路很朴素：把仓库里最稀有的两堆物品先合并成一个“大柜子”，给这个柜子统一贴一张标签，下次再遇到它们就只要进柜子内部找；然后重复这个动作，不断把当前最稀有的两堆合并。从下往上看，所有物品被组织成一棵“行李树”，每件物品的标签就是它从树根一路走向自己的那串 0 和 1。这就是霍夫曼编码。

这套方法妙在两点：其一，它是贪心的——每次都只处理当前最小的两个概率，却能得到全局最优；其二，它天然满足前缀码性质——没有任何一个码字是另一个码字的前缀，所以解码时不需要分隔符，扫一遍 0/1 串就能无歧义地还原。高频物品被放在树的高处，路径短；稀有物品被埋在树的深处，路径长，平均码长因此被压到接近熵。

蚂蚁们按这套“行李树”打包后，箱子数量果然大幅减少。但细心的情报员发现一个遗憾：当符号概率不是 2 的整数次幂时，比如 0.15、0.08 这种“不整”的概率，每个符号至少要占用 1 个整数比特位，总会浪费一点点空间。有没有办法连这一点点也省下来？下一节，工头决定不再给每件物品单独贴标签，而把整堆行李看成一个整体来编码。

算术编码：一根刻度尺装下全仓库

霍夫曼编码就像给每件物品单独贴标签，标签的长度必须是整数个比特。而工头在某个深夜想到了一个更疯狂的主意：干脆不给单件物品贴标签，把整堆行李当作一个整体，在一条从 0 到 1 的刻度尺上定位它。他规定：读入第一件物品时，按它的概率把 [0,1) 切成几段，选中属于它的那一段；读入第二件物品时，再在刚刚选中段里按概率切一刀。物品一件件进来，区间一段段缩小，最终整个序列就对应刻度尺上一段极小的区间。

解码时只需要知道这个区间里的任意一个小数，就能反向一步一步还原出整串物品。因为输出的是“整个序列在尺子上的位置”，而不是每个符号各自的整数码长，算术编码可以为很小概率的符号也分配“比 1 比特更少”的平均空间，因此它比霍夫曼更贴近熵极限——在上面的动效里，ARI 那根柱子几乎压到了红线。

蚂蚁们用刻度尺把整仓库行李“折叠”成一个点，理论上终于贴近了熵线。但工头很快发现，这套方法虽然精妙，却要维护一张巨大的概率表。回到实际工程，还有没有更简单粗暴、又能处理海量数据的招？有——ZIP 靠的不是精雕细刻，而是“重复的绝不重复打包”。

ZIP与LZ77：金牌打包队的组合拳

真到了搬家那天，工头发现一个比“符号频率”更明显的浪费：仓库里有一百片完全相同的树叶排成一排。如果一片片编码，就算每个标签只有 1 比特也要花 100 比特。工头灵机一动，在货单上写了一行字：“从第 3 排开始，连续 100 片树叶，和前面第 50 排的完全一样。”这一行字就取代了 100 次编码。这就是 LZ77 的思想：用一块滑动窗口记住最近见过的内容，一旦发现重复串，就输出一个“距离 + 长度”对，告诉解码器“去前面哪个位置复制多长一段”。

ZIP 实际使用的 DEFLATE 算法，正是 LZ77 和霍夫曼编码的组合拳：先用滑动窗口把重复子串替换成短小的 （距离，长度） 记号，再用霍夫曼编码压缩这些记号本身。解码时滑动窗口不断回放历史，得到的数据与原始文件逐字节一致——所以 ZIP 是标准的无损压缩。文件里重复越多，压缩率越惊人，这也解释了为什么代码文本能压 5 到 10 倍，而已经高度随机的加密数据几乎压不动。

ZIP 的成功证明：在工程世界里，与其费尽心思给每个符号贴最优标签，不如先把明摆着的重复清掉。而信息论的眼光还可以走得更远——当压缩的对象从文本变成神经网络的表征时，蚂蚁整理的就不再是仓库，而是数据本身的“气质”。

压缩与表征学习：让 AI 学会拎重点

如果蚁后想让远方的蚂蚁朋友快速了解“我们仓库的整体气质”，她不会念完整张清单，而是说：“东西很多，树叶为主，偏绿色，整体很轻。”这几个关键词就是仓库的表征——一种高度压缩后的抽象。机器学习中的表征学习做的是同一件事：把高维输入数据压成一个低维向量，让后续任务只依赖这个“压缩包”。

信息论为表征学习提供了一把精确的手术刀——信息瓶颈。它要求模型学到的表征 $Z$ 与原始输入 $X$ 的互信息尽量小（压得越狠越好），同时保证 $Z$ 与任务标签 $Y$ 的互信息足够大（有用的信息不能丢）。这完美对应了有损压缩的质量权衡：把文件压得越小越好，但不能让解压后失真到无法使用。自编码器、量化模型、embedding 降维，本质上都在实践这条法则。

蚂蚁用几个词概括仓库，AI 用几个比特抓住数据的本质。从熵到信源编码定理，从霍夫曼到算术编码，再到 ZIP 和表征学习，压缩从来不只是“变小”的技术，而是一套关于“什么值得保留、什么可以舍弃”的数学哲学。理解了熵，你就同时理解了文件压缩的极限和深度学习表征的边界。

AI 应用场景

Python 演示

import heapqfrom collections import Counter class HuffmanNode:    def __init__(self, char, freq):        self.char = char        self.freq = freq        self.left = None        self.right = None     def __lt__(self, other):        return self.freq < other.freq def build_tree(text):    freq = Counter(text)    heap = [HuffmanNode(ch, f) for ch, f in freq.items()]    heapq.heapify(heap)    while len(heap) > 1:        a = heapq.heappop(heap)        b = heapq.heappop(heap)        parent = HuffmanNode(None, a.freq + b.freq)        parent.left = a        parent.right = b        heapq.heappush(heap, parent)    return heap[0] def build_codes(node, prefix="", codes=None):    if codes is None:        codes = {}    if node.char is not None:        codes[node.char] = prefix    else:        build_codes(node.left, prefix + "0", codes)        build_codes(node.right, prefix + "1", codes)    return codes def encode(text, codes):    return "".join(codes[ch] for ch in text) def decode(bits, root):    res = []    node = root    for b in bits:        node = node.left if b == "0" else node.right        if node.char is not None:            res.append(node.char)            node = root    return "".join(res) if __name__ == "__main__":    text = "hello huffman compression"    root = build_tree(text)    codes = build_codes(root)    bits = encode(text, codes)    original_bits = len(text) * 8    compressed_bits = len(bits)    print("code table:", codes)    print("original bits:", original_bits)    print("compressed bits:", compressed_bits)    print("compression ratio: %.2f%%" % (100 * compressed_bits / original_bits))    print("lossless roundtrip:", decode(bits, root) == text)

1. heap = [HuffmanNode(ch, f) for ch, f in freq.items()]把每个字符包装成一个节点，放进最小堆，相当于蚂蚁把每种物品单独成一堆。
2. while len(heap) > 1:反复取出最小两堆合并，对应“先处理最稀有的两件家当”。
3. parent = HuffmanNode(None, a.freq + b.freq)合成一个空字符的内部节点，它的频率是两个子节点之和。
4. parent.left = a` 与 `parent.right = b把两个子节点挂到新节点上，行李树逐渐成形。
5. codes[node.char] = prefix走到叶子节点时，把从根到叶的 0/1 路径记为码字。
6. def encode(text, codes)查码表把每个字符替换成比特串，完成压缩。
7. original_bits = len(text) * 8假设一个字符原本占 8 比特，这是压缩前的成本。
8. print("lossless roundtrip:", decode(bits, root) == text)解码后再比对原文，验证无损。

常见误区

面试题