信息论与编码篇---最佳不等长编码
简单来说，最佳不等长编码就是：在保证无损压缩的前提下，让平均码字长度最短的那种编码方法。
1. 什么是不等长编码？
想象你要给一本小说做数字压缩：
等长编码（笨办法）：不管"的"（出现几万次）还是"龘"（出现1次），每个字都用相同长度的二进制码。这很浪费，因为"的"完全可以编得更短。
不等长编码（聪明办法）：高频用短码，低频用长码。就像摩尔斯电码一样，最常用的
E用.，很少用的Q用--.-。
2. 什么是"最佳"？
"最佳"有两个含义：
| 层面 | 含义 | 通俗理解 |
|---|---|---|
| 理论最佳 | 平均码长 ≥ 信源熵 H | 熵 H 是理论下限，不可能更低 |
| 实际最佳 | 平均码长 L 无限接近 H | 找一种编码让 L 尽量小 |
最佳不等长编码就是：在给定信源概率分布的情况下，找到一种编码方法，使得平均码长 L 最小，同时还要满足唯一可译（解码无歧义）。
3. 最经典的算法：哈夫曼编码
哈夫曼编码是最佳不等长编码的代表。它的核心思想特别简单：
把概率最小的两个符号，合并成一个新符号，反复进行，直到只剩一个符号。
步骤图解（以符号 A、B、C、D 为例）：
假设概率：A=0.5，B=0.25，C=0.125，D=0.125
第一步：找概率最小的两个（C和D，都是0.125），合并成新节点 CD=0.25
第二步：现在有 A=0.5，B=0.25，CD=0.25。再找最小的两个（B和CD），合并成 BCD=0.5
第三步：现在有 A=0.5，BCD=0.5。合并成 ABCD=1.0
第四步：从根往下走，左边标0，右边标1（反过来也行）
结果：A=0，B=10，C=110，D=111
检查：平均码长 = 0.5×1 + 0.25×2 + 0.125×3 + 0.125×3 = 1.75 比特，正好等于熵（理论最优）。
4. 最佳不等长编码的特点
| 特点 | 说明 |
|---|---|
| 概率匹配 | 概率越大的符号，码字越短 |
| 前缀码 | 任何一个码字都不是另一个的前缀，解码无歧义 |
| 即时解码 | 读到最后一个比特就能立刻解码，不需要往后看 |
| 最优性 | 在给定的概率分布下，平均码长最小 |
| 唯一性 | 码字分配可能不唯一（0/1可以互换），但平均码长唯一 |
5. 生活中的类比
想象你要给一个班级的同学编学号，但学号长度根据姓氏出现频率来定：
张同学（概率30%）→ 学号
0（最短）王同学（概率25%）→ 学号
10（次短）李同学（概率20%）→ 学号
110（中等）其他同学（概率25%，各1-2%）→ 学号
1110、1111等（长）
这样设计，点名时平均报号长度最短，但又不会搞混谁是谁。
6. Mermaid总结框图
框图解读：
起点（蓝色）：已知信源的概率分布。
目标（粉色）：找到平均码长最小的不等长编码。
方法（绿色）：哈夫曼编码是最经典的实现算法。
步骤：反复合并最小概率的两个符号，构建码树。
结果（黄色）：
概率匹配：高频短码，低频长码
前缀码：保证唯一可译和即时解码
最优性：平均码长最小，逼近理论极限熵 H
一句话总结：最佳不等长编码就是哈夫曼编码，它通过给高频符号分配短码、低频符号分配长码，让平均码长最短，同时保证解码无歧义。