简介这是一份基于C语言实现的LZW压缩算法源码面向学习数据压缩原理、希望掌握经典压缩算法代码实现的学生与开发者。LZW是一种基于动态字典匹配的无损压缩算法早期在GIF等图像格式中广泛使用源码覆盖编码、解码、字典构建与更新、内存管理及边界条件处理等完整流程并将核心逻辑拆分为多个模块便于对照学习。压缩包共14个文件包括8个C源文件、5个头文件和1个Makefile整体仅12KBC源文件按压缩、解压、数据结构等职责划分头文件声明接口Makefile可快速构建示例程序。目前已有311人学习下载。通过阅读和运行这份源码读者可以掌握Hash表管理字典、最长前缀匹配、位级编码等关键技巧同时学会在C语言中设计可扩展的压缩算法骨架为后续优化、移植其他算法或完成课程设计提供基础。1. LZW 压缩算法与 C 语言源码这东西到底能拿来干什么很多人第一次接触 LZW是在《数据压缩》课本或者某次面试题里。课本会告诉你它是无损压缩、基于字典、Unix 的 compress 命令用过它然后就没有然后了。但真正常年写 C 的人碰到 LZW 的机会其实比想象中多嵌入式设备里要压缩配置字、遥测数据上位机要把采集数据压缩后通过串口传出去老协议栈里要解一个历史遗留的 .Z 文件。这时候你脑子里如果只有一个模糊的字典概念动手写起来会非常痛苦。LZW 的全称是 Lempel-Ziv-Welch它的核心思路一句话能说清用变长的编码去代替重复出现的字符串编码表在压缩和解压过程中动态生成不需要预先传输字典。这篇文章就围绕“LZW、C语言、压缩算法、源码”这四个关键词展开从定长编码的坑讲到底层位操作的写法再给你一份可以直接抄的 C 语言实现、参数怎么调、以及最容易让新手翻车的几个边界问题。读完你可以照着代码在本地跑通也能看懂网上各种版本之间为什么行为不一致。2. LZW 的核心机制字典自举与定长编码的取舍2.1 LZW 为什么不需要传输字典编码和解码同时建表LZW 的字典不是预先定义好的而是压缩和解压两边各自动态生成的。压缩端维护一个“当前前缀”每次读入一个新字符把“前缀字符”去字典里查查到了就继续累加查不到就把当前前缀的编码输出同时把这个新组合加入字典。解压端完全对称它看到的是一个编码流把每个编码翻译回字符串同时也在同一个位置建立同样的字典条目。这件事听起来简单但第一次写的人几乎都会困惑一个问题字典条目是在输出编码之后才加入的那解压端读到某个编码时这个编码对应的字符串到底存在吗答案是存在因为压缩端输出的编码总是“已经存在于字典中的那个前缀的编码”而这个前缀是上个循环结束时刚生成的新条目。换句话说字典的增长严格滞后于输出但解压端重建的时候也严格滞后同样多两边始终保持同步。C 语言实现时最直观的做法是用一个二维数组当作字典dict[code][len]存字符串dict_len[code]存长度。这种写法可读性最高但性能一般。另一种做法是用哈希表把“前缀编码 字符”映射到新编码查表速度快但代码复杂度上了一个台阶。我一般建议第一版先用二维数组跑通确认逻辑正确后再换哈希表因为 LZW 的调错难点在字典同步不在数据结构本身。2.2 定长编码输出带来的压缩率边界LZW 输出的码字不是固定 8 位或者 16 位而是一个动态增长的编码长度。最常见的方案是字典初始有 256 个条目对应 0~255 的单字节字符第一个新条目从 256 开始编号。9 位编码能表示 0~511所以当字典条目数达到 512 时编码宽度要升到 10 位达到 1024 时升到 11 位达到 2048 时升到 12 位。Unix compress 和 GIF 的老实现都停在 12 位即字典最大 4096 个条目超过以后有两条路清空字典重新建表或者冻结字典不再增长。这里有一个新手最容易理解错的点编码宽度决定了输出的位流怎么切。如果你的压缩输出是 9 位编码你不能再按字节去写文件必须先把 9 位的码字按位拼接。这意味着你要自己维护一个“位缓冲”凑满 8 位才写一个字节。很多人第一次跑通逻辑打印出来却是乱码就是因为没有处理好位流的拼接顺序。下面第 3 章给出的代码就把这一层单独抽出来处理。2.3 清空字典还是冻结字典两种策略的适用场景当字典满了LZW 有两种常见的续命策略。第一种是清空字典把编码宽度重置为 9 位重新开始建表。这种策略适合数据局部性强的情况——文件不同区域有各自的重复模式重新建表能让新区域的重复串更快进入字典。第二种是冻结字典不再加入新条目但已有的编码继续用。适合数据整体模式稳定、后续新字符串价值不大的情况。从压缩率看清空字典通常更优但会引入一个标记问题解压端必须知道“字典清了宽度要重置了”。Unix compress 在输出流里写入一个专门的清空码Clear Code来解决。GIF 也类似。如果你只是自己封装数据格式可以在压缩数据头部写一个标志位或者在字典满时直接输出一个约定好的特殊编码。我一般选清空策略因为 C 语言里重置一张表比维护一个冻结状态更省事而且对大多数实测数据压缩率更好。3. 照着写的 C 语言压缩源码核心数据结构与位流输出3.1 最小可运行的 LZW 压缩端实现下面这份代码是压缩端的核心骨架用二维数组做字典按 9~12 位动态增宽满 4096 条后清空重建。为了篇幅清晰省去了文件读写封装只保留 encode 主流程和位写入函数。#include stdio.h #include string.h #include stdlib.h #define MAX_DICT 4096 #define MAX_STRLEN 4096 // 字典条目用一个 char 数组存字符串len 记录长度 char dict[MAX_DICT][MAX_STRLEN]; int dict_len[MAX_DICT]; int next_code; // 下一个可用编码 int cur_bit; // 当前编码位数从 9 开始 FILE *out_file; unsigned char bit_buf; int bit_count; void write_bits(int code, int width) { // 把 width 位的编码依次拼到 bit_buf满 8 位写一个字节 for (int i width - 1; i 0; i--) { bit_buf (bit_buf 1) | ((code i) 1); bit_count; if (bit_count 8) { fputc(bit_buf, out_file); bit_buf 0; bit_count 0; } } } void reset_dict() { next_code 256; // 0~255 保留给单字符 cur_bit 9; memset(dict_len, 0, sizeof(dict_len)); // 为单字符初始化 256 条 for (int i 0; i 256; i) { dict_len[i] 1; dict[i][0] (char)i; } } int find_dict(int prefix, unsigned char ch) { // 在已有条目里查找 prefix ch 组成的字符串 int target_len dict_len[prefix] 1; char *target (char*)malloc(target_len 1); memcpy(target, dict[prefix], dict_len[prefix]); target[dict_len[prefix]] (char)ch; target[target_len] \0; for (int i 0; i next_code; i) { if (dict_len[i] target_len memcmp(dict[i], target, target_len) 0) { free(target); return i; } } free(target); return -1; } void lzw_compress(FILE *in, FILE *out) { out_file out; bit_buf 0; bit_count 0; reset_dict(); int prefix fgetc(in); // 第一个字节作为初始前缀 if (prefix EOF) return; unsigned char ch; while ((ch fgetc(in)) ! EOF) { int idx find_dict(prefix, ch); if (idx ! -1) { prefix idx; // 前缀变长继续尝试加长 } else { write_bits(prefix, cur_bit); // 加入新条目 memcpy(dict[next_code], dict[prefix], dict_len[prefix]); dict[next_code][dict_len[prefix]] (char)ch; dict_len[next_code] dict_len[prefix] 1; next_code; // 编码宽度需要增加时加宽 if (next_code (1 cur_bit) - 1 cur_bit 12) { cur_bit; } // 字典满了清空重建 if (next_code MAX_DICT) { reset_dict(); } prefix ch; } } // 输出最后一个前缀 if (next_code (1 cur_bit) - 1 cur_bit 12) { cur_bit; } write_bits(prefix, cur_bit); // 把位缓冲里剩余字节刷出去 if (bit_count 0) { bit_buf (8 - bit_count); fputc(bit_buf, out_file); } }这段代码背后有几个关键设定需要你理解否则你改参数会改错地方。find_dict用的是线性扫描复杂度是 O(字典条目数 × 字符串长度)在 4096 个条目下不慢但如果你把 MAX_DICT 调大这里就会成为性能瓶颈。代码里每次查找都 malloc 一个临时串这也是教学版为了方便付出的代价正式工程里应该直接用prefix的地址和长度去比较避免反复分配释放。write_bits是从高位到低位逐位输出这样做的好处是解压端可以按同样顺序逐位读取不用考虑跨字节的奇偶问题。GIF 也是类似思路只是它在 LZW 之前多了一个字节序变换层这也是为什么很多 GIF 解码器里要单独处理 lsb 和 msb 的区别。字典加入新条目的时机在输出当前前缀之后这是 LZW 最微妙的地方。解压端看到编码后先输出编码对应的字符串然后再把“上一个输出 当前输出的第一个字符”加入自己的字典。两个动作严格对称压缩端才能在解压端建出同样的字典。3.2 配套的解压端核心逻辑压缩端好写解压端才是真正容易踩坑的地方因为解压端是被动重建字典它看到的编码顺序就是压缩端输出的顺序但字典条目的内容要靠解码结果来推导。char dict_dec[MAX_DICT][MAX_STRLEN]; int dict_dec_len[MAX_DICT]; int next_code; int cur_bit; unsigned int read_bits(FILE *in, int width) { static unsigned int bit_buf 0; static int bit_count 0; while (bit_count width) { bit_buf (bit_buf 8) | fgetc(in); bit_count 8; } unsigned int val (bit_buf (bit_count - width)) ((1 width) - 1); bit_count - width; return val; } void reset_dec_dict() { next_code 256; cur_bit 9; for (int i 0; i 256; i) { dict_dec_len[i] 1; dict_dec[i][0] (char)i; } } void lzw_decompress(FILE *in, FILE *out) { reset_dec_dict(); int prev read_bits(in, cur_bit); if (prev EOF) return; fwrite(dict_dec[prev], 1, dict_dec_len[prev], out); int curr; while ((curr read_bits(in, cur_bit)) ! EOF) { char *entry; int entry_len; if (curr next_code) { entry dict_dec[curr]; entry_len dict_dec_len[curr]; } else { // 特殊情况curr 正好等于 next_code说明是刚加入的条目 // 这个条目 dict[prev] dict[prev][0] entry (char*)malloc(dict_dec_len[prev] 1); memcpy(entry, dict_dec[prev], dict_dec_len[prev]); entry[dict_dec_len[prev]] dict_dec[prev][0]; entry_len dict_dec_len[prev] 1; } fwrite(entry, 1, entry_len, out); // 将 prev entry[0] 加入字典 dict_dec_len[next_code] dict_dec_len[prev] 1; memcpy(dict_dec[next_code], dict_dec[prev], dict_dec_len[prev]); dict_dec[next_code][dict_dec_len[prev]] entry[0]; next_code; if (next_code (1 cur_bit) - 1 cur_bit 12) { cur_bit; } if (next_code MAX_DICT) { reset_dec_dict(); } prev curr; if (curr next_code - 1) free(entry); // 临时 malloc 的要释放 } }这段代码里最值得注意的就是curr next_code的分支也就是教材上说的“特殊情形”。这个情况只会在解压端出现压缩端输出了某个前缀编码后又立即输出了刚刚新建的那个条目。对于解压端它读到的新编码大于当前字典里已有条目的最大编号但根据 LZW 的同步规则这个新条目一定等于“上一输出字符串 上一输出字符串的第一个字符”。这个特殊分支写错的话解压出来的文件中间会少一个字符或者多一个字符而且不会报错——损坏是静默的。我用一个简单办法验证压缩一个 1 万字符的英文文本解压回来用cmp对比如果中间出现一个字符的偏移错误十有八九是这个分支没写对。3.3 位宽切换的时机问题压缩端next_code (1 cur_bit) - 1这件事必须发生在写入下一个编码之前。换句话说编码宽度只影响后续输出的编码位数不影响已经输出的位流。解压端也是一样读编码时先按当前cur_bit读读完后判断next_code是否要加宽然后下一次读再按新的宽度。这里最常见的翻车是把next_code 512写成next_code 512。前者意思是 512 号编码已经开始用了所以要换成 10 位后者则晚了一个编码解压端会在一个编码宽度上连续错位。因为位流是逐位拼接的一个编码的宽窄错误会让后面所有编码全部错位诊断结果就是解压出来全是乱码但你没有报错。排查这种问题建议手动构造一个很小的输入打印每一步的编码和字典条目号肉眼就能看出在第几个编码后宽度变了。4. C 语言调用 LZW 的工程封装从文件到内存的常用姿势4.1 直接压缩文件到文件的调用范式拿到前面的核心代码你还需要一个入口函数把FILE*接起来。常见的工程形态是命令行工具compress input output。这里给出一个极简封装包含打开文件、调用压缩、关闭、以及一个粗糙的压缩比统计。int compress_file(const char *in_path, const char *out_path) { FILE *in fopen(in_path, rb); if (!in) { perror(open input); return -1; } FILE *out fopen(out_path, wb); if (!out) { perror(open output); fclose(in); return -1; } long start ftell(in); fseek(in, 0, SEEK_END); long in_size ftell(in); fseek(in, 0, SEEK_SET); lzw_compress(in, out); long out_size ftell(out); printf(input%ld, output%ld, ratio%.2f%%\n, in_size, out_size, (double)out_size / in_size * 100); fclose(in); fclose(out); return 0; }注意上面这段代码里 ftell 在 Windows 二进制模式下如果文件很大可能超过 long 范围实际工程里建议用_ftelli64或fseeko64。而且在 Linux 上long是 64 位没问题但 Windows 上的long还是 32 位。这个坑很多移植代码都会踩到。4.2 内存到内存的 LZW不落盘的场景文件压缩是最常见的使用方式但真实开发里还有另一个高频场景把一段内存里的数据压缩成另一段内存。比如嵌入式场景数据在 RAM 里压缩完直接塞进通信缓冲区。你再开临时文件就太蠢了。实现上只需要把FILE*换成内存缓冲区的读写接口核心 LZW 逻辑完全不动。typedef struct { unsigned char *buf; size_t len; size_t cap; size_t pos; } mem_stream; int mem_write_byte(mem_stream *ms, unsigned char b) { if (ms-pos ms-cap) { ms-cap ms-cap ? ms-cap * 2 : 1024; ms-buf realloc(ms-buf, ms-cap); } ms-buf[ms-pos] b; return 0; } int mem_read_byte(mem_stream *ms) { if (ms-pos ms-len) return EOF; return ms-buf[ms-pos]; }把 lzw_compress 里的fgetc与fputc换成这两种接口就好其余逻辑一行不用改。我的经验是先做成文件版跑通再改内存版因为文件版方便用系统 diff 工具验证内存版出了问题不好定位。4.3 多平台移植时的字节序处理LZW 输出的位流严格来说是自己定义的字节序。你在 x86 小端机器上压缩出来的文件换到 ARM 大端机器上解压如果不做任何处理必须确保读位和写位的顺序完全一致。前面的write_bits是从高位到低位逐位操作read_bits也是从高位开始读两边只要都按这个约定跟机器的内存字节序就没有关系。真正的坑来自你把 LZW 数据嵌入到另一种容器格式里。比如你压缩出一个.lzw文件然后又想在这个文件前面加个 4 字节的长度头。如果你用memcpy把长度直接拷到头部在小端机器上写出 01 00 00 00在大端机器上写出 00 00 00 01解压端如果不一致就废了。所以工程里所有跨端格式的长度字段我都手动按字节序拼接绝不依赖本机字节序。5. LZW 源码调试避坑现象、原因与解决5.1 解压结果前几个字节正确后面全部乱码这是最常见的故障现象。现象压缩再解压回来的文件开头 10 个字节对后面全是乱码。原因位宽切换时机不对。压缩端在输出某个编码前已经切换了位数解压端却在读下一个编码后才切换。两个端的位流从此偏差一个编码宽度。解决在压缩端write_bits前打印当前cur_bit和next_code解压端同样打印。对比第几个编码开始两侧的位数不同。通常问题出在next_code (1 cur_bit) - 1这个条件上把和的差异找出来改对齐就行。5.2 压缩后比原文件还大压缩率超过 100%现象对小文件压缩后输出比输入大 30%~50%。原因LZW 在数据量小于字典容量时每个编码至少 9 位而原始数据每个字节 8 位两者差了 12.5%。再加上位缓冲尾部对齐可能补几个零小文件大概率压缩后变大。解决这不是 bug是算法特性。工程上可以做两件事一是设定一个阈值比如小于 256 字节的文件直接原样存储头部用标志位区分二是先检查输入数据里重复模式是否足够多再决定是否值得压缩。我一般在实际项目中加一个“压缩后大小 原大小则存原数据”的回退逻辑虽然多占一个标志位但能避免用户在压缩小文件时怀疑程序写错了。5.3 字典清空后解压端没有同步清空现象压缩和解压都正常但跑到文件后半段解压出现乱码。原因压缩端在字典满 4096 时调用了reset_dict()但解压端没在同样位置清空。两边字典从此不同步后面的所有编码都翻译错。解决在压缩端的压缩输出流里加入一个自定义的“清空标记”编码比如把 255 之前某个保留值定义为清空命令。要让压缩端在next_code MAX_DICT时先输出这个标记再reset_dict()解压端读到一个标记时也执行reset_dec_dict()。如果不想增加标记复杂度也可以在压缩格式头部写一个“压缩模式”字段用固定字典大小 4096、固定宽度 12 位来规避清空问题——也就是只让字典满后冻结不再清空。代价是压缩率对大文件稍差收益是代码简单很多。5.4 读位流的 EOF 判断错误导致尾部数据丢失现象大文件压缩后解压最后一行数据丢失或不完整。原因在read_bits循环里用fgetc读到EOF时可能当前bit_buf里还残留有效数据但你直接跳出了循环。解决不要在read_bits内部遇到 EOF 就立即返回 EOF而是先把bit_buf里不足 8 位的剩余位取完再返回EOF。或者更安全的方式压缩端写入一个文件结束编码EOF code解压端读到这个编码才停止。具体做法是在字典里约定一个保留编码比如0xFFF4095压缩端在写完最后一个实际编码后输出这个 EOF 编码解压端读到它就知道整个流结束然后把bit_buf里剩下的位全部丢弃。5.5 特殊情形curr next_code的处理分支跑不到现象测试文件都比较短特殊情形分支从未执行你以为代码没问题等跑到大数据就炸。原因特殊情形在短文件中出现的概率极低如果数据太规整压缩端很少出现“刚加入新条目后立即再次引用它”的情况。解决不要依赖运气。强制构造测试用例压缩一段重复性很高的文本比如连续 10000 个同样字符这种数据很容易触发特殊分支。另外也可以在所有测试完成后单独打印特殊分支执行次数确认它不是零。这算是我调 LZW 的保留习惯因为它不报错你根本不知道它有没有被覆盖。5.6 内存泄漏与乱七八糟的 malloc现象压缩大文件内存占用不断上升最后程序崩溃或被杀。原因find_dict里用 malloc 创建临时字符串每次查找都分配不释放特殊分支里临时 malloc 的字符串也没有在循环尾部释放。解决统一改为栈上的固定缓冲数组或者在每次循环结束前统一释放临时资源。更彻底的做法是重构find_dict直接拿dict[prefix]的地址和dict_len[prefix]去比较不复制任何字符串。这样既省内存又省时间。6. 从源码到可用验证 LZW 实现正确性的三条路径6.1 用已知数据生成对比指纹拿到一段实现后第一步不是在项目里直接集成而是先做无损闭环验证。我习惯用三组数据做回归纯文本典型高重复率、二进制可执行文件低重复率、全零字节流极端重复率。对每组数据分别跑压缩和解压用cmp或memcmp确认输出和输入完全一致。如果压缩率想有个基准参照可以在 Linux 上用系统的compress命令如果有历史包或gzip做侧面参考。LZW 和 gzip 的压缩率本来就不一样不能用 gzip 的压缩率来验收你的 LZW但你至少能确认自己的压缩率没有出现明显形状异常——比如文本压缩率在 40%~60%二进制在 80%~95%全零在接近 0.1% 以下这些是大致合理的区间。提示全零流的压缩率测试最容易暴露位宽切换和字典清空的问题因为它会让字典瞬间塞满触发所有边界分支。6.2 字典命中率与压缩率的工程级可视化只是压缩率正确还不够工程上你还想知道“字典够不够大”。我给自己的实现加过一个统计功能记录每次find_dict是找到了还是没找到输出一个命中率。当命中率稳定在 95% 以上说明当前数据规律已经充分被字典吸收如果命中率长时间低于 80%说明数据局部性强、字典频繁重建此时可以考虑增大 MAX_DICT 或调整清空策略。// 伪代码示意 int hit_count 0, miss_count 0; int idx find_dict(prefix, ch); if (idx ! -1) { hit_count; } else { miss_count; } // 在程序退出前打印统计 printf(hit%d miss%d rate%.2f%%\n, hit_count, miss_count, 100.0 * hit_count / (hit_count miss_count));这个统计不属于 LZW 的核心逻辑但它是判断调参方向最直接的工具。很多人拿到源码后第一件事是调字典大小却不知道自己是该调大还是该调小有了命中率数据就不用拍脑袋。6.3 边界测试用例清单我整理了一个固定的边界测试清单每次改完代码都会跑一遍再提交。这不是完整的单元测试但覆盖面足够把 LZW 常见的实现缺陷暴露出来。空文件压缩端直接返回不产生任何输出。解压端拿到 0 字节输入也不能崩溃。单字节文件压缩后多出若干填充位解压后必须还原为一个字节。这个小场景测的是位缓冲的收尾逻辑。正好 256 字节且全是重复字符压缩过程中字典会快速增长可能触发位宽从 9 升 10。重点观察宽度切换那几字节是否正确。整段随机数据压缩率会比原文略高因为 LZW 对随机数据几乎没有压缩能力。需要确认解压仍 100% 还原且程序不因为字典满而崩溃。超长重复模式比如连续 20000 个abcabcabc...这会触发字典清空和重建验证两端清空同步逻辑。这套清单我前后用了很久每次改数据结构或输出格式都能在几分钟内验证出哪里坏了。6.4 从固定 12 位到动态宽度一个值得尝试的优化方向如果你不想一直停留在原始 LZW 的实现上有一个成本很低的优化把编码宽度从固定的 12 位改为“从 9 位开始按需升到 10、11、12”这就是前面代码已经实现的动态宽度方案。相比全程 12 位输出的老版本动态宽度在小文件上能省掉大量填充位对大文件前期也有可观收益。再进一步你可以尝试把起始位宽从 9 改为 8。因为单字符字典只需要 256 个条目第 256~511 之间的编码可以用 8 位表示但 8 位最多到 255如果你从 256 编码开始算8 位表示不了。所以只能从 9 位起。如果你自定义一个保留位或者偏移量可以把起始位宽压到 8但解压端要做额外换算复杂度不值。我在这类压缩算法上的习惯是先用最原始的定宽实现把传输和解压流程打通再逐步换成动态宽度。因为定宽版本更容易在逻辑上做二分定位动态宽度一旦出错你很难分清是位流问题还是宽度切换问题。等两边的环都闭合了再去做性能优化或者参数调节。最后说一句私人的习惯每次写完一个 LZW 版本我都要用全零字节流和一段真实的 JSON 配置文本做回归前者卡边界后者贴近真实数据。这两个用例通过基本就敢往项目里放了。希望帮到你。本文还有配套的精品资源点击获取