好久没碰底层的东西了前阵子整理代码库翻出一个很有意思的项目基于哈夫曼树的 BMP 图片压缩系统。做这个项目的起因很实际当时手头有一批工业扫描仪输出的 BMP 原图一套产品档案扫下来就是几个 GBNAS 快被塞满了传输更是灾难。市面上主流的压缩软件我当然试过像压缩大师、WinRAR 这类工具也能压 BMP但通用压缩器对位图结构并没有做专门优化压缩率平平无奇而且这种通用打包格式在嵌入式终端上根本解不开。理想方案显然是做一个针对 BMP 的无损压缩系统压缩和解压两端都自己可控于是哈夫曼树成了最稳的选择。这个项目不算大但麻雀虽小五脏俱全从 BMP 文件解析、字节频率统计、哈夫曼树构建到编码表序列化、位流读写、解压回填一条链路全走了一遍。当时开发环境是 Win7 64 位用的纯 C 语言全程没有依赖任何第三方压缩库。这篇就完整复盘一下这个系统的设计与实现把原理、代码、踩过的坑、还有实测数据都摆出来给需要做无损压缩或者刚接触哈夫曼编码的朋友一个可参考的样本。1. 项目拆解BMP 压缩为什么值得专门做一套系统1.1 BMP 的真实应用场景与痛点你可能觉得 BMP 是很古老的格式早该淘汰了。但真不是这样工业上位机、医疗影像采集、仪器截图、很多老旧设备至今只输出 BMP而且常常是 24 位真彩甚至 32 位带 Alpha 通道的大图。这格式最大的问题就是完全不压缩一帧 1920×1200 的 24 位图体积就是 1920×1200×3 字节大约 6.9MB根本不需要高清摄像头随便扫几张就够喝一壶。当时我们这套系统对接的扫描仪单张图普遍在 30MB 到 80MB一天能产生好几百张存储和归档压力非常大。换 JPEG 或者 PNG 行不行业务部门明确要求反差大的线条图、文字稿必须无损绝不允许有损压缩带来的边缘振铃和字符模糊。PNG 虽然是无损的但它在嵌入式板卡上解压速度偏慢而且对二值化线条图的压缩率远没有想象中好。这种情况下自研一个基于哈夫曼树的 BMP 专用压缩系统反而是性价比最高的路线。1.2 为什么是哈夫曼树而不是现成压缩库很多人问既然要无损压缩为什么不直接调 zlib 或者 LZMA理由有三点。第一是可控性。BMP 的像素排列有明确的行对齐规则压缩端可以针对这个规则做预处理把像素字节流按行整理甚至对行首行尾的填充字节做单独处理通用压缩库做不到这种定制。第二是资源占用。嵌入式终端主频低、内存小纯哈夫曼解码只需要一棵树和逐位跳转的指针全状态占用的内存按 KB 算这个数量级在板卡上毫无压力。第三是格式自由度高。压缩后的文件结构完全自己定想怎么打包就怎么打包后续接传输协议也好做只要定好头部格式两边同步升级就行。当然如果只看纯压缩率哈夫曼面对真实的扫描照片通常打不过 LZMA这点我后面会在实测数据里坦诚告诉你。但在这个项目里我们要的不是极限压缩率而是在可控、快速、够用的前提下把 30MB 的图压到能接受的范围哈夫曼树就是那个均衡点。1.3 无损压缩在 BMP 上的可行性判断无损压缩的本质是去掉数据里的统计冗余。BMP 未压缩冗余量非常可观纯色背景大量重复的像素值、文字区域黑白跳变留下的大量 0x00 字节、连续扫描产生的相似灰度值这些都哈夫曼编码的潜在收益来源。我自己在动手前先做了一件事抽取几张典型图做字节频率统计。结果很有意思一张白色背景的文字稿统计下来 0xFF 这个字节值占比超过 60%另外还有大量 0x00、0x0D 之类的低频值一张扫描照片高字节和低字节的组合虽然丰富但整体频率分布明显不均衡。只要有频率差哈夫曼编码就有收益频率差越大收益率越高。这也是为什么哈夫曼树对 BMP 可行、而对某些均匀分布的加密数据完全没有意义的根本原因。2. 哈夫曼树压缩核心原理从字节频率到最优前缀编码2.1 香农信息量为什么出现频率高的要用短码哈夫曼编码的理论根基是信息论核心思想可以一句话说清楚出现频率越高的事件携带的信息量越少所以用越短的二进制码来表示反之则用长码。香农把这种不确定性的度量叫自信息量公式是 -log2(p)频率高的概率值大算出来的比特数就小。放在 BMP 压缩里一个字节的取值范围是 0 到 255。我们把一张图里所有像素字节的取值频率统计出来像素字节频率表就相当于一张概率表。压缩时高频字节比如 0x00 可以只占 1 个二进制位低频字节比如 0xE3 可能占到 10 位以上。长话短说如果平均码长小于 8 位那压缩后位流的总位数就比原始字节流少这就是压缩率的理论来源。2.2 最优前缀编码为什么解码时不会产生歧义哈夫曼编码属于前缀编码意思是任何一个符号的编码都不是另一个符号编码的前缀。这种特性保证了解码时从左到右扫描位流可以唯一确定每段编码对应的原始字节不需要分隔符不需要知道每个符号的边界。举个直观的例子如果 0x00 编码是 00x01 编码是 100x02 编码是 110那收到位流 0110 的时候只能切成 0|110对应 0x00 和 0x02绝不会被切出歧义。这是哈夫曼树天然的结构保证因为每个符号的编码路径都在叶子节点结束没有任何叶子是另一个叶子的祖先。不过工程上有几个需要注意的细节。第一个是叶子到根路径上左右分支谁记 0 谁记 1 会直接影响编码的形态但并不影响压缩率因为每个码字的长度不变。第二个是如果两个节点频率相等先合并哪个会影响树形状微调但同样不影响带权路径长度实践中只要最小堆取出的顺序稳定即可。第三个是我们要处理的符号是字节固定 256 个所以构建树之前可以建立一个 256 的数组避免用哈希表绕弯。2.3 构建哈夫曼树的具体步骤与最小堆优化构建过程本身很简单教科书里写得很清楚我直接说项目里的实际操作。先为频率非零的每个字节值创建一个叶子节点节点里记录字节值和出现频次把这些节点全部放进最小堆。然后循环执行从最小堆里取出频次最小的两个节点合并成一个新节点新节点的频次等于两者之和左孩子放小的那个、右孩子放大的那个再把新节点塞回最小堆。循环直到堆里只剩一个根节点这一棵就是哈夫曼树。最小堆的实现我用的是数组模拟的二叉堆因为节点总数最多 256 个叶子加上 255 个内部节点上限 511 个用动态扩容完全没必要固定开 512 个节点的指针数组就行。入堆和出堆的时间复杂度都是 O(log n)整棵树构建下来也就 O(n log n)n 是有效符号数在 BPP 场景下最多 256构建耗时完全可以忽略。从树生成编码时我习惯用递归做深度优先遍历维护一个当前路径的位数组到叶子节点时把这个字节值、码长、编码位拷贝到编码表里。这个编码表是后面压缩和解压的核心数据结构必须正确序列化进压缩文件里否则解压端拿到位流也还原不出任何数据。3. 系统设计与关键数据结构落地3.1 压缩文件格式设计头部、编码表、位流三段式自研压缩系统有一个非常自由又需要谨慎设计的地方就是压缩文件的组织格式。我在第一版设计里参考了通用压缩包的思路采用三段式结构文件头、编码表、位流。文件头固定 12 字节魔数占 2 字节我用的是 0x484D 对应 ASCII 的 HM 两个字符用于快速识别文件类型和防止错误文件被误解压接下来 4 字节存原始像素数据大小单位是字节再下来 2 字节存编码表有效项数最后 4 字节存压缩位流的总位数。这里关键点是位流总位数必须存因为按字节写入时最后一字节很可能只有几位有效剩下补了 0如果不记录总位数解压时就会把补的 0 当成编码去解码产生多余的输出字节。3.2 编码表如何序列化落盘编码表理论上可以只存树的结构让解压端重建树那样编码表体积稍大而且重建过程费时间。更省事的做法是直接把每个字节值对应的码长和编码位写进文件。我采用的方式是变长记录每个有效符号写入 1 字节的字节值、1 字节的码长然后按位写入编码本身。编码按高位在前的方式逐一写成位流。最坏情况下 256 个符号全有效码长最大可能接近几百位但 BMP 场景下一个码长超过 24 位的符号非常少见而且越长的码对应的频率一定越低。因此表体量通常在 500 到 1500 字节左右而这个表本身也会占据压缩文件的一部分体积。必须说明的是对很小的文件编码表可能比像素数据还大这是哈夫曼压缩的经典问题我会在常见问题里专门讲。3.3 BMP 像素数据提取与行对齐处理BMP 的像素区域不是简单地把每个像素按依次排列就能得到实际文件中每行的字节数必须按 4 字节对齐这个规则叫行字节数计算公式((宽×位深31)/32)×4。举个例子一张宽 100 像素的 24 位 BMP理论行字节数应该是 300而 300 除以 4 会得到 75刚好整除所以这一行没有填充字节但如果宽是 101理论行字节数是 303按公式算出来的 row_size 就是 304每一行末尾都要填 1 个无意义字节。这些填充字节在压缩前必须保留并参与频率统计因为解压后要原样还原 BMP缺一个字节都会导致整张图错位。提取像素数据的代码我写成独立函数读文件头后定位像素偏移然后按行读取 row_size 字节逐行往紧凑缓冲区里追加。如果 BMP 是上下颠倒存储的也就是高度为负值解析时要先按绝对值确定真实高度否则循环边界会出错。4. 压缩与解压实操流程全记录4.1 压缩端完整流程与核心代码压缩端分五个阶段我可以直接给出最核心的伪代码配合 C 语言实现片段。第一阶段解析 BMP拿到像素数据和宽度高度第二阶段统计频次并构建哈夫曼树第三阶段生成编码表第四阶段写压缩文件头部和编码表第五阶段逐字节编码像素数据写入位流。先看 BMP 结构体的定义和解析片段typedef struct { uint16_t bfType; // 固定 0x4D42即 BM uint32_t bfSize; // BMP 文件总大小 uint32_t bfOffBits; // 像素数据偏移量 uint32_t biWidth; // 图像宽度 int32_t biHeight; // 图像高度负数表示倒序存储 uint16_t biBitCount; // 位深度24 或 32 uint32_t biSizeImage; // 像素数据大小行对齐后 uint8_t *pixelData; // 像素数据缓冲区 uint32_t rowSize; // 每行字节数 } BMPImage; BMPImage* parse_bmp(uint8_t *fileBuf, uint32_t fileSize) { BMPImage *img calloc(1, sizeof(BMPImage)); memcpy(img-bfType, fileBuf, 2); if (img-bfType ! 0x4D42) return NULL; memcpy(img-bfSize, fileBuf 2, 4); memcpy(img-bfOffBits, fileBuf 10, 4); memcpy(img-biWidth, fileBuf 18, 4); memcpy(img-biHeight, fileBuf 22, 4); memcpy(img-biBitCount, fileBuf 28, 2); int channels img-biBitCount / 8; img-rowSize ((img-biWidth * img-biBitCount 31) / 32) * 4; uint32_t height abs(img-biHeight); img-biSizeImage img-rowSize * height; img-pixelData malloc(img-biSizeImage); memcpy(img-pixelData, fileBuf img-bfOffBits, img-biSizeImage); return img; }注意解析 BMP 时我没有一次性把整个文件读入内存而是用 read 函数分段读。因为大 BMP 动辄几十 MB一次性读入内存虽然简单但嵌入式平台经常撑不起分段读取更稳。上面的代码为了篇幅做了简化实际项目里是边读边校验边界防止文件被截断导致越界读写。然后是统计频次并构建树的代码片段int freq[256] {0}; for (uint32_t i 0; i img-biSizeImage; i) { freq[img-pixelData[i]]; }统计完成后只有 freq 大于 0 的字节值为有效符号。如果有效符号只有 1 种那么整张图全是同一个字节值哈夫曼树退化成单节点编码只有 0 一位。这个边界情况我在测试时才遇到必须单独处理否则构建树的循环会出错。写压缩文件的头信息和编码表时我定义了一个简单的写入函数。位流写入是比较容易出错的地方这里给一个自用的位缓冲写入器typedef struct { FILE *fp; uint8_t buf; int bitCount; } BitWriter; void write_bit(BitWriter *bw, uint8_t bit) { if (bit) bw-buf | (1 (7 - bw-bitCount)); if (bw-bitCount 8) { fputc(bw-buf, bw-fp); bw-buf 0; bw-bitCount 0; } }这个写位过程是逐位调用压缩时每写入一个符号编码就循环把每一位交给这个函数。最后一字节不足 8 位时buf 里剩余的高位是 0等到收尾时如果 bitCount 不为 0就把这个不完整的字节写出去并把最终总位数记录在文件头。4.2 解压端流程与关键细节解压比压缩麻烦一点。压缩时我们有完整的频次信息和编码表解压时什么都得从文件里读回来。解压流程是先读 12 字节文件头校验魔数再读编码表项数、原始数据大小、位流总位数然后根据编码表重建哈夫曼树或者直接根据码长和码字重建一个字典最后逐位读取压缩位流从树根开始走走到叶子就输出一个字节输出到指定数量后停止。从编码表重建树的代码HNode* rebuild_tree(EncodedSymbol table[], int count) { HNode *root malloc(sizeof(HNode)); root-left root-right NULL; root-isLeaf 0; for (int i 0; i count; i) { HNode *cur root; for (int b 0; b table[i].codeLen; b) { int bit (table[i].code[b / 8] (7 - (b % 8))) 1; if (bit 0) { if (!cur-left) { cur-left malloc_zero_node(); } cur cur-left; } else { if (!cur-right) { cur-right malloc_zero_node(); } cur cur-right; } } cur-isLeaf 1; cur-data table[i].byteValue; } return root; }解码时最需要注意的边界条件是最后那个填充字节。位流总位数知道后解码循环只要精确执行 totalBits 次即可多读一位都可能在文件末尾产生多余的符号。我在第一版因为没有存总位数解压测试时图片末尾总是多出一两个像素的杂色排查了好久才发现是补零位被当成了有效位这个问题严重到可以独立写成一条避坑要点。4.3 实测压缩率数据与结论我拿三组图做了实测硬件就是那台 Win7 工控机纯 C 编译优化开 O2。第一组是白底文字稿1024×768 的 24 位 BMP原始大小 2.36MB。第二组是扫描灰度照片同样 1024×768原始大小 2.36MB。第三组是深度设备的 32 位带透明通道截图1600×900原始大小 5.49MB。实测结果如下表所示测试样本原始大小压缩后大小压缩率压缩耗时解压耗时白底文字稿2.36MB1.12MB47.5%约280ms约310ms灰度扫描照片2.36MB1.98MB83.9%约270ms约300ms32位透明截图5.49MB3.41MB62.1%约690ms约720ms白底文字稿压缩率最漂亮原因就是前面说的频率极不均衡大量 0xFF 和 0x00 拿到短码。灰度照片像素字节分布宽每个值都有一定占比码长下不去压缩率就差很多。透明截图因为多了 Alpha 通道很多像素的 Alpha 固定为 255拉低了整体熵所以又比灰度照片好。这个表很好地印证了一个结论哈夫曼压缩率完全取决于数据的频率分布是否集中而 BMP 里大块纯色和重复像素恰恰提供了这种集中度。5. 常见问题与踩坑实录5.1 小文件越压越大的坑这是哈夫曼编码最容易让人测试翻车的地方。一个小 BMP 可能是几十 KB 到一两百 KB里面有效符号可能也就十几种频率统计和树构建都没问题但压缩文件头部 12 字节、编码表几百字节加在一起估算就发现压出来的体积比原文件还大。原因很简单哈夫曼压缩的收益来自平均码长从 8 位降到更低位收益需要足够多的数据量来摊销头部和编码表的固定开销。如果原文件只有 10KB编码表 600 字节那就是 6% 的开销很可能把压缩收益全部吃掉。我的处理方式是加了一个策略判断编码完所有像素数据后计算压缩后总大小如果小于原始像素区域大小就输出压缩文件如果大于等于就直接标记一个未压缩标志把原始像素数据原样拷到文件尾部。这样既不会放大文件又能保证统一的后缀名和解压入口解压时碰到未压缩标志就直接拷贝输出。实测中这种方式对小文件非常实用。5.2 位流边界与补零问题位流边界问题在前面提过但值得单独强调因为它属于那种一秒钟看不出来、排查要好几小时的隐蔽 Bug。压缩位流按字节写最后一字节不足 8 位时补 0。如果解压时不知道总位数补的 0 就会参与解码结果是在还原出来的图像末尾多出几个像素或几个字节。由于 BMP 是按行对齐的多出来的数据会造成整张图最后几行错色、错位看起来特别像像素偏移问题。解法就是在文件头保存压缩位流的总位数解压循环严格按这个数来遍历。另外还有一个细节解码循环里到达叶子节点输出字节后要把游标重新指向根节点继续处理下一位。如果位流中途出现无法到达叶子的情况也就是目标分支不存在那说明文件损坏或者编码表有问题此时应立刻报错而不是强行继续避免产生一堆错误数据。5.3 解压速度慢的根因与优化空间纯哈夫曼树解压每个字节都要从根节点往下跳平均 5 到 10 次100MB 像素数据解压就要跳几千几万次节点虽然节点操作本身极快但指令浪费在指针追踪和分支跳转上整体性能上不了很大但优化空间很小。我在项目里做了一次优化把树节点用数组存储每个节点只存左右孩子索引替换掉原来的指针结构这样能减少 malloc 的开销并提高缓存命中率。数组存储对嵌入式环境也更友好回收内存时只需要 free 一次。如果追求更快的解码可以转而实现规范哈夫曼编码解码时用一张固定大小的查找表按位查表速度会成倍提升但复杂度也相应上去了。这个优化可以在后续版本里逐步补上。5.4 编码表重建时的一个细节叶子节点重复覆盖重建树的时候如果两个有效符号具有不同的编码前缀它们在树上的路径不会重合到叶子所以理论上不存在叶子重复覆盖。但如果编码表从文件读回时出错或者文件被截断很可能一个中间节点被误设为叶子节点后续另一个符号又经过这个节点往下挂导致整棵树结构错乱。解压时表现就是还原出来的图像一部分正常、一部分乱码且乱码位置没有明显规律。我加了一个防御性检查在重建树的循环里如果当前节点已经标记为叶子又出现新的编码需要往下走直接返回编码表错误拒绝继续解压。这个检查没有额外开销还能在第一时间识别损坏的压缩文件算是性价比很高的一道防护。6. 后续扩展方向与个人心得项目做到这里功能上已经闭环了但说实话哈夫曼树对 BMP 这种格式只是基础手段后面完全可以再加一层优化。最简单的扩展是差分编码对同一行的相邻像素求差值再对差值做哈夫曼编码因为扫描图像的相邻像素差值通常集中在小范围值这样做可以把灰度照片的压缩率从 83.9% 提到 60% 左右。另一个方向是游程编码和哈夫曼编码的混合压缩对大块连续同色区域先做 RLE 统计再对统计结果做哈夫曼对那种颜色块特别多的工程图纸非常有效。如果要把压缩系统用在批量归档场景还可以在编码表序列化阶段引入定长码表合并把多个文件的编码表汇总成公共表进一步压缩表头开销。解码端如果用数组型节点和规范哈夫曼编码解压性能还有一次显著的提升空间。最后说一点个人体会。哈夫曼树看起来是大学数据结构课上的基础题真正落地到 BMP 压缩系统里才体会到基础和工程之间隔着多少细节。文件格式设计时要考虑编码表体积和位流边界解析 BMP 时要处理行对齐和倒序存储写入位流时任何一个粗心都会导致文件损坏。这些细节没有人会在教科书里告诉你但恰恰是它们决定了一个压缩系统能不能真正用在生产环境里。如果你也想实现一个类似的系统我的建议是先把 BMP 解析和位流读写做扎实再考虑优化压缩率前面地基不稳后面的一切都白搭。