C++实现LZW无损压缩算法：从原理到工程实践 1. 项目概述从字符串到编码的奇妙旅程最近在整理一些历史数据发现很多文本日志文件体积庞大传输和存储都不太方便。手动压缩吧费时费力用现成的库吧有时候又想知道底层到底是怎么“变魔术”的。这让我想起了数据压缩领域一个经典且优雅的算法——LZW。它不像哈夫曼编码那样需要预先统计频率也不像游程编码那样只对连续重复数据有效。LZW的魅力在于它能在压缩过程中动态地“学习”并构建一本属于自己的字典用简短的编码来代表越来越长的字符串片段。这种“边读边学”的特性让它对文本、特别是包含大量重复短语的文本有着非常不错的压缩效果。这次我们不依赖任何第三方压缩库就用纯C来实现一个完整的LZW压缩与解压缩程序。目标很明确第一深入理解LZW算法每一步的核心思想搞清楚编码表是如何从无到有建立起来的第二获得一份清晰、可运行、可调试的源代码你可以直接拿去研究或者集成到自己的小工具里第三通过动手实现掌握处理二进制数据、位操作、文件IO等C中相对底层但至关重要的技能。无论你是正在学习数据结构和算法的学生还是想夯实C基本功、探索无损压缩原理的开发者这个项目都会是一次很有价值的实践。我们会从最朴素的字典模型开始逐步处理边界情况最终实现一个健壮的压缩器。你会发现看似复杂的压缩过程其内核逻辑是如此的简洁和巧妙。2. LZW算法核心思想与设计思路拆解2.1 LZW算法原理为何无需预读统计LZW算法的全称是Lempel-Ziv-Welch它是Abraham Lempel和Jacob Ziv提出的LZ系列算法的变种由Terry Welch加以改进。它的核心智慧在于自适应字典编码。与哈夫曼编码需要扫描全部数据以构建静态频率表不同LZW的字典是在压缩过程中动态创建和使用的。想象一下你在阅读一本英文书边读边记笔记。一开始你的笔记里只记录了26个字母a-z和空格。当你读到第一个单词“the”时你发现字母‘t’和‘h’的组合“th”经常出现于是你在笔记里新加一条“256号代表‘th’”。之后每当再遇到“th”这两个字符连续出现你就不再写‘t’和‘h’而是直接写上“256”这个编号。接着你可能发现“the”这个完整的单词出现频率更高于是你又添加“257号代表‘the’”。如此往复你的笔记字典里记录的就不再是单个字符而是越来越长的、在这本书里常见的字符串片段。LZW算法正是这样工作的初始化字典包含所有可能的单字符例如0-255代表所有字节值。压缩过程顺序读取输入数据维护一个当前“前缀字符串”。算法总是尝试为“当前前缀下一个字符”这个更长的字符串在字典中寻找编码。如果找到则扩展前缀如果没找到则输出当前前缀的编码并将这个新的字符串当前前缀下一个字符添加到字典中然后从下一个字符开始新的前缀。输出最终输出的是一系列代表字典中字符串的编码码字。解压过程是压缩的逆过程同样从初始化单字符字典开始根据接收到的码字序列一边输出字符串一边以与压缩器相同的规则重建字典从而完全还原原始数据。这种设计的优势非常明显它对于存在大量重复子串的数据压缩效率极高比如文本、源代码、位图等。而且它是自适应的无需提前知道数据的统计特性。2.2 我们的C实现方案选型理解了原理接下来就要用C将其落地。这里有几个关键的设计决策点1. 字典的数据结构选择这是性能的关键。我们需要一个能快速根据“字符串”查找“编码”压缩时又能根据“编码”查找“字符串”解压时的结构。压缩字典我们需要std::unordered_mapstd::string, uint16_t。unordered_map哈希表提供了平均O(1)时间的字符串查找速度非常适合根据前缀快速确定其编码。解压字典我们更需要std::vectorstd::string或std::mapuint16_t, std::string。由于解压时我们是按编码顺序依次重建字典的用vector通过下标编码直接访问字符串效率最高O(1)时间复杂度。2. 编码位宽的选择字典不能无限大。通常我们使用固定位宽的编码例如12位。这意味着字典最多有2^12 4096个条目。为什么是12位这是一个权衡。9位512条可能太小字典很快被填满导致后续压缩效率下降16位65536条又太大每个输出码字占2字节对于小文件可能得不偿失。12位是一个经典折中选择它要求我们能够按位bit进行读写而不是按字节。3. 文件IO与位流处理标准C文件流是按字节操作的。但我们要输出12位的码字这就需要实现一个位流写入器和位流读取器。这是本项目的一个技术难点也是亮点。我们需要一个缓冲区来累积位凑够一个字节8位再实际写入文件读取时也是同理。4. 处理字典满的情况当字典条目数达到最大值如4096时常见的策略有停止增长后续不再添加新条目仅使用现有字典进行编码。简单但可能影响后续数据的压缩率。清空重置清空字典保留单字符基础项重新开始构建。适用于数据特征可能发生变化的长文件。冻结冻结字典不再变化。 在我们的实现中为了清晰展示核心逻辑我们将采用“停止增长”策略。在实际产品级实现中重置策略更为常见。基于以上分析我们的实现蓝图已经清晰我们将构建一个LZWCompressor类和一个LZWDecompressor类它们内部封装字典、位流处理器并提供compress和decompress方法。3. 核心模块详解与C实现要点3.1 字典模块的设计与实现字典是LZW算法的心脏。我们需要实现两种视图的字典。压缩字典 (CompressDictionary):class CompressDictionary { private: std::unordered_mapstd::string, uint16_t map_; uint16_t nextCode_; const uint16_t maxCode_; public: // 初始化时加入所有256个单字节字符串 CompressDictionary(uint16_t bitWidth) : maxCode_((1 bitWidth) - 1) { reset(); } void reset() { map_.clear(); for (int i 0; i 256; i) { map_[std::string(1, static_castchar(i))] i; } nextCode_ 256; // 256-255是单字符编码新编码从这里开始 } bool contains(const std::string str) const { return map_.find(str) ! map_.end(); } uint16_t getCode(const std::string str) const { return map_.at(str); // 调用前需确保contains为true } // 添加新字符串并返回其编码如果字典已满则返回false bool add(const std::string str, uint16_t outCode) { if (nextCode_ maxCode_) { return false; // 字典已满 } outCode nextCode_; map_[str] nextCode_; nextCode_; return true; } bool isFull() const { return nextCode_ maxCode_; } };注意这里使用std::unordered_map键是std::string。在频繁拼接字符串查找时这可能会成为性能瓶颈。在极端性能要求的场景下可以考虑使用定制的Trie树结构。但对于理解和首次实现哈希表是最清晰的选择。解压字典 (DecompressDictionary):class DecompressDictionary { private: std::vectorstd::string vec_; uint16_t nextCode_; const uint16_t maxCode_; public: DecompressDictionary(uint16_t bitWidth) : maxCode_((1 bitWidth) - 1) { reset(); } void reset() { vec_.clear(); vec_.reserve(maxCode_ 1); for (int i 0; i 256; i) { vec_.push_back(std::string(1, static_castchar(i))); } nextCode_ 256; } const std::string getString(uint16_t code) const { if (code vec_.size()) { throw std::runtime_error(Invalid code during decompression!); } return vec_[code]; } // 添加新字符串返回新编码 bool add(const std::string str, uint16_t outCode) { if (nextCode_ maxCode_) { return false; } outCode nextCode_; vec_.push_back(str); nextCode_; return true; } bool isFull() const { return nextCode_ maxCode_; } };实操心得解压字典用vector非常合适因为编码是连续递增的直接通过下标访问是O(1)操作。注意在getString时要进行边界检查因为理论上可能收到无效的编码如果压缩文件损坏或版本不一致。3.2 位流处理跨越字节的边界这是本项目最易出错的部分。我们要处理12位码字而文件系统以8位1字节为单位。位流写入器 (BitWriter):class BitWriter { private: std::ofstream outputStream_; unsigned char buffer_; // 当前正在组装的字节 int bitsInBuffer_; // 当前缓冲区中已存储的位数 public: explicit BitWriter(std::ofstream os) : outputStream_(os), buffer_(0), bitsInBuffer_(0) {} // 写入一个bitsWidth位的码字 void writeBits(uint16_t code, int bitsWidth) { int bitsRemaining bitsWidth; while (bitsRemaining 0) { // 计算当前字节还能放入多少位 int freeBits 8 - bitsInBuffer_; int bitsToWrite std::min(bitsRemaining, freeBits); // 将code的相应位移到buffer的正确位置 // 例如写入12位码字0xABC (1010 1011 1100) // 第一次循环可能写入高4位(1010)到buffer的低4位 unsigned char part (code (bitsRemaining - bitsToWrite)) ((1 bitsToWrite) - 1); buffer_ | (part (freeBits - bitsToWrite)); bitsInBuffer_ bitsToWrite; bitsRemaining - bitsToWrite; // 如果缓冲区满了写入文件并清空 if (bitsInBuffer_ 8) { outputStream_.put(buffer_); buffer_ 0; bitsInBuffer_ 0; } } } // 刷新缓冲区如果缓冲区还有数据补零并写入最后一个字节 void flush() { if (bitsInBuffer_ 0) { outputStream_.put(buffer_); // 剩余位已在buffer_高位低位是0 buffer_ 0; bitsInBuffer_ 0; } } };位流读取器 (BitReader):class BitReader { private: std::ifstream inputStream_; unsigned char buffer_; // 当前读取的字节 int bitsInBuffer_; // 当前缓冲区中剩余的未读位数 bool eof_; // 是否已到达文件末尾 public: explicit BitReader(std::ifstream is) : inputStream_(is), buffer_(0), bitsInBuffer_(0), eof_(false) {} // 读取一个bitsWidth位的码字如果读到文件尾则返回false bool readBits(uint16_t code, int bitsWidth) { code 0; int bitsNeeded bitsWidth; while (bitsNeeded 0) { if (bitsInBuffer_ 0) { if (inputStream_.eof()) { eof_ true; return false; // 没有足够的数据了 } buffer_ inputStream_.get(); bitsInBuffer_ 8; } int bitsToRead std::min(bitsNeeded, bitsInBuffer_); // 从buffer_的高位提取bitsToRead位 unsigned char part (buffer_ (bitsInBuffer_ - bitsToRead)) ((1 bitsToRead) - 1); code (code bitsToRead) | part; bitsInBuffer_ - bitsToRead; bitsNeeded - bitsToRead; // 清除已读出的位 buffer_ ((1 bitsInBuffer_) - 1); } return true; } bool isEof() const { return eof_; } };关键细节与避坑指南字节序Endianness我们的实现是在单个字节内进行位操作属于“比特序”问题。我们约定总是处理字节的高位MSB。在BitWriter中我们将新位放在buffer_的高位空位在BitReader中我们从buffer_的高位剩余位开始读取。保持这个约定一致至关重要否则压缩和解压将无法匹配。flush()的必要性压缩结束时buffer_里可能还有未写满的位比如最后只写了4位。必须调用flush()将这些位低位补零写入文件否则会丢失数据。解压时对应的BitReader会正确读取这些位并在遇到文件尾时停止。解压时的文件尾判断BitReader::readBits在无法读取足够位数时应返回false。解压循环应以此作为终止条件而不是单纯依赖ifstream::eof()因为位流可能结束在一个字节的中间。3.3 压缩与解压缩的核心流程控制有了字典和位流处理器我们就可以组装核心逻辑了。压缩流程伪代码与关键点初始化字典 (包含0-255单字符) 当前前缀P 空 while 从输入文件读取下一个字符 C { if (字典中存在 P C) { P P C } else { 输出 P 对应的编码到位流 if (字典未满) { 将 P C 加入字典 } P C // 注意P 重置为单字符 C } } // 循环结束后 if (P 不为空) { 输出 P 对应的编码 } 刷新位流写入器注意事项字符C的类型是unsigned char0-255以避免符号扩展问题。P最初是空的在代码中可以用一个std::string变量来表示但频繁的字符串拼接P C会产生很多临时对象影响性能。一个常见的优化是使用std::string_view或直接操作字符数组但为了代码清晰我们初次实现仍使用std::string。解压缩流程伪代码与关键点初始化字典 (包含0-255单字符) 从位流读取第一个码字 - 输出对应的字符串 - 令 oldCode 该码字 while 从位流成功读取下一个码字 newCode { if (字典中存在 newCode) { 输出 字典[newCode] 对应的字符串 - 令 currentString 字典[newCode] if (字典未满) { 将 字典[oldCode] currentString[0] 加入字典 } } else { // 这是一个LZW算法的特殊情况 currentString 字典[oldCode] 字典[oldCode][0]; 输出 currentString if (字典未满) { 将 currentString 加入字典 } } oldCode newCode; }核心难点——特殊情况处理解压算法中if (字典中存在 newCode)的else分支是理解LZW的关键。这种情况发生在压缩时一个刚被加入字典的字符串假设为X在下一个步骤中立刻被用作前缀并遇到了一个新字符c从而使得Xc被加入字典并输出X的编码。在解压时我们收到这个新编码时它对应的字符串Xc还未被加入解压字典此时我们需要根据oldCode即X的编码和X的第一个字符来推导出Xc。这个逻辑必须与压缩器的行为严格对应。4. 完整的C实现与代码剖析下面我们将把上述模块组合起来形成一个完整的、可编译运行的LZW压缩解压程序。为了清晰我们将所有类定义在同一个文件中。4.1 头文件与常量定义// lzw.h #ifndef LZW_H #define LZW_H #include fstream #include string #include unordered_map #include vector #include cstdint #include stdexcept // 默认使用12位编码字典最大容量4096 constexpr int DEFAULT_CODE_BITS 12; constexpr uint16_t MAX_DICT_SIZE 1 DEFAULT_CODE_BITS; // 4096 class BitWriter { /* 如前文所述 */ }; class BitReader { /* 如前文所述 */ }; class CompressDictionary { /* 如前文所述 */ }; class DecompressDictionary { /* 如前文所述 */ }; class LZWCompressor { public: static bool compress(const std::string inputFilename, const std::string outputFilename, int codeBits DEFAULT_CODE_BITS); }; class LZWDecompressor { public: static bool decompress(const std::string inputFilename, const std::string outputFilename, int codeBits DEFAULT_CODE_BITS); }; #endif // LZW_H4.2 压缩器实现细节// lzw.cpp - compress 函数实现 bool LZWCompressor::compress(const std::string inputFilename, const std::string outputFilename, int codeBits) { std::ifstream inFile(inputFilename, std::ios::binary); if (!inFile.is_open()) { std::cerr 无法打开输入文件: inputFilename std::endl; return false; } std::ofstream outFile(outputFilename, std::ios::binary); if (!outFile.is_open()) { std::cerr 无法创建输出文件: outputFilename std::endl; return false; } // 可选在文件头写入编码位宽确保解压时使用相同参数 outFile.put(static_castunsigned char(codeBits)); CompressDictionary dict(codeBits); BitWriter bitWriter(outFile); std::string currentPrefix; char ch; while (inFile.get(ch)) { unsigned char c static_castunsigned char(ch); std::string extendedPrefix currentPrefix static_castchar(c); if (dict.contains(extendedPrefix)) { // 当前前缀字符仍在字典中扩展前缀 currentPrefix extendedPrefix; } else { // 输出当前前缀的编码 uint16_t codeToOutput dict.getCode(currentPrefix); bitWriter.writeBits(codeToOutput, codeBits); // 尝试将新字符串加入字典 uint16_t newCode; if (dict.add(extendedPrefix, newCode)) { // 成功添加可以继续 } else { // 字典已满后续不再添加新条目 // 在实际应用中这里可以重置字典 (dict.reset()) } // 重置前缀为当前单个字符 currentPrefix std::string(1, static_castchar(c)); } } // 处理文件末尾剩余的前缀 if (!currentPrefix.empty()) { uint16_t codeToOutput dict.getCode(currentPrefix); bitWriter.writeBits(codeToOutput, codeBits); } bitWriter.flush(); inFile.close(); outFile.close(); return true; }代码解析与心得文件以二进制模式打开这是必须的否则在Windows等系统上\n字符可能会被转换破坏数据。unsigned char处理从文件读取的char可能为负值转换为unsigned char能确保其在0-255范围内作为字典键的一部分是安全的。字典满的处理代码中只是简单地停止添加。一个更健壮的工业级实现会在字典满时或达到一定使用率时重置字典并向输出流写入一个特殊的“重置码字”例如256如果256被用作单字符扩展的起始点则可以用一个更大的特殊值通知解压器也重置字典。这能更好地适应数据特征的变化。性能瓶颈最内层循环的dict.contains(extendedPrefix)和extendedPrefix currentPrefix c是性能热点。extendedPrefix的创建涉及内存分配和拷贝。一个优化是使用std::string_view来避免拷贝但需要小心管理底层字符的生命周期。4.3 解压器实现细节bool LZWDecompressor::decompress(const std::string inputFilename, const std::string outputFilename, int codeBits) { std::ifstream inFile(inputFilename, std::ios::binary); if (!inFile.is_open()) { std::cerr 无法打开输入文件: inputFilename std::endl; return false; } // 读取文件头中的编码位宽如果存在 int storedCodeBits inFile.get(); if (storedCodeBits ! EOF storedCodeBits ! codeBits) { std::cout 警告文件头指定的位宽( storedCodeBits )与参数( codeBits )不同使用文件头位宽。 std::endl; codeBits storedCodeBits; } else if (storedCodeBits EOF) { // 文件没有头使用默认参数需要将文件指针复位 inFile.clear(); inFile.seekg(0); } std::ofstream outFile(outputFilename, std::ios::binary); if (!outFile.is_open()) { std::cerr 无法创建输出文件: outputFilename std::endl; return false; } DecompressDictionary dict(codeBits); BitReader bitReader(inFile); uint16_t oldCode, newCode; // 读取第一个码字 if (!bitReader.readBits(oldCode, codeBits)) { // 空文件 return true; } if (oldCode dict.nextCode_) { // 第一个码字就无效 std::cerr 压缩文件已损坏或格式不正确。 std::endl; return false; } std::string currentString dict.getString(oldCode); outFile.write(currentString.c_str(), currentString.size()); std::string firstChar currentString.substr(0, 1); // 用于后续构建 while (bitReader.readBits(newCode, codeBits)) { std::string outputString; if (newCode dict.nextCode_) { // 码字在字典中 outputString dict.getString(newCode); } else if (newCode dict.nextCode_) { // 特殊情况码字等于下一个待分配的编码 outputString dict.getString(oldCode) firstChar; } else { // 无效码字 std::cerr 解压错误遇到无效码字 newCode std::endl; return false; } // 输出字符串 outFile.write(outputString.c_str(), outputString.size()); // 构建新字符串并加入字典 std::string newEntry dict.getString(oldCode) outputString.substr(0, 1); uint16_t addedCode; if (dict.add(newEntry, addedCode)) { // 成功添加 } // 更新状态为下一次循环准备 firstChar outputString.substr(0, 1); oldCode newCode; } outFile.close(); inFile.close(); return true; }关键点与错误处理文件头我们在压缩文件开头写入了一个字节表示编码位宽。解压时先读取它这提高了兼容性。如果文件没有这个头比如旧版本文件则回退到使用传入的codeBits参数。第一个码字的处理第一个码字一定是单字符直接输出即可。特殊情况的判断if (newCode dict.nextCode_)是处理前文提到的“刚加入字典的字符串立刻被使用”情况的核心。注意dict.nextCode_是下一个将要分配的编码所以当newCode等于它时意味着解压器需要“预测”这个新字符串。错误处理对码字进行了有效性检查newCode dict.nextCode_或newCode dict.nextCode_。如果收到超出范围的码字说明压缩文件可能已损坏或者压缩/解压使用的位宽参数不一致。firstChar的维护我们需要记录上一个输出字符串的第一个字符用于构建要加入字典的新条目dict.getString(oldCode) firstChar。注意在每次循环末尾更新它。4.4 主函数示例与测试// main.cpp #include lzw.h #include iostream int main(int argc, char* argv[]) { if (argc ! 4) { std::cerr 用法: argv[0] compress/decompress input file output file std::endl; return 1; } std::string mode argv[1]; std::string inputFile argv[2]; std::string outputFile argv[3]; bool success false; if (mode compress) { success LZWCompressor::compress(inputFile, outputFile); if (success) { std::cout 压缩完成。 std::endl; } } else if (mode decompress) { success LZWDecompressor::decompress(inputFile, outputFile); if (success) { std::cout 解压完成。 std::endl; } } else { std::cerr 模式错误请使用 compress 或 decompress。 std::endl; return 1; } if (!success) { std::cerr 操作失败。 std::endl; return 1; } return 0; }你可以使用一个文本文件例如test.txt内容为TOBEORNOTTOBEORTOBEORNOT进行测试# 编译 g -stdc11 -o lzw main.cpp lzw.cpp # 压缩 ./lzw compress test.txt test.lzw # 解压 ./lzw decompress test.lzw test_decompressed.txt # 比较 diff test.txt test_decompressed.txt如果diff命令没有输出说明压缩和解压过程完全无损实现正确。5. 常见问题、优化方向与扩展思考5.1 实现中可能遇到的典型问题压缩后文件反而变大原因LZW对非常短或完全随机无重复模式的数据压缩效果不好。因为输出的是固定位宽如12位的编码而输入是8位字节。如果字典没有建立起有效的长字符串映射每个输出码字可能只代表一个或两个输入字符导致膨胀。例如12位码字是1.5字节如果只代表1个原始字节文件就变大了50%。排查检查输入文件类型。对纯随机二进制文件LZW可能不适用。可以尝试使用更大的初始字典如直接使用12位但单字符编码仍用8位表示需要更复杂的头信息或者在压缩率持续不佳时动态增加码字位宽变长LZW。解压时出现“无效码字”错误原因1压缩和解压使用的编码位宽(codeBits)不一致。确保使用相同参数。原因2压缩文件在传输或存储过程中损坏。原因3最隐蔽压缩器和解压器对字典满后的处理逻辑不一致。比如一个重置了字典另一个没有。我们的示例代码采用“停止增长”两者一致。但如果实现重置逻辑必须确保压缩器写入重置标记解压器读到后执行同样的重置操作。处理大文件时内存或速度问题字典内存使用12位编码字典最多4096个条目。unordered_map和vector的内存开销是可控的。但如果使用16位或更大位宽内存消耗会急剧增加unordered_map的每个条目开销较大。可以考虑使用更紧凑的结构如数组实现的Trie树。速度瓶颈如前所述字符串拼接和哈希查找是热点。对于std::string键的unordered_map频繁的字符串构造和销毁会拖慢速度。可以使用std::string_view但需注意生命周期或者实现一个自定义的哈希函数和相等比较器直接操作字符指针和长度。5.2 性能优化与功能扩展方向变长编码Variable-Length Code 经典的LZW实现如GIF图像格式中使用的采用变长编码。开始时使用9位码字当字典条目数达到2^9时切换到10位以此类推直到最大位宽如12位。这能在压缩初期减少输出体积提高整体压缩率。实现此功能需要BitWriter和BitReader支持动态改变写入/读取的位数。字典管理策略重置策略当压缩率下降或字典满时清空字典保留前256项重新开始。需要在输出流中插入一个特殊的“重置码字”。LRU淘汰策略当字典满时淘汰最久未使用的条目而不是停止增长或全部重置。这更复杂但可能对数据特征变化不剧烈的流式数据有更好效果。输入输出缓冲 目前的实现是逐字符读取和逐字符串输出。对于大文件应该使用缓冲区例如std::vectorchar批量读取数据到内存压缩逻辑遍历这个缓冲区。输出时也可以先缓存一批码字再统一写入位流减少系统调用次数。支持流式压缩 将压缩器类实例化提供putByte()和finish()这样的接口使其可以处理网络流或管道数据而不是仅面向文件。更高效的数据结构 对于追求极致性能的场景可以替换std::unordered_map。一种经典方法是使用哈希链表Hash Table with Chaining或双数组Trie树Double-Array Trie来存储字典键不再是完整的std::string而是父节点编码当前字符对这样可以极大减少内存占用和提升查找速度。5.3 从LZW出发理解压缩算法的权衡实现完LZW你应该对无损压缩有了更深的体会。压缩算法的核心永远是在时间、空间和压缩率之间做权衡。LZ77/LZ78系列包括LZW侧重于利用数据的重复性。它们通过查找并引用之前出现过的字符串来压缩对于文本、源代码等非常有效。其解码速度通常很快像LZW是线性时间。熵编码如哈夫曼、算术编码侧重于利用数据的概率分布。它们为更频繁出现的符号分配更短的编码。通常用于对LZ系列算法输出的“符号流”进行二次压缩例如DEFLATE算法就是LZ77哈夫曼。字典大小的权衡字典越大能记住的字符串模式越多压缩率可能越高但内存占用也越大并且每个码字占用的位数也越多除非用变长编码。我们的12位选择就是一个典型权衡。自适应性LZW的自适应特性使其无需预读和训练但这也意味着对开头部分的数据压缩率较低。有些算法采用两遍扫描第一遍统计第二遍编码可以获得更优的压缩率但无法用于流式数据。把这个LZW实现当作一个起点。你可以尝试修改位宽测试不同文件类型的压缩率可以实现变长编码可以尝试与简单的哈夫曼编码结合看看压缩率能提升多少。通过动手调整和实验你会对“数据压缩”这门艺术有更直观、更深刻的认识。