4、霍夫曼编码：静态霍夫曼、动态霍夫曼、规范霍夫曼，以及我在嵌入式项目中用霍夫曼压缩日志的实战。

霍夫曼编码，说白了就是给数据里的每个符号重新分配一套「变长」的二进制编号。高频的符号给短码，低频的给长码。这样整体下来，数据量就变小了。

我最早接触这东西是在大学的数据结构课上。当时觉得不就是个二叉树嘛，没啥了不起。直到后来在嵌入式项目里被日志存储逼疯了，才真正体会到它的价值。

4.1 静态霍夫曼编码

静态霍夫曼，意思就是先扫描一遍原始数据，统计出每个符号出现的频率。然后根据这个频率建一棵霍夫曼树，再生成编码表。最后用这个编码表去压缩数据。

流程很简单：

1. 统计频率
2. 构建霍夫曼树（每次取两个最小频率节点合并）
3. 生成编码表（左0右1，从根到叶子）
4. 用编码表替换原始符号
5. 把编码表也存到压缩文件里（否则解不了）

我在一个传感器数据采集项目里用过静态霍夫曼。数据量不大，每次采集完一批再压缩，两遍扫描的代价可以接受。但有个坑——编码表本身也要占空间。如果数据本身很小，编码表可能比压缩后的数据还大。

4.2 动态霍夫曼编码

动态霍夫曼，也叫自适应霍夫曼。它不需要预先统计频率。编码器和解码器同时维护一棵动态更新的霍夫曼树。每处理一个符号，就更新频率并调整树结构。

好处很明显：

• 只需要一遍扫描
• 不需要存储编码表
• 适合流式数据

但代价也不小：

• 算法复杂得多
• 树要频繁更新，CPU开销大
• 初始阶段压缩效果差（因为频率还没统计出来）

我记得在调试一个网络传输模块时，试过动态霍夫曼。压缩率确实比静态的好，但CPU占用率高了将近30%。对于嵌入式设备来说，这个代价有点大。

4.3 规范霍夫曼编码

规范霍夫曼，是霍夫曼编码的一种「标准化」形式。它不改变码长，只改变码字的分配方式。

传统霍夫曼的码字是随意的，只要满足前缀码就行。规范霍夫曼则强制要求：

• 相同码长的码字，按数值递增排列
• 码长较短的码字，数值小于码长较长的码字
• 码字之间保持数值连续性

这样做的好处：

• 解码时不需要重建整棵树
• 只需要存储每个码长有多少个符号
• 解码速度更快

我举个例子你就明白了。假设有符号A、B、C、D，码长分别是2、2、3、3。传统霍夫曼可能给A=00、B=01、C=100、D=101。规范霍夫曼会强制A=00、B=01、C=10、D=11——等等，这不对，因为C和D的码长是3，不能和A、B的码长2混在一起。

正确的规范分配应该是：先按码长排序，码长短的优先。然后从0开始，每个码字加1，再左移一位给下一个码长。

算法如下：

// 假设码长分布：码长2有2个符号，码长3有2个符号
// 第一步：计算每个码长的起始码字
码长2: 起始码字 = 0
码长3: 起始码字 = (0 + 2) << 1 = 4

// 第二步：分配码字
码长2: 0, 1
码长3: 4, 5

// 二进制表示
码长2: 00, 01
码长3: 100, 101

你看，结果和传统霍夫曼一样。但规范霍夫曼的分配过程是确定的、可预测的。

4.4 实战：嵌入式日志压缩

好了，说点实际的。我在一个基于STM32的工业数据采集器项目里，用霍夫曼压缩日志。设备每天产生约50MB的日志，SD卡很快就满了。而且日志要通过串口上传，速度只有115200bps，50MB要传将近1小时。

我的方案是这样的：

1. 日志格式预处理：把时间戳、日志级别、模块名、消息体分开。时间戳用相对值（增量编码），日志级别和模块名用枚举值。
2. 符号集设计：只对消息体中的ASCII字符编码。控制字符和特殊符号不压缩。
3. 编码选择：用静态霍夫曼。因为日志是分批产生的，每批约1MB，两遍扫描的代价可以接受。
4. 编码表存储：用规范霍夫曼的存储方式，只存码长分布。每批日志的编码表大约占200字节。

核心代码片段：

// 霍夫曼树节点
typedef struct {
    uint16_t symbol;    // 符号值
    uint32_t freq;      // 频率
    int16_t left;       // 左子节点索引
    int16_t right;      // 右子节点索引
    int16_t parent;     // 父节点索引
} huff_node_t;

// 构建霍夫曼树
void huff_build_tree(huff_node_t *nodes, int count) {
    // 每次找两个频率最小的节点合并
    for (int i = count; i < 2 * count - 1; i++) {
        int min1 = -1, min2 = -1;
        uint32_t freq1 = UINT32_MAX, freq2 = UINT32_MAX;
        
        for (int j = 0; j < i; j++) {
            if (nodes[j].parent == -1) {
                if (nodes[j].freq < freq1) {
                    freq2 = freq1; min2 = min1;
                    freq1 = nodes[j].freq; min1 = j;
                } else if (nodes[j].freq < freq2) {
                    freq2 = nodes[j].freq; min2 = j;
                }
            }
        }
        
        // 合并
        nodes[i].freq = freq1 + freq2;
        nodes[i].left = min1;
        nodes[i].right = min2;
        nodes[min1].parent = i;
        nodes[min2].parent = i;
    }
}

实际效果：

指标	压缩前	压缩后	提升
单批日志大小	1.0 MB	0.42 MB	58%
编码表大小	-	218 字节	可忽略
压缩耗时	-	32 ms	可接受
解压耗时	-	18 ms	可接受

4.5 三种霍夫曼对比

特性	静态霍夫曼	动态霍夫曼	规范霍夫曼
扫描次数	2遍	1遍	2遍（基于静态）
编码表存储	需要	不需要	极小（码长分布）
解码速度	中等	慢	快
CPU开销	低	高	低
适用场景	批量数据	流式数据	存储受限系统

你想想看，如果你的系统内存只有几十KB，CPU主频不到100MHz，动态霍夫曼那套频繁更新树的逻辑根本跑不动。静态霍夫曼加规范存储，才是嵌入式领域的正道。

嗯，霍夫曼编码就讲到这里。记住一点：没有最好的算法，只有最合适的方案。选型时把数据特征、硬件资源、实时性要求都列出来，答案自然就有了。