7.1 通用编码与最小充分统计

7.1 通用编码与最小充分统计

本节摘要：介绍不必预知分布的通用编码——LZ 家族如何边跑边学地逼近熵率，冗余的极小极大账本如何计算；再把统计学的充分统计与无损压缩放到同一张信息论图纸上，说明"最优摘要=最小充分压缩"的统一视角。

一个压缩器如何面对它不认识的数据

第 3 章的霍夫曼与算术编码都有一条隐含前提：概率表先于压缩存在。可是给一个新格式的日志文件、一段没见过的基因组序列、一种新设备的传感流——谁去先统计出分布？逐个信源定制码表的成本高得荒谬，而数据类型的增速远快于码表设计的速度。

通用编码的研究纲领是：设计一个不依赖任何具体分布先验的压缩器，对一切平稳遍历信源，渐近逼近其熵率。不需要知道你是谁，只要求你是"统计上稳定的"——压缩器边读边建字典、边统计边自适应，样本越长，学到的分布越准，码长越贴向真实熵率。这个纲领由齐夫与伦佩尔在一九七七年前后完成：LZ77 用"回指之前出现过的串"替代概率模型，LZ78/LZW 用在线生长的字典实现同样的效果。压缩器自己长成了统计学家——这是通用编码最深刻的身份转变。

LZW：一边读、一边长大字典的压缩器

LZW 的机制可以用三句话说尽：读入字符串时总尝试在字典里找"能匹配的最长短语"；找到了就输出它的编号并继续，找不到就把这个新短语登记进字典（编号递增）。字典从单字符开始，随着数据流不断长出更长的短语——重复模式越多，字典里的短语越长，每次输出携带的信息越多。

# LZW 通用编码演示：不预设任何概率模型
def lzw_encode(data: bytes):
    table = {bytes([i]): i for i in range(256)}   # 初始字典：单字节
    out, w = [], b""
    for byte in data:
        wc = w + bytes([byte])
        if wc in table:
            w = wc                                  # 还能匹配，贪心地继续伸长
        else:
            out.append(table[w])                    # 输出当前短语的编号
            table[wc] = len(table)                  # 新短语登记进字典
            w = bytes([byte])
    if w:
        out.append(table[w])
    return out

import random
rep = ("信息论称量信息论称量信息论称量" * 6).encode("utf-8")   # 高度重复的中文流
codes = lzw_encode(rep)
print(f"重复文本: {len(rep)} 字节 → {len(codes)} 个码字"
      f"（按 16 比特码字计 {len(codes) * 2} 字节，压到 {len(codes) * 2 / len(rep) * 100:.1f}%）")

random.seed(1)
rnd = bytes(random.randrange(256) for _ in range(200))          # 均匀随机字节
codes2 = lzw_encode(rnd)
print(f"随机字节: 200 字节 → {len(codes2)} 个码字"
      f"（16 比特计 {len(codes2) * 2} 字节，膨胀到 {len(codes2) * 2 / 200 * 100:.0f}%）")
# 输出:
# 重复文本: 270 字节 → 83 个码字（按 16 比特码字计 166 字节，压到 61.5%）
# 随机字节: 200 字节 → 200 个码字（16 比特计 400 字节，膨胀到 200%）
​

两个读数各讲一个道理。重复文本被压到六成——字典很快长出整句短语，回指代替了逐字传输；随机字节则膨胀到两倍——没有可学的模式，字典全是无用功，编号本身比原始字节还宽。第二个读数不是缺陷而是诚实：熵接近满载的信源本来无可压缩，通用编码在"学不到规律"时至少应当承认这一点（成熟实现会把"原样存储"作为回退模式）。这正呼应第 3 章的箴言——压缩的收益全部来自规律，通用编码只是把"找规律"自动化了。

理论侧的账本同样清楚。对平稳遍历信源，LZ 类算法的每符号冗余（超出熵率的部分）随样本长度按其倒数的对数级收缩——渐近最优对一切分布同时成立。极小极大视角把这写成对偶：不存在对某分布更好、对别的分布更差的摇摆，通用编码支付的是"万分布皆优"的均匀代价。统计学习理论里的"没有免费午餐"边界在此有精确的正面版本：为不确定性支付的冗余可以任意小，只要你肯读足够长的样本。

充分统计：统计学与压缩的同构

换个门进来会发现同一座房子。统计学问：观测了一堆数据 X，想推断参数，能不能把数据压缩成一个摘要 T(X) 而不损失任何推断信息？充分统计量的定义恰好用信息论写出来最干净：T 是充分的，当且仅当给定 T 后数据与参数的互信息为零——摘要之外的部分对参数不再含有信息。

这个定义的深刻在于把"摘要"与"压缩"统一了。把参数换成"信源的下一部分"，充分性就是"预测所需的全部历史信息"；把充分统计量的维度压到最小，就得到最小充分统计量——信息论意义上不可再压缩的摘要。举一个经典算例：抛一枚未知概率的硬币 n 次，完整记录是一长串正反面序列，但推断概率只需要次数统计（正面的个数）——一个数对一串序列，压缩比巨大，而关于硬币的一切推断信息分毫未损。二项分布属指数族，其充分统计的维度恒定，不随样本量增长——"可以无限压缩的摘要"正是指数族在统计推断里地位特殊的根源。

两端合起来看：压缩器是自动寻找充分统计的机器。字典里长出的短语、算术编码器里的自适应频率表，本质都是对"预测下一步需要什么历史信息"的在线估计。机器学习中的表征学习把这句话推向极端——神经网络中间层想学的，正是"对下游任务充分"的最小表示，这也是第 8 章信息瓶颈的入口。

💡 一条可带走的洞见：评估任何摘要系统（报表、特征、嵌入向量）时，问两个信息论问题就够了——它对目标保存了多少互信息（充分性），它的规模比原始数据小多少（压缩率）。两个数一比，摘要的性价比就现形了。

通用性的对偶账：万分布皆优的代价

通用编码"对一切平稳信源渐近达熵率"听上去免费，极小极大账本算清了它的隐性条款。对偶原理：通用编码在"最坏分布下的冗余"与"自适应统计的代价"之间画出一条对偶线——你为不知道分布付出的冗余，恰好等于一次"模型选择"的统计代价。计数论证给出直观版本：长度为 n 的二进制串里，能被压缩掉哪怕一比特的串占比不超过一半；能压掉 k 比特的占比不超过二的负 k 次方——绝大多数序列无法被任何通用压缩器压小，能压的都是"恰好有规律"的少数。这与第 3 章柯尔莫哥洛夫复杂度的"不可计算"一起，构成了压缩理论的"硬边界三部曲"：单串极限不可算、万分布皆优有对价、随机数据本质不可压。

工程侧的对价更实在：通用压缩器对"它认识的数据类型"要慢半拍——字典要现学、模型要热身，短文件的压缩比明显吃亏（第 8.2 节随机字节膨胀实验的温和版本）。预置字典（把常见数据类型的统计规律预烧进压缩器）是标准的折中方案，新一代压缩工具的"训练模式"就是这个思路的产品化——通用性与启动性能的权衡，本质还是那本对偶账。

本节要点回顾

• 通用编码不预设分布，对一切平稳遍历信源渐近逼近熵率——压缩器自己长成统计学家；
• LZW 用在线生长的字典实现"回指代替传输"，重复流压到六成，随机流膨胀两倍——诚实承认无可压缩；
• 冗余的极小极大账本：为"万分布皆优"支付的均匀代价随样本长按对数倒数级收缩；
• 充分统计的信息论定义——给定摘要后数据与参数互信息为零；最小充分统计即不可再压缩的摘要；
• 压缩器是自动找充分统计的机器：字典、频率表、神经网络中间层，都是"预测所需历史"的在线估计。

经典世界的前提松动到此。下一节把载体换成量子比特：在测量即破坏、复制被禁止的世界里，称量规则如何改写。