哈夫曼编码
哈夫曼编码根据符号频率构建最优的二进制前缀码。每次合并权重最小的两棵树，让低频符号位于较深位置，高频符号使用较短编码。默认 ABRACADABRA 的载荷为 23 位，同符号集的定长码为 33 位。
摩尔斯码也给常见 E 一个点、Q 四个信号，但它依赖字符间停顿。普通比特流没有停顿，因此哈夫曼码要求任何符号码都不是另一个的前缀。把符号只放在树的叶子上，就能满足这一点。
哈夫曼编码如何工作
统计频率，每个符号作为带权单节点树放入最小优先队列。反复取出最轻的两棵，接到权重为两者之和的新父节点下，再把合并树放回队列，直到只剩一棵。
从根到各符号叶子，左边记 0、右边记 1，路径就是码字，深度就是码长。合并顺序决定哪些符号承担更长编码。
为什么最小两项可以先合并
取一棵最优前缀树中最深的一对兄弟叶子，把两个最低频符号交换到那里。低频符号加深所增加的成本，不超过高频符号变浅节省的成本，因此总成本不增加。于是至少存在一棵最优树，让这两个最低频符号成为兄弟。
把它们缩成权重之和的一个符号，重复同样论证，再展开。这个归纳过程证明每次最小合并安全。
同权重时，本课按创建顺序处理，让相同文本得到相同树。其他一致平局规则也可得到最优树，码字可能不同，最优总位数相同。
画布把优先队列画成从左到右排序的架子，以展示“取最小两项”。Python 实际使用 heapq，内部数组不是全排序；堆课程另行展示它的存储结构。
逐步演示
默认 ABRACADABRA，11 个字符、5 种符号。
- 计数：A 五次，B、R 各两次，C、D 各一次。
- 队列：按频率和创建顺序为
C(1) · D(1) · B(2) · R(2) · A(5)。 - 合并一：C、D 合为权重 2 的
[CD]。同为 2 时旧节点优先，得到B(2) · R(2) · [CD](2) · A(5)。 - 合并二：B、R 合成 4，队列
[CD](2) · [BR](4) · A(5)。 - 合并三：CD、BR 合成 6，队列
A(5) · [CDBR](6)。 - 合并四：5 与 6 合并，根权重 11，等于文本长度。
- 编码：左 0、右 1。A 距根一边，码为
0；其余深度三，C=100、D=101、B=110、R=111。 - 输出：
0 · 110 · 111 · 0 · 100 · 0 · 101 · 0 · 110 · 111 · 0，共 23 位。五种符号定长每个需⌈log₂ 5⌉ = 3位，共 33 位，减少约 30%。五个 A 各从三位降到一位，省下十位。
画布每次取架子最左两树，琥珀色 min pair 括号标出它们。结尾绿柱 23、灰柱 33 比较载荷，不含码表。实际文件还需让解码器知道编码规则，这么短的文本中，表头可能超过节省的十位。
时间与空间复杂度
令 n 为文本长度，k 为不同符号数。
| 阶段 | 常用计数模型下的成本 |
|---|---|
| 统计频率 | O(n) |
| 堆上构树，k−1 次合并 | O(k log k) |
| 访问树并分配路径 | O(k) 次节点访问 |
| 编码 | O(n) 次符号查询 |
常用固定字母表、码字操作按常数处理的模型下，总时间 O(n + k log k)，树与频率表空间 O(k)。若逐位生成输出、复制全部码字，还要计入输出位数和码字总长度，不能把这些可变长数据当成免费。
合并次数固定为 k−1，压缩收益却由频率分布决定。在同一至少二符号字母表的二进制前缀码模型下，定长码也是合法候选，因此哈夫曼载荷不劣于它。能否省位，取决于最优平均码长是否低于 ⌈log₂ k⌉。
边界情况
- 只有一种符号：没有合并，根也是叶子，路径为空。本实现用
path or "0"赋一位码，避免按当前解码约定输出空串。其他格式也可另存长度，但必须有明确约定。 - 两种符号：各一位，即使频率偏斜也如此。逐符号二进制前缀码不能给一个符号半位；算术编码可跨符号降低平均位数。
- 与定长相同：Uniform 的四种等频符号各两位，总计 24 对 24。五种等频符号仍可省位，24 对 30；频率 3、3、2、2 虽不均匀，也可在 20 位打平。是否均匀不等于是否打平。
- 极端偏斜：频率 1、2、4、8 可形成链式形状，低频码长到 k−1，但总量仍更优。Skewed 为 25 对 30。
- 平局：创建顺序使本课可复现；其他选择可改形状和码字，不改最优总成本。
常见错误
- 只排序一次后顺次配对。 合并父节点必须回队列，以新权重参与之后选择。
- 按频率名次直接分配
0、1、01。 可能让一个码成为另一个的前缀，无法判断何时结束符号。需要保持前缀无歧义规则。 - 忽略单符号约定。 本实现需要
path or "0"，否则空路径无法按当前格式表达重复次数。 - 只发送载荷，不提供编码规则。 解码器需树、码表或可复建的频率与规则。实际压缩比要计入表头，短文本不代表会省文件空间。
- 编码器与解码器平局不一致。 两棵树都可能最优，却映射到不同码字。靠频率重建时，必须采用同一平局规则。