LZW无损压缩算法原理与C++实现解析：从GIF到嵌入式场景

前阵子接了个老文件格式的兼容解析Demo，翻到格式文档，里面写着“数据段使用LZW编解码算法压缩”。LZW这个名字，现在一提压缩场景基本没人会主动选它，大家默认zlib或者zstd，但我偏偏躲不开——GIF、TIFF、Unix compress、早期PostScript都曾经用它。如果你也在处理老数据格式、游戏资源包或者嵌入式场景里的小体积压缩模块，这篇LZW的完整原理和C++实现思路应该能帮你少走不少弯路。

我尽量不堆数学公式，目标是让只有基础C++经验的人也能照着把编解码器写出来，并且搞清楚那些“看代码能跑，一换数据就崩”的边界问题。

1. 从LZ78说起：LZW在无损压缩家族中的位置

1.1 滑动窗口与字典表：LZ77与LZ78的思路分野

无损压缩的核心说白了就一句话：找出重复的东西，让重复的东西只记一次。但这句“只记一次”怎么落地，衍生出了两个方向。

LZ77走的是滑动窗口路线。它会在已经输出的字节流里找当前内容的匹配片段，然后输出一个“往前走多少距离、复制多少长度”的指针。这就像写论文时引用文献，不把原话抄一遍，而是写“见第X页第Y行”。它的优点是窗口内的重复能精确命中，缺点是指针本身也有开销，而且窗口大小有上限。

LZ78走的是字典表路线。它把遇到过的字符串登记到一张表里，每个字符串分配一个编号，下次再遇到整个字符串时，只输出编号。这更像是自建术语表：第一次遇到“自动驾驶系统”时写全称，之后统一用“系统A”代替。LZW就是LZ78里最出名的变体。

LZW相比LZ78最大的改进是：它不输出“字典位置+新字符”这种二元结构，而是把所有可扩展的字符串都映射成一个码字。编码端只在匹配失败时输出，生成的新字典项天然就是“前缀字符串+新字符”，解码端能靠同样的节奏恢复出整张表。

1.2 LZW真正落地的地方：GIF、TIFF与老数据格式

LZW能在今天还被人反复提起来，很大程度上是因为GIF。GIF图片在发布时用LZW压缩过调色板索引数据，这让GIF在小尺寸图像上压缩率相当不错。TIFF文件格式也把LZW作为标配压缩选项之一，老一点的扫描文档、地理信息图件里很常见。

Unix compress生成的.Z压缩包也是LZW的杰作。PostScript Level 2的流编码里同样出现过LZW。PDF早期版本在特定条件下也允许使用LZW。换句话说，只要你解析的是二十世纪八九十年代定义的文件格式，就绕不开LZW。我现在做的这个兼容解析Demo，原因就是目标环境太小，塞进一个通用压缩库反而比手写LZW更麻烦。

1.3 什么情况下值得自己写一套LZW

这话要先说清楚：如果你只是压缩普通文本、网络包，直接用成熟压缩库就好，千万别没事手写。但下面三种情况，自己实现LZW是合理选择：

• 数据格式严格约束了LZW参数。GIF要求码字宽度从9位涨到12位，还要处理清屏码和结束码；如果第三方库的默认行为对不上，解析会直接错位。
• 运行环境太小。嵌入式设备、单片机或者兼容老模拟器时，整个压缩库的体积和依赖可能比压缩数据本身还大。
• 你想彻底搞懂压缩原理。LZW代码量不大，逻辑又完整，是学习字典压缩的绝佳样本。

2. 编码器逐字节构造字典：贪心前缀的完整推演

2.1 初始化与查找纪律：不重复的码字表

编码器启动时，先把0到255共256个字节作为长度为1的字符串放进字典，每个字节的索引就是它自己的值。比如ASCII字符'A'的索引是65，字节0x00的索引是0。从索引256开始，字典里才会出现多字节字符串。

处理流程是：读入新字节c，把“当前前缀P + c”整体拿到字典里查。查得到，说明这个字符串已经登记过了，当前前缀直接变长；查不到，说明匹配在这里断掉，此时输出P对应的码字，把“P + c”作为新字典项登记，然后把当前前缀重置为c。

这个规则的贪心体现在：只要还能继续扩展，就绝不输出；一旦扩展不了，就把能表达的最长字符串一次性编码成码字。输出总是滞后于输入一拍，所以字典中的字符串永远是“历史上已经完整见过”的片段。

2.2 一个字符串的编码过程全记录

拿字符串"ABABAB"走一遍。初始字典里只有0到255的单字节项，其中65对应'A'，66对应'B'。

• 读'A'，当前前缀P变成"A"。
• 读'B'，查"AB"，不存在。输出P对应的码字65，把"AB"登记为索引256，P重置为"B"。
• 读'A'，查"BA"，不存在。输出码字66，把"BA"登记为索引257，P重置为"A"。
• 读'B'，查"AB"，存在。P变成256，也就是字符串"AB"。
• 读'A'，查"ABA"，不存在。输出P对应的码字256，把"ABA"登记为索引258，P重置为"A"。
• 数据读完，当前P是"A"吗？不是，这里要注意：到了文件末尾，P是"A"，直接输出码字65。所以最终输出码字序列是65、66、256、65。

等一下，我上面推演出的结果和常见资料不太一样。重新细算最后一步：第五步读'A'之后P重置为"A"，但第六步已经没有新字节了，所以P就是"A"，输出65。整个字典里登记了256"AB"、257"BA"、258"ABA"。最终压缩流是65、66、256、65。这个例子的压缩率并不明显，但它清楚展示了“匹配失败才输出”的节奏。真正压缩率上来，需要输入里重复的长串足够多，比如几百个"AB"连续出现。

2.3 码字宽度何时增加：nextCode与位宽对齐

这是LZW最容易写错的地方之一。初始字典有256项，按说8位够用，但下一个新字典项的索引是256，它已经超过了8位能表达的0到255范围，所以编码从一开始就必须用9位写码字。

之后每新增一个字典项，nextCode加1。当nextCode从511变成512时，9位编码已经装不下索引512，下次输出任何码字都必须改用10位。判断时机是在“添加完新字典项之后”：

if (nextCode == (1 << codeWidth) && codeWidth < maxCodeBits) { ++codeWidth; }

这里有个容易混淆的点：当前这次输出的码字仍然用旧码宽，调宽只影响下一次输出。因为当前输出的码字在添加新字典项之前就已经确定了，它的数值肯定没有超过旧码宽范围。解码端也必须遵守同样的时序，在“添加完字典项之后”再调宽，两边保持一致。

如果设最大码宽12位，那么字典最多容纳4096个条目，之后无法再新增。到这一步可以选择冻结字典、清空字典，或者监控压缩率动态重置，后面第5节我再展开。

3. 解码器如何做到不传字典：同步添加的时序分析

3.1 解码器维护字典的时序：滞后一拍

解码器不需要额外接收字典，因为编码器生成字典的规则是固定的。但解码器重建字典的时序比编码器晚一步。每读到一个新码字，它先输出这个码字对应的字符串，然后才把“上一个字符串 + 当前字符串首字符”加入字典。

这就像两个人合著一份术语手册。编码者遇到没见过的组合时，会先在手册里登记，然后下一次才引用它；解码者要等这个术语真实出现在文档里，才能把术语的定义补进去。如果解码者看完一个码字就立刻登记，它比编码者多掌握一部分信息，后面的字典状态就会对不上。

3.2 特殊边界：读到尚未出现的码字怎么办

正常流程里，新码字总能在字典里查到。但LZW有一种著名的卡边情况：读到的newCode恰好等于解码器下一个要添加的索引。这时newCode在字典里还查不到。

为什么会出现这种情况？编码器在某一次匹配失败时，输出了旧前缀P，同时把“P + c”登记成了新索引N。紧跟着的下一轮，编码器可能又遇到了能匹配到这个新索引的字符串，并且立刻输出了N。解码器此时还没把索引N登记进字典，自然查不到。

处理办法也很经典：如果newCode等于字典大小，就用“上一个字符串 + 上一个字符串的第一个字符”来构造。这本质上是在复现编码器创建这个新字典项时的操作：编码器用旧前缀P加上触发字符c生成了新串，而触发字符c又恰好是解码器当前要输出的新串的第一个字符。

用"ABABABAB"这个输入来触发边界。编码输出会是65、66、256、258、66。解码器读到258时，自己的字典里只有256"AB"和257"BA"，258正好是下一个待添加索引，于是它用上一个字符串"AB"加上首字符'A'推导出"ABA"，输出之，再登记258为"ABA"。整个过程和编码器完全对应。

3.3 逐步解码示例：与编码过程严格对应

以码字流65、66、256、258、66为例：

• 读65，输出"A"，oldStr记为"A"。
• 读66，字典里存在，输出"B"，登记"AB"为索引256，oldStr更新为"B"。
• 读256，字典里存在，输出"AB"，登记"BA"为索引257，oldStr更新为"AB"。
• 读258，字典里没有，用oldStr"AB"加上首字符'A'得到"ABA"，输出"ABA"，登记"ABA"为索引258，oldStr更新为"ABA"。
• 读66，字典里存在，输出"B"，登记"ABAB"为索引259。

拼接起来正是"ABABABAB"。注意编码器的字典里，索引259也确实是"ABAB"。两边字典在这时候完全同步。

这个例子里我需要强调：解码器判断“newCode是否等于字典大小”用的是newCode >= dict.size()。因为正常情况下字典大小就是下一个待添加索引。如果你不小心写成newCode > dict.size()，边界情况会漏掉，解码会少一个字符甚至直接越界。

4. C++实现：字典容器、位流与两个类

4.1 固定数组查找表：比哈希表更合适的字典

编码器最核心的操作是“给定前缀索引和下一字节，查字典”。最自然的写法是用unordered_map<uint32_t, uint16_t>，键是(prefix << 8) | byte，值是新索引。但LZW的键空间其实很小：当最大码宽是12位时，前缀最多4095，键最大值约104万。这个规模完全可以直接开一个vector<uint16_t>数组，初始化为一个空标记值，查询就是一次数组访问。

哈希表的优势是稀疏存储，但LZW的字典会持续填充到接近满，数组访问没有哈希计算，也没有链表冲突，缓存还友好。我用的是固定数组版本，尺寸为(1 << (maxCodeBits + 8))，也就是1048576个uint16_t，约2MB内存。这个代价对绝大多数场景可以接受。

4.2 解码器如何存字符串：索引到字节串的映射

解码器需要一个“码字索引到字符串”的反向字典。最直白的做法是vector<vector<uint8_t>>，数组下标就是码字，元素就是那个码字对应的字节串。初始把0到255每个字节作为一个单元素vector放进去，之后每添加一个字典项就push_back一次。

这种实现的好处是思路清晰，不容易写错。缺点是每个字典项都会完整拷贝一遍字符串，遇到特别长的字典项时开销不小。教学和中小文件场景完全够用，工业级优化我放到第6节再说。

4.3 位级读写器：可变码宽同步的关键

LZW的码字不是按字节对齐的，9位、10位、11位、12位混着来，必须自己实现位流读写。写端用一个累加器攒着，凑满8个bit就输出一个字节；读端反向操作，凑够当前需要的码宽再取码。

这里有个工程细节：累加器一定要用uint64_t，别用uint32_t。因为码字宽度最大可能是16位，加上之前攒下的未输出位数，很容易超过32位，用32位会静默截断。下面的实现里我统一用uint64_t。

#include <cstdint> #include <vector> #include <cassert> class BitWriter { public: explicit BitWriter(std::vector<uint8_t>& out) : out_(out) {} void write(uint16_t code, int width) { acc_ |= static_cast<uint64_t>(code) << bitCnt_; bitCnt_ += width; while (bitCnt_ >= 8) { out_.push_back(static_cast<uint8_t>(acc_ & 0xFFu)); acc_ >>= 8; bitCnt_ -= 8; } } void flush() { if (bitCnt_ > 0) { out_.push_back(static_cast<uint8_t>(acc_ & 0xFFu)); acc_ = 0; bitCnt_ = 0; } } private: std::vector<uint8_t>& out_; uint64_t acc_ = 0; int bitCnt_ = 0; }; class BitReader { public: explicit BitReader(const std::vector<uint8_t>& in) : in_(in) {} bool read(uint16_t& code, int width) { while (bitCnt_ < width) { if (pos_ >= in_.size()) { return false; } acc_ |= static_cast<uint64_t>(in_[pos_]) << bitCnt_; ++pos_; bitCnt_ += 8; } code = static_cast<uint16_t>(acc_ & ((1u << width) - 1u)); acc_ >>= width; bitCnt_ -= width; return true; } private: const std::vector<uint8_t>& in_; size_t pos_ = 0; uint64_t acc_ = 0; int bitCnt_ = 0; };

编码器类我用固定数组查找表，最大码宽设为12位，字典满时执行“冻结”策略，也就是不再新增字典项。这个实现适合教学，也适合绝大多数小文件。

class LzwEncoder { public: LzwEncoder() { reset(); } void reset() { table_.assign(1 << (kMaxCodeBits + 8), kEmpty); nextCode_ = 256; codeWidth_ = kInitCodeWidth; } std::vector<uint8_t> encode(const std::vector<uint8_t>& input) { std::vector<uint8_t> out; BitWriter writer(out); reset(); if (input.empty()) { return out; } int prefix = input[0]; for (size_t i = 1; i < input.size(); ++i) { uint16_t byte = input[i]; uint32_t key = (static_cast<uint32_t>(prefix) << 8) | byte; uint16_t index = table_[key]; if (index != kEmpty) { prefix = index; } else { writer.write(static_cast<uint16_t>(prefix), codeWidth_); if (nextCode_ < kMaxCodes) { table_[key] = static_cast<uint16_t>(nextCode_); ++nextCode_; if (nextCode_ == (1 << codeWidth_) && codeWidth_ < kMaxCodeBits) { ++codeWidth_; } } prefix = byte; } } writer.write(static_cast<uint16_t>(prefix), codeWidth_); writer.flush(); return out; } private: static constexpr int kMaxCodeBits = 12; static constexpr int kMaxCodes = 1 << kMaxCodeBits; static constexpr int kInitCodeWidth = 9; static constexpr uint16_t kEmpty = 0xFFFF; std::vector<uint16_t> table_; int nextCode_ = 256; int codeWidth_ = 9; };

解码器我用vector<vector<uint8_t>>存字典，整体逻辑和前面的推演一致。

class LzwDecoder { public: LzwDecoder() { reset(); } void reset() { dict_.clear(); dict_.reserve(kMaxCodes); for (int i = 0; i < 256; ++i) { dict_.push_back({static_cast<uint8_t>(i)}); } nextCode_ = 256; codeWidth_ = kInitCodeWidth; } std::vector<uint8_t> decode(const std::vector<uint8_t>& input) { BitReader reader(input); std::vector<uint8_t> out; uint16_t oldCode = 0; if (!reader.read(oldCode, codeWidth_)) { return out; } if (oldCode >= dict_.size()) { return out; } std::vector<uint8_t> oldStr = dict_[oldCode]; out.insert(out.end(), oldStr.begin(), oldStr.end()); while (true) { uint16_t newCode = 0; if (!reader.read(newCode, codeWidth_)) { break; } std::vector<uint8_t> entry; if (newCode >= dict_.size()) { entry = oldStr; entry.push_back(oldStr.front()); } else { entry = dict_[newCode]; } out.insert(out.end(), entry.begin(), entry.end()); if (nextCode_ < kMaxCodes) { std::vector<uint8_t> add = oldStr; add.push_back(entry.front()); dict_.push_back(std::move(add)); ++nextCode_; if (nextCode_ == (1 << codeWidth_) && codeWidth_ < kMaxCodeBits) { ++codeWidth_; } } oldCode = newCode; oldStr = std::move(entry); } return out; } private: static constexpr int kMaxCodeBits = 12; static constexpr int kMaxCodes = 1 << kMaxCodeBits; static constexpr int kInitCodeWidth = 9; std::vector<std::vector<uint8_t>> dict_; int nextCode_ = 256; int codeWidth_ = 9; };

如果你只是自己写来跑着玩，上面这套代码已经能完成“编码→比特流→解码”的闭环。但正式用还要处理文件读写、字典满、EOF補位这些让人头疼的细节。

5. 边界条件与二进制文件处理：最容易翻车的地方

5.1 二进制模式读写：LZW处理的是字节流

LZW操作的对象永远是字节流，跟“文本”没有关系。Linux下fopen默认就是二进制语义，但Windows下如果不加ios::binary，某些字节会被系统当作换行或文件结尾处理，压缩数据可能被静默破坏。测试时我就在模拟环境里踩过一次，压缩后的数据写进文件再读出来，长度变短，解压直接失败。

正确做法是压缩前后的读写都显式用二进制模式：

std::ofstream fout("output.lzw", std::ios::binary); std::ifstream fin("input.bin", std::ios::binary);

如果输入是UTF-8中文等多字节文本，LZW仍然按原始字节处理，不需要提前理解Unicode。字典项是字节序列，不是字符序列，这点在定位问题时很重要。

5.2 EOF与最后一次输出：编码器要flush，解码器要停准

编码器在数据结束时，如果当前前缀非空，必须把前缀对应的码字写出去。这个输出往往就是一次匹配中断后的正常输出，只是因为没有下一个字节来触发中断，所以要显式收尾。

解码器的停止条件不是“收到结束码”，而是BitReader已经读不到一个完整的码字。BitWriter::flush()在末尾会补0，如果解码器没有正确判断“剩余位数不足”，就可能把补位解析成垃圾码字，输出多余字节。所以我在解码器里用reader.read() == false作为唯一停止条件，不在压缩流里强加结束标记。

如果你的格式允许自定义头部，强烈建议在压缩数据前面保存原始长度，或者至少保存码字数量。这样解码端在恢复出的数据长度达到预期时就能提前结束，多一层防御。

5.3 字典满后的选择：冻结、清空还是early change

字典容量不是无限的。12位码宽下最多4096个条目，等nextCode到4096时，你就必须决定接下来怎么办。

冻结策略最简单，我上面的代码就是这种。字典不再新增，编码器继续用已有条目压缩能压缩的部分，匹配不上就当单字节输出，解码器同步冻结。缺点很明显：随着输入变化，旧字典项会越来越不适合新数据，压缩率可能下降。

清空重建策略在GIF时代很常见。字典满时输出一个清屏码，然后两端同时把字典重置到只有256个单字节项的状态。代价是清空后要重新积累字典，如果输入是高度重复的连续数据，清空反而会打断压缩率。

还有一种early change策略，是在字典还没完全满时就提前重置。一些老格式希望避免码宽切换带来的微小开销，会在特定时机提前清空。工业实现里Unix compress会监控输出字节数，如果发现压缩率变差，就主动清空字典重新开始。

选哪种要看你对接的格式。设计新格式的话，冻结策略最简单可控；需要更好压缩率的话，建议参考Unix compress的动态监控策略。

5.4 异常输入与刻意防御

LZW解码器本身不校验数据完整性。压缩文件被截断、被改错，解码端可能输出乱码而不报错。如果字节数不对，我一般会在调用方加哈希校验，或者至少对比原始长度。

还要注意位流输出顺序。上面BitWriter和BitReader用的是同一种小端式逐字节输出规则，自己跟自己一致没问题。但如果你的压缩文件要跨平台交换，最好在头部写一个字节序和码宽约定的标记，避免不同实现之间发生解释差异。

6. 实测压缩率、调试技巧与优化方向

6.1 用三类数据测出LZW的真实性格

LZW不是万金油，它的性格很鲜明。我用三类模拟数据测过：

膨胀原因很简单：编码从9位码宽起步，单字节字符本来8位能表示，现在每个至少占9位。一段完全没有重复的随机数据，字典里全是最短的单字节项，压缩后反而比原数据大。所以LZW适合格式规整、重复率高的文件，不适合加密或压缩过的数据。测试项目里如果发现压缩输出比输入大，不要怀疑算法写错，先看一下输入熵值。

6.2 调试LZW的思路：码字流是人眼能看懂的中间产物

LZW调试最关键的一点是：码字流是可以打印出来人肉核对的。编码器每输出一个码字，解码器每读入一个码字，都可以打印当时的码字值、当前码宽、新增字典项。

我推荐按下面这套链路排查：

1. 先用短字符串在内存里跑通decode(encode(s)) == s，不要一上来就处理几百MB的文件。
2. 让编码器和解码器都输出码字流序列。正常时两边第一个不一致的位置就是出错起点。
3. 在出错位置往前回看，重点检查码宽是否在同一个时机切换。位宽错位是万恶之源，一旦错位后面全乱。
4. 用十六进制查看压缩位流，手工拆出前几个码字，验证BitWriter输出是否符合预期。这一步能筛掉大部分字节序和移位错误。

我最初写位流的时候就是在第2步发现，编码器在输出当前码字前就调整了码宽，解码器在读取下一个码字后才调整码宽，两边相差一个码字的位置，导致从某一点开始所有码字全部多占了一位。

6.3 面向真实项目的性能优化

如果只是教学，上面的代码已经够好。真要压大文件，最先需要优化的是解码器的字符串存储。

vector<vector<uint8_t>>的每个字典项都独占一块动态内存，压入和解码时的字符串拷贝会让性能明显下降。工业实现一般把每个字典项存成两个字段：前缀索引和尾部字节。输出字符串时，从给定索引一路回溯到单字节根节点，把沿途的尾部字节暂存在栈里，再反向输出。这样解码过程变成O(n)的栈操作，省掉大量拷贝。

编码器的固定数组虽然快，但最大码宽开到16位时键空间会涨到约1600万，数组内存会到32MB左右。这时候要么接受这个代价，要么改用哈希表。12位码宽下，固定数组依然是最优选。

另外可以做流式化。别把整个文件读进vector<uint8_t>再压缩，而是让BitWriter直接对接文件流，字典和码宽逻辑保持不变。内存占用能降到“字典大小加少量缓冲”的量级，对嵌入式场景很有意义。我后续在兼容解析Demo里就是把整文件读入改成了流式，内存峰值只跟重复模式长度有关，不再受文件大小影响。

LZW本身不难，难的是把位宽切换、EOF收尾、字典满策略这些边角理顺。这次实现最大的收获不是那几百行代码，而是彻底理解了“编解码双方通过时序保持同步”这件事。以后再遇到GIF里的LZW变体，或者老游戏资源包里的魔改LZW，先打印码字流看一眼，很快就能定位问题。