哈夫曼编码压缩：用变长编码缩小模型权重的存储

什么是哈夫曼编码？

哈夫曼编码是一种经典的无损数据压缩算法，由大卫·哈夫曼在1952年提出。它的核心思想是“变长编码”：使用频率越高的符号，分配越短的二进制编码；使用频率越低的符号，分配越长的编码。这样，整体的平均编码长度就会缩短，从而达到压缩数据的目的。

在深度学习领域，模型权重通常以固定长度的浮点数存储，占用大量存储空间。利用哈夫曼编码，我们可以对权重的出现频率进行统计，用更紧凑的编码表示常见权重值，从而缩小模型的整体存储体积，这正是哈夫曼编码压缩模型权重的基本思路。

变长编码相比定长编码的优势

假设我们有一个仅包含4个符号的文本：A, B, C, D。在定长编码中，每个符号需要2个二进制位来表示（例如 A=00, B=01, C=10, D=11）。如果符号的出现概率不均匀，比如 A 出现了100次，B、C、D 各出现了10次，那么定长编码的总位数为 (100+10+10+10)*2 = 260 位。

而哈夫曼编码会根据频率重新分配码字：

• A（频率最高）→ 0
• B → 10
• C → 110
• D → 111

总位数变为 100*1 + 10*2 + 10*3 + 10*3 = 160 位，压缩率达到 160/260 ≈ 61.5%。可以看到，频率越集中的数据，哈夫曼编码的压缩效果越明显。

哈夫曼树的构建过程

哈夫曼编码的实现依赖于一棵称为“哈夫曼树”的二叉树。构建步骤清晰且规整：

1. 统计频率

统计每个符号在数据中出现的次数（或概率）。例如，我们要压缩权重文件，可以将所有权重量化到有限个离散值，然后统计每个离散值出现的频次。

2. 初始化叶子节点

将每个符号看作一棵只有一个根节点的树，节点的权值等于该符号的频率。将这些节点放入一个优先队列（通常是最小堆），按权值从小到大排序。

3. 合并生成二叉树

重复以下步骤，直到队列中只剩一个节点：

• 从队列中取出两个权值最小的节点。
• 创建一个新节点作为它们的父节点，父节点的权值等于这两个子节点的权值之和。
• 将父节点放回队列。

最后剩下的节点即为整棵哈夫曼树的根节点。

4. 分配编码

从根节点出发，向左子树走编码为 0，向右子树走编码为 1，到达叶子节点时，路径上的二进制序列就是该符号的哈夫曼编码。

示例：
假设四种权重 w0, w1, w2, w3 的频率分别为 45%, 30%, 15%, 10%。

• 初始节点：10%, 15%, 30%, 45%
• 取出10%和15%，合并为25%，放回 → 节点顺序：25%, 30%, 45%
• 取出25%和30%，合并为55%，放回 → 节点顺序：45%, 55%
• 取出45%和55%，合并为100%，结束。

从根到叶的路径：
w3(10%) → 路径 RL (右-左) → 编码 01
w2(15%) → 路径 RR (右-右) → 编码 00
w1(30%) → 路径 L → 编码 1
w0(45%) → 路径 R → 编码 0

哈夫曼编码的压缩与解压流程

压缩过程

1. 数据扫描：遍历原始数据，统计每个符号的频率。
2. 构建哈夫曼树：根据频率生成编码表。
3. 替换编码：将原始数据中的每个符号替换为对应的变长编码，生成二进制流。
4. 存储必要信息：为了解压时能重建哈夫曼树，需要在压缩文件中保存频率表或编码树的结构。常见做法是存储频率表（或直接存储规范哈夫曼编码的码字长度）。

解压过程

1. 解码哈夫曼树：根据保存的频率表（或码字长度表）重建出完全相同的哈夫曼树。
2. 逐比特解码：从压缩二进制流的开头读取比特，从根节点开始，遇 0 则走左子节点，遇 1 则走右子节点，直到抵达叶子节点。输出该叶子对应的符号，然后回到根节点继续下一轮解码，直至所有数据恢复。

由于哈夫曼编码是前缀码，任何编码都不是另一编码的前缀，这使得解码过程无需额外分隔符，效率很高。

在模型权重压缩中的应用

将哈夫曼编码用于深度学习模型压缩，通常遵循以下流程：

1. 权重量化与聚类

原始模型权重多为32位浮点数，直接统计频率意义不大。我们先对权重进行量化或聚类，将其映射到有限个代表值（质心）上。例如，将权重矩阵的每个值分配到最近的聚类中心，然后用该中心的索引来表示原始权重。

2. 统计索引频率

量化后，模型参数变成了一个由索引组成的矩阵。统计每个索引出现次数，得到频率分布。通常，神经网络权重经聚类后，靠近零的值出现频率很高，呈现出较明显的不均匀分布，非常适合哈夫曼压缩。

3. 生成哈夫曼编码表并编码

对每个索引分配变长编码，将原始索引矩阵转换为二进制串。同时保存编码表和聚类中心的实际浮点值（码书），以便恢复完整模型。

4. 解压推理

使用模型时，先根据哈夫曼编码还原索引矩阵，然后通过查找码书将索引映射回浮点数权重，复原模型进行计算。由于哈夫曼压缩是无损的，还原后的权重与量化后的权重完全一致，不会额外损失精度。

扩展学习：规范哈夫曼编码

标准哈夫曼编码需要保存完整的树结构或频率表，开销较大。工程中常用规范哈夫曼编码来优化存储。它仅需记录每个符号的码字长度，并按照特定规则生成编码，就能保证唯一可解码性。

规范哈夫曼编码的生成规则很简单：

• 对于同一个码长的符号，按符号值顺序分配连续递增的码字。
• 不同码长之间遵守“长码的前缀不得与短码相同”的规则。

这样，解码端只需根据码字长度表即可快速重建编码树，极大减少了元数据开销。在模型压缩场景下，规范哈夫曼编码是实际落地的首选方案。

小结

哈夫曼编码利用符号的频率差异实现变长压缩，原理直观且易于实现。将模型权重通过量化得到离散索引，再利用哈夫曼编码压缩这些索引，能够显著缩小模型存储体积，同时保持无损的精度恢复。这一技术是许多模型压缩工具链中的重要一环，配合量化、剪枝等手段，让复杂模型在资源受限的边缘设备上运行成为可能。