-
-
[原创] 信息编码之 LZW 压缩算法
-
发表于: 2025-8-1 11:48 3679
-
最近发现一个在线塔防策略游戏网站：b73K9s2c8@1M7s2y4Q4x3@1q4Q4x3V1k6Q4x3V1k6&6L8%4u0Y4i4K6u0W2K9h3!0Q4x3V1j5`.，基本玩法是昼夜交替的生存挑战，如图 1.1 所示，玩家需白天建立资源供应链，包括采矿（水晶、铁矿、铀矿等）、运输（通过运输机连接建筑）和工厂生产（如炮弹、弓箭、护盾等），为夜晚防御做准备，晚上僵尸从地图边界进攻，玩家需通过防御塔（箭塔、加农炮、闪电塔等）和城墙抵御攻击。每 10 天会刷新强力 BOSS。
游玩时发现可以本地存档，下次游玩时加载存档文件继续上次进度。作为一名网安狗，当即就想到修改存档改变数值，达到无限水晶和技能点的效果。
通过打开开发者工具并跟踪保存存档的过程，我们可以定位到具体的保存函数。这里不展开具体的跟踪步骤，基本思路是：以存档文件名为关键词进行搜索，找到触发保存的函数，再向下追踪调用栈，分析可知网页逻辑是先将存档数据保存到 localStorage 中，通过索引 savegame_blob_xxxx 查找对应的存档数据，再执行保存文件的操作。搜索关键词 savegame_blob_ 找到处理函数，逻辑流程如下：this.root.savegames.saveGame() → updateLastSavegame() → dataToString(t) →compressToEncodedURIComponent(t) → _compress(t)。
如图 1.2 所示，分析_compress() 可知这是一个 LZW 压缩算法，那么什么是 LZW 压缩算法呢？
LZW 其实是三个大佬的名字，这个算法最开始是 Ziv 和 Lempel 这两个人于 1977，1978 年发明，在 1984 年的时候由 Terry Welch 进行了改进，由此得名 LZW 编码（Lempel-Ziv-Welch Encoding），属于 LZ78 编码的变种。简单来说，LZW 算法就是通过建立一个字符串表，将多次出现的字符串存到表中并编号，用较短的编号表示较长的字符串来实现压缩。也被称为串表压缩算法。
假设我们要通过互联网传输一本英文牛津字典。按照常规方式，一个字符占 1 字节，这本字典大约包含 60 万个单词（包括重复的），每个单词平均 5 个字母，总共约 300 万个字符，也就是 300 万字节的数据量。
但如果我们换种思路：先提取出不重复的单词，假设有 20 万个唯一单词。我们给每个单词编上一个编号，比如从 1 开始。只需 3 个字节（24 位）就能唯一表示一个编号（224>200000）。这样，每个单词只需用 3 个字节的编号代替原始文本。对于总共 60 万个单词，传输只需 60 万 × 3 = 180 万字节。相比原来的 300 万字节，这种方法节省了超过三分之一的数据量。
LZW 编码也是同理，把出现过的字符串映射到编号上，实现压缩。例如对于字符串：ABABAB，可以看到子串 AB 多次重复， 我们可以用一个特殊的符号（比如数字 2）来表示 AB ，那么原来的字符串就可以表示为：AB22。在这个例子中，数字 2 被称为子串 AB 的符号（Symbol）。那 A 和 B 本身有没有符号？当然有。我们可以规定 0 表示 A，1 表示 B。于是最终压缩后的数据是一个符号流（Symbol Stream）：0122。
当然在真实的 LZW 编码中，A 和 B 不会用 0 和 1 表示，而是直接用它们的 ASCII 值。LZW 的初始字典包含所有 256 个 ASCII 字符，这些字符的符号就是它们各自的 ASCII 值。从 256 开始，编码过程中会动态添加新的字符串映射，这部分称为扩展字典（Extended Dictionary）。上面案例中在 LZW 编码会转成：65 (A) 66 (B) 257 (AB)。
有同学可能会问：为什么第一个 AB 不也用 2 表示？这样不又节省了一个符号？这个问题正好引出了 LZW 的一个核心思想：压缩后的数据是自解释的（self-explaining）。 在 LZW 编码中，压缩数据本身不包含完整的字典。也就是说，压缩文件里并不会存放“2 → AB”这种映射关系。LZW 编码、解码中除了初始字典（0 → A 和 1 → B），不会带有任何关于扩展字典的映射。
回到上面的示例。其编码过程（概念简化版）如下：
那解码器是怎么知道符号 2 代表 AB 的？答案是：它在解码的过程中自己“推出来”的。LZW 的解压过程和编码一样，从初始字典出发，一边根据已经解出的内容动态构建字典一边解码。
当我们解码 0122 时，解码器的过程（概念简化版）是：
现在就解释为什么前面不能直接用 2。因为在前两个字符 A 和 B 被编码输出之前，AB 组合还不存在于字典中。一开始就用 2 表示 AB，解码器看到“2”时会不知道它指的是什么，它还没从前文推导出 2 → AB 的关系。所以前面的 0 和 1 不只是输出结果，它们本身就是构建后续字典的“依据”，是字典构建的“第一现场”。这就是“自解释”：压缩后的数据本身就包含了解压所需的全部信息，压缩时使用的字典不需要另外传输或存储。
下面我们通过一个稍微复杂的例子，完整展示 LZW 编码与解码的全过程，重点是理解：在解码时，每一步是如何对应编码过程中的操作，以及如何一步步还原原始字符串并重建编码时使用的字典。
编码器在处理原始字符串时，会不断读取新字符，并尝试将已有的字符串或组合进行编码。为了实现这一过程，我们维护两个变量：
编码器的工作是将 P+C 这个组合查找字典，如果存在，就继续向后读取字符并扩展；如果不存在，就将 P 对应的符号输出，并将 P+C 加入字典。具体编码流程如下：
初始化：字典中只包含所有单字符的默认项，例如 0 → a，1 → b，2 → c 等。此时变量 P 和 C 均为空。
读取字符：读入一个新字符赋值给 C，然后将 P 和 C 合并为字符串 P+C。
字典查找：检查 P+C 是否在字典中：
重复处理：返回第 2 步，继续处理下一个字符，直到整个输入字符串处理完毕。
到达字符串尾部，没有新的 C 读入时，则将 P 对应的符号输出，结束。
LZW 编码的关键就在第 3 步 —— 理解变量 P 是什么。P 是当前维护的、可以被编码为符号的子串，但还没有输出。随着每读入一个新字符 C，我们尝试把它加到 P 的末尾，形成新的组合 P+C。只要这个组合还能在字典中找到，我们就不断更新 P = P+C，也就是说，我们在试图找到尽可能长的子串将其编码为一个符号，这就是压缩的实现。一旦 P+C 不在字典里了，就意味着当前这段子串没办法再长了。此时我们：
通过这种方式，我们就能把较长、重复的子串用一个符号表示，从而达到压缩的效果。至于为什么输出的是 P，是因为 P+C 还没被收录进字典，还没有符号可以输出。只能把已有的 P 输出，再把 P+C 加进去，以备后面用到。
举个例子，对于一个字符串：ababnababan，初始状态字典里有三个默认的映射，如表 1.1 所示：
开始编码，编码步骤如表 1.2 所示：
输出的结果为 0132372，完整的字典如表 1.3 所示：
图 1.2 展示原字符串是如何对应到压缩后的编码，图 1.3 展示 LZW 编码如何保存映射到字典中。
读到这里，可能大家有一个疑惑，为什么要这么设计字典映射与编码？这其实都是为解码做准备，解码的过程比编码复杂，其核心思想在于解码需要还原出编码时的用的字典，即如何对应编码的过程。
在 LZW 解码中，输入是压缩后的符号流（Symbol Stream）。和编码类似，解码过程也维护两个变量：
这里的“W”可以理解为一个符号。每个符号代表一个已知的字符串片段。用 Str(cW) 和 Str(pW) 表示它们解码出来的原字符串。
显然，第 5 步是解码过程的关键，也是最难理解的一步。在这一阶段，解码器不仅在解析符号，更重要的是它一边解码，一边模拟编码时的字典构建过程。下面详细阐述 0132372 解码成 ababnababan 的流程：
与编码一样，解码时初始状态字典里只有三个默认的映射，如表 1.4 所示：
开始解码，解码步骤如表 1.5 所示：
仔细观察新映射是如何添加到字典中的，我们可以看到，解码器其实是在一步步“重演”编码器的操作，从而还原出编码过程。
如果新读入的 cW 能在字典里找到，那就能直接解码 cW，然后一边解码（输出 Str(cW)），一边构建新的映射（Str(pW) + Str(cW) 第一个字符）。
如果 cW 不在字典中，这时就需要解码器做出一个推理，我们来看 Step 6：
cW=7，7 还没出现在字典里，但根据之前 cW 能在字典找到的情况，解码器可以推理出 7 映射的新字符串应该是当前的 Str(pW)，也就是 ab，以及未知的 Str(cW) 第一个字符拼接而成。而 cW 映射的就是这个即将新加入的字符串：Str(pW) + Str(cW)[0]，所以 cW 的第一个字符就是 Str(pW) 的第一个字符 a，所以 Str(cW) = aba。
知道了怎么处理，现在思考为什么 cW 解码时，其还没有在字典里建立映射？因为字典中新条目总是比编码“晚一步”生成，如表 1.6 所示，编码器在输出某个符号时，已经读取了后面的字符，并基于它构建了下一条字典项。
而解码则不同，如表 1.7 所示，解码器先读符号再解码，根据解码的结果构建映射。
所以编码器写入字典的映射，解码器总要等到下一轮才会写入。而当要新增的映射恰好在同一轮被引用时，就出现了先拿到符号但是还没建立这个映射的情况。这其实就是遇到了编码器刚刚创建但还没来得及传达其含义的字典项。这时就需要根据当前上下文，靠 Str(pW) + Str(pW)[0] 来还原原意。
以上的分析主要基于英文文本的压缩场景。那么在中文语境下，LZW 又该如何应用呢？首先我们得分析中文文本和西文文本的不同之处：
对 LZW 算法的中文文本压缩的应用而言，最简单的做法是直接套用通用的 LZW 算法。但这方法缺点在于通用算法以字节为基本处理单位，压缩过程中会人为地割裂中文数据编码中蕴含的语义信息，导致压缩比偏低。对此，徐秉铮、华强等人从数据读取方式和基础码集结构出发，调整算法以适配汉字的编码和大字符集特性，压缩效果有所提升，但仍远低于 LZW 算法对英文文本的压缩比。陈庆辉等人在现有基础算法上进行改进，提高了由于中文文本中重复字串不长导致压缩比远低于英文文本的压缩比例，压缩效果显著增强。
本文采用陈庆辉等人的中文文本压缩算法，其算法基于最大字典编码长度为 19 位的 LZW 传统算法，将 GB2312-80 标准字符中的一级汉字和第 1、3 区的常用字符存入初始字典。并针对中文文本重复字串不长的特点，对字典码值进行双模式变长编码输出，具体编码输出方法如下：
按码值的最小二进制表示位数对字典进行分段，则字典可分为 19 段。其中码值 2n−1−1∼2n−1 为字典的第 n 段。记当前字典中码值的最大长度为 n，其中 11<n<20。
这么做的意义在于，大部分数据（常用词）用小编号的码值，而这些码值属于字典的前段。用更短的二进制位表示这些高频码值，就可以整体减少压缩文件的大小。而较大的码值本身出现得少（不常用字符串），即使编码更长，对整体影响也很小。
LZW 算法的解压过程无需在压缩后的数据中添加任何辅助信息就能够自动还原字典，从而保证较快的编解码速度。不过它也不是完美的。其性能容易受到一些因素影响，下面将分析相关影响因素并提出改进方案。需要注意的是，不同的应用场景对压缩效率、速度和资源占用的要求不同，因此改进方法并没有统一的标准，必须根据具体需求选择最合适的方案。
LZW 算法通过构建一个字典，用索引替代重复的字符串，在编码方面：
举个例子压缩 ABABABAB 字符串时，固定长度编码和变长编码差异显著。固定长度编码一开始就用 3 位编码，能表示 8 个索引，但实际初期仅用 4 个，高位闲置，内存浪费；而变长编码初期用 2 位编码，在字典满 4 个条目后，动态扩展为 3 位编码，前期节省编码长度，后期也能处理复杂情况，避免了固定编码的内存浪费。
所以，在内存受限的环境中，更推荐使用变长编码，动态调整每个索引所占的位数，既保证压缩效果，又节省内存和存储空间。
LZW 算法中，字典大小的选择会直接影响压缩效果和处理速度：
因此，字典大小的设置要根据应用场景权衡：
需要注意的是：字典大小主要影响压缩过程。而在解压时，只需按编码值查表恢复原始字符串，不涉及复杂匹配，因此对字典大小不太敏感。
LZW 算法的核心在于字典的构建和查找，其性能高度依赖于搜索效率。不同的搜索方式直接影响压缩和解压的速度与资源消耗。常见的三种搜索方式包括：串行搜索、并行搜索和哈希表搜索。
串行搜索
串行搜索是最基础的做法。每次查找新子串时，从字典头部开始一项一项地查找，直到找到匹配项或遍历完整个字典。这种简单，但在字典较大时效率很低，压缩速度慢。
并行搜索
将整个字典拆分为多个子字典，每个子字典可以独立、同时进行查找。这样可以并行处理多个搜索请求，提高速度。通常，第一个子字典为“虚拟字典”，只记录基本字符（如 0–255），不占内存。其余子字典按照不同的字宽（表示的子串长度）划分，可以分布在不同的硬件单元上并行查找，从而提升处理速度。其缺点是控制逻辑更复杂，每次输出不仅要包含子字典的索引，还要记录其在子字典中的位置，编码格式也更复杂。
哈希表搜索
哈希表搜索通过“前缀字符 + 新字符”组合成一个关键字，再用哈希函数直接计算出字典位置，实现快速定位。这种方法查找速度快，但有两个问题需要注意：
传统的编码方法中，每次只能在已有字符串的基础上增加一个字符来扩展，这种方式效率低下，不仅浪费内存，还拖慢处理速度。可以用其他数据结构重构：
Trie 树（前缀树）
以节点数组的形式存储，从根节点出发的一条路径表示一个字符串。每个节点包含以下三个字段：
当遇到一个未在字典中的字符时，只需将其作为新节点添加到 Trie 树中，并继续扩展构建新的分支。
动态数组 + 哈希表
将字典视为动态扩展的数组，每个条目存储完整字符串及其唯一编码，同时通过哈希表加速字符串查找。
有限自动机（DFA）
将字典转换为确定有限自动机，每个状态对应一个字符串，边表示字符输入后的转移路径，终止状态节点返回对应编码，新增状态生成新条目。
在 LZW 算法中，字典大小在压缩开始前就已经固定，不能根据文件内容动态调整。这意味着，一旦字典被填满，就无法再添加新的字符串，压缩效率也可能随之下降。为了改善这一问题，常见的做法是采用字典更新机制，在不增加字典大小的前提下继续优化压缩效果。以下是几种常见的更新策略：
字典重置（Dictionary Reset, DR）
当字典满了以后，直接清空除初始字典之外的所有条目，重新开始构建字典。DR 实现简单，重置迅速，但每次重置都会丢失所有已有匹配，导致压缩率瞬间降低，整体压缩效果可能变差。
双字典（Double Dictionary, DD）
为了避免重置带来的压缩效率骤降，DD 方法准备两个字典：
当备用字典积累到一定程度后，替换旧字典继续使用，旧字典重置接受。这种方式压缩效率过渡平滑，不会突然降低。但需要双倍字典空间，而且新旧切换时可能丢弃高频出现的字符串。
先进先出（FIFO）
FIFO 方法认为最早加入字典的字符串可能与当前数据相关性较低。当字典满了后，按照“先加入先淘汰”的规则，从旧条目开始逐个替换新的字符串。逻辑简单，无需额外空间。但无法区分高频或低频条目，可能误删仍然有用的字符串，影响压缩效率。
最近最少使用（LRU）
LRU 方法更智能，它记录字典中每个字符串的使用频率，一旦字典满了，就移除使用最少的字符串，空出位置给新内容。其能保留最有用的高频字符串，压缩效果更好。但需要持续跟踪和更新每个条目的使用记录，计算复杂度高，运行开销大。
本文的 LZW 算法实现采用了变长编码、Trie 树结构、哈希表加速查找，并支持最大 19 位字典容量。支持中西文压缩，该算法分别用 Python、Java、JS、Go、C 和 Matlab 实现，并对各版本进行了性能对比测试，评估了其压缩效率和运行速度。
本文的开发环境如表 1.12 所示：
lzw.py
lzw.c
lzw.java
lzw.js
lzw.go
lzw.m
性能测试包括压缩率测试和压缩速度测试，针对 Python、C、Java、JavaScript 和 Go 五个版本进行评估。测试数据集涵盖三类文本：纯英文小说《The Count of Monte Cristo.txt》、中文小说《三体全集.txt》以及中英混合小说《Twilight.txt》。结果如下：
分析结果可知：各语言在三个文本上的压缩率差异很小，几乎一致，对于英文文本压缩率完全相同。至于中英文文本上略有细微差别，Python 在纯中文文本上略低一些。在压缩时间上，C 和 Go 的压缩速度最快，Go 略优于 C，Java 压缩速度最慢，Python 和 JavaScript 表现中等，Python 稍快于 JS。
LZW 算法利用了数据内部的重复模式，无需预先知道数据的概率分布，因此算法结构相对简单。像英文文本和数字图像这样的数据，本身就有很强的重复性（比如相邻字符或像素相似），这使得 LZW 压缩效果特别好。由于这种优势，LZW 被广泛应用于图像和文档格式中，比如 GIF 和 TIFF 图像格式，以及早期的 PDF 文件中，用来压缩图像或文字内容。特别是在 GIF 格式中，LZW 现在仍是核心压缩算法。
GIF（Graphics Interchange Format，图形交换格式）是一种无损压缩的点阵图像格式，由 CompuServe 于 1987 年推出。由美国在线服务公司 CompuServe 于 1987 年开发。它因体积小、易传输，很快成为早期互联网中最流行的图片格式之一。
GIF 的特点包括：
正因为颜色数量有限，GIF 并不适合用来存储照片或色彩渐变丰富的图像，这些场景下不仅压缩效果差，文件反而更大。尽管现在有了更高效的格式如 WebP 和 AVIF，GIF 仍因其兼容性和无需插件的优势，在表情包和轻量级动画中保持着不可替代的地位。
一个 GIF 文件由多个部分组成，每一部分都有特定的功能，共同组成一幅静态图或动画。以下是 GIF 文件的基本结构：
我们以一个具体的 GIF 文件为例，使用十六进制编辑器（如 010 Editor）进行逐段分析，来直观地说明 GIF 文件的各个组成部分。
文件头（前 6 个字节）：47 49 46 38 39 61
签名（3 字节）：47 49 46 → ASCII 对应 "GIF"，说明这是 GIF 文件。
版本号（3 字节）：38 39 61 → ASCII 对应 "89a"，表示使用 1989 年修订版（支持动画、透明色等扩展特性）。
逻辑描述块，包括屏幕描述符和全局颜色表（7+N 字节）：
屏幕尺寸（4 字节）：32 00（宽 50 像素），32 00（高 50 像素）。
标志位（1 字节）：F7（11110111）
第 7 位：1 → 存在全局调色板（Global Color Table）。
第 6-4 位：111 → 该字段表示图像调色板中每种原色（红、绿、蓝）所使用的位数，存储值为实际位数减 1。例如，字段值为 7，表示每个基色占 8 位。理论上，图像最多可表示 (28)3 种颜色（即 24 位真彩色）。
第 3 位：0 → 表示颜色表的排序方式，值为 1 表示颜色按在图像中出现的频率从高到低排序；值为 0 则表示颜色顺序未作特别排序。
第 2-0 位：111 → 全局颜色列表的大小，计算方法是 2n+1，其中 n 为这三个 Bit 的十进制数值，这里代表全局颜色表有 27+1=256 种颜色。
背景颜色索引（1 字节）：F0 → 全局调色板中索引为 240 的颜色作为背景颜色。
像素宽高比（1 字节）：00
全局调色板（256 色，3×256=768 字节）：69 6A 68 6C 6C 6C 64 64 64...
每个颜色由 RGB 三字节组成：69 6A 68 → 深灰色、64 64 64 → 暗灰色...
扩展块（以 0x21 开头，多个子块）
应用扩展（Netscape 动画循环次数，关键子块）：21 FF 0B 4E 45 54 53 43 41 50 45 32 2E 30 03 01 00 00 00
扩展标识符：21 FF → 通用扩展块标识（Application Extension）。
块大小：0B → 后续数据长度为 11 字节。
应用标识符：4E 45 54 53 43 41 50 45 32 2E 30 → "NETSCAPE2.0"（Netscape 浏览器自定义扩展）。
循环次数：03 01 00 00，第 3、4 字节表示 gif 的循环播放次数，如果是 0x0000 表示无限循环。
图形控制扩展（控制单帧显示效果）：21 F9 04 00 32 00 00 00
扩展标识符：21F9 → 图形控制扩展（Graphic Control Extension）。
块大小：04 → 后续 4 字节为有效数据。
标志位：00 → 该帧未启用透明色（第 6–5 位为 00），处置方式为“无操作”（第 2–0 位为 000），即当前帧显示后不清除，下一帧直接覆盖显示在其上。
延迟时间：32 00 → 小端序 0x0032，每帧显示 500 毫秒。
透明颜色索引：00。
图像数据块（以 0x2C 开头，单帧图像）
图像标识符（1 字节）：2C。
图像位置（4 字节，小端序）：00 00 00 00 → X=0 像素，Y=0 像素（图像左上角位于屏幕原点）。
图像大小（4 字节，小端序）：32 00 32 00 → 宽度=200 像素，高度=174 像素（与屏幕尺寸一致，无裁剪或偏移）。
LZW 数据块：08 FF 00 11 08 1C 48 B0 60 82 83 02 A1... FF .... FF ... 00
初始字典大小：08→ 表示 LZW 算法初始编码表大小为 28=256。
压缩数据：LZW 算法生成的编码流，有多个子块构成，子块首字节表示该子块长度（1 字节，1 ≤ n ≤ 255），后跟 n 字节的压缩数据，多个子块依次排列。最后以 00 作为整个LZW 数据块结束符。
文件结束符（最后 1 字节）：3B → GIF 文件结束标志。
整体结构图如图 2.3 所示：
那么 LZW 对什么数据进行压缩呢？GIF 图像通过全局/局部调色板表示颜色，每个像素不直接存储 RGB 值，而是存储一个索引，指向调色板中的颜色。LZW 压缩的对象正是这些颜色索引值的序列。在保存为 GIF 格式时，图像像素首先被转换为调色板索引，然后这组索引作为输入数据传入 LZW 编码器进行压缩。压缩后的结果就是写入 GIF 文件中的图像数据部分。
在当今高度重视隐私和网络安全的社会背景下，压缩算法作为一种可逆过程，本身并不具备安全性。一旦压缩数据被获取，就可以被还原为原始内容。因此，如何保护压缩数据的安全性成为一个研究课题。
最直接的方法是“先压缩，后加密”，将压缩和加密作为两个独立步骤处理。但这种做法效率较低，尤其在对实时性要求较高的场景中，表现不佳。
为提高处理效率，越来越多的研究聚焦于压缩与加密的融合，即在压缩过程中直接引入加密机制，实现同步压缩与加密。许多学者在这一方向上提出了不同的改进方案，以下将介绍几种典型的 LZW 加密压缩联合方法。
这种方法通过对 LZW 字典按特定规则重新排序，实现加密效果。由于字典顺序被打乱，常规的解码器难以预测索引，只有掌握置乱规则的人才能正确还原原始数据。以下以 Zhou 等人于 2008 年提出的方法为例：该方法将 LZW 字典构建为二维数组结构，并在压缩过程中不断对字典内容进行置乱，从而实现压缩与加密同步进行。
使用固定编码长度为 b 位的字典，b 是一个偶数，这里选择 b=12，即字典大小为 4096。首先创建初始字典，将初始字符通过带密钥的哈希函数随机插入到字典中。在加密压缩过程中，首先对明文执行标准的 LZW 压缩。唯一的区别在于：当需要将新字符串 P+C 添加到字典时，不再顺序插入，而是通过带密钥的哈希函数随机选择一个空位置插入。每次添加之后，对整个字典进行置乱处理。具体做法如下：
以 b=4,c1=2,c2=3,r1=1,r2=2 为例，置乱过程如图 3.1 所示：
在所有字符完成压缩加密后，解密与解压缩过程依赖相同的密钥来重构与编码时一致的字典顺序。由于插入位置是通过带密钥的哈希函数确定的，未持有密钥的攻击者无法准确还原字典结构，因此无法解密数据。
除此之外，整个算法由包括两部分，除了改进的 LZW 算法外，还有一个密钥调度程序（Key Scheduling Algorithm），其功能就是产生出指定位数密钥流，密钥流一部分来实施安全压缩，另一部分作为掩码用于与结果数据进行异或。算法原理图如图 3.2 所示。
接下来我们从两个方面对方案进行分析，首先是方案安全性：
接下来是效率方面，该方案由于字典条目是随机插入和置换的，索引无法递增，只能固定用 b 位编码，相比于原始 LZW 的可变长度编码，效率损失明显。
此处仅展示 Python 的参考实现。哈希函数采用 SHA256，密钥流由 128 位 RC4 流密码生成。通过维护一个空位索引列表，并结合带密钥的哈希函数进行随机选择，实现了在数组中高效且精确地定位可用插入位置。采用字典重置方式进行字典更新。
2011 年，Li 等人分析了该方案的算法安全性，指出其存在缺陷，并给出了可行的选择明文攻击和选择密文攻击方法。下面我们将对这一攻击过程进行复现与验证。
Zhou 等人的方法建立在两个安全前提之上：
但当我们只关注字典中的 “单符号初始条目”（初始字典里预先存好的单个字符，如字母 a、b、c 等），Zhou 的两个假设就不成立了。原因在于单符号条目的特殊性：
因此我们可以发现：如果两个任意明文中第 i 个被编号的字符串（Si, Si ′）在字典中是单符号，那么只有当这两个符号完全相同时，他们的密文索引 Bi 和 Bi ′ 才会相同。
证明：由于初始条目的置换方式仅由密钥决定，且该密钥在整个加密压缩过程中保持不变，因此所有初始单符号的排列顺序在整个过程中都是固定的。设 Si 和 Si ′ 是两个不同明文的第i个被编码字符串，如果它们都是单个符号 a，那么在经历 i 次编码后，两个对应的字典 Di 和 Di ′ 中，符号 a 的索引位置是相同的，即 Di(a)=Di ′(a)。密文索引的计算方式为 Di(a)⊕Ki。由于异或操作是可逆的，且密钥流 Ki 相同，那么只要 Si=Si ′，就有 Bi=Bi ′。反过来说，如果 Bi=Bi ′，也可以推出 Si=Si ′。
利用上述定理，攻击者可以发起针对单符号条目的选择明文攻击，步骤如下：
选择密文攻击的思路和之前的“选择明文攻击”类似，但攻击者的操作方向相反，虽然步骤比“选择明文攻击”多（效率低一点），但依然能破解单符号密文。
攻击者的目标仍是识别哪些密文索引对应单符号条目。但因为字典里有些位置是空的（无效条目），攻击者没法直接知道哪些密文对应有效的单符号，所以得逐步试探：
攻击效果：
虽然这种攻击只能直接破解单字符对应的密文（如字母、空格等），但由于单字符在明文中出现频率很高，尤其常见于文本开头，攻击者可以通过查找表“对号入座”，轻松还原这些字符，造成信息泄露。字典越小，单符号出现越频繁，泄露风险越大。尽管攻击对多字符字符串效果较弱，但只要能还原开头部分，就可能暴露关键信息，且结合语言模式还可能进一步推测后续内容。
攻击局限性：
攻击效果受限于字典大小和明文特性：理论上，如果字典已存满所有可能的两字符组合（如aa、ab等），LZW 会优先使用这些更长的词条进行编码，导致单字符的密文索引 Bi 不再出现，使查找表无法继续扩展。但在实际应用中，这种情况极少发生。一方面，自然语言中的两字符组合数量有限，很多组合根本不会出现；另一方面，字典容量通常不足以容纳所有两字符组合。因此，字典“完全覆盖两字符字符串”的情况要么不可能，要么极为罕见。
对图像无效：因为图像中的多符号字符串（比如连续像素组合）长度不固定，且泄露的单个像素无法还原图像结构（比如一个像素的颜色无法推断整幅图的内容），因此该算法可能仍适用于图像加密。
攻击脚本（Python）：
该方案核心漏洞是“单符号密文索引 Bi 不依赖明文”。改进的关键是让算法的行为与明文绑定，破坏这种独立性。有以下几种改进思路：
那么代价是什么呢？这些改进会带来两个问题：
该方法建立多个有相同条目但条目顺序不同的字典，每次压缩时随机选择其中一个字典进行最长匹配，并输出索引。由于相同的字符串在不同字典中的位置不同，只有知道每一步使用的是哪个字典，才能正确解码。这种方法称为 RDT（Randomized Dictionary Table）算法。
为了实现这一点，Xie 等人于 2005 年在 LZ78 算法的基础上，提出基于一种具有不同入口序的多字典表编码方法，算法生成一个伪随机字典选择序列作为密钥，该序列由伪随机位生成器（PRBG）生成，仅需一个短小的种子即可驱动。整个过程类似流式加密，但密钥流不是用于异或操作，而是用于控制字典选择。字典的初始化和更新策略大致思路是对字典初始条目进行随机置乱，使用密钥控制置乱过程。新条目插入到随机位置，同时将原位置的条目移至当前字典的末尾，当字典满时，这就等同于用新条目替换字典中的一个随机条目。具体步骤如下：
这里仅给出 python 的实现，仅作参考。伪随机数生成器使用 RC4 算法；初始字典置乱算法使用 RC4 + Fisher-Yates 算法。
Xie 的方案同样存在可被单字符攻击利用的漏洞。由于每次编码输出前缀索引后，字典的随机选择仅由密钥决定，与明文无关，因此单字符在每次随机选择后的字典中的位置是相对固定的。攻击者可以遍历 n 步随机字典选择路径，构建单字符前缀的查找表，从而还原出部分明文信息，造成信息泄露。
攻击脚本（Python）：
除了前述方法，LZW 的联合压缩加密还有许多其他研究。例如，Hermassi 等人利用混沌映射生成密钥流，动态更新 Huffman 树，使得同一符号可以对应多个等长但不同的编码，提高了安全性；Liu 等人则提出了一种改进的 Huffman 树突变机制，通过仅修改内结点，避免了每次突变后对整棵树重新编码的开销。
由于篇幅有限，这里不再逐一展开。如果有小伙伴对方法感兴趣，后续我会专门写一篇文章进行深入讲解。
目前 LZW 算法的研究主要集中在两个方向：
一是压缩性能的优化。现有很多改进方案要么压缩速度快但压缩率低，要么压缩率有所提升但处理速度下降，很难两者兼顾。
二是压缩与加密的结合。目前的联合加密方案也普遍存在效率与安全难以兼顾的问题，比如：
如何在保证安全的前提下，实现高效压缩，仍是 LZW 研究中的一个重要难题。
参考资料：
可能是最通俗的Lempel-Ziv-Welch (LZW)无损压缩算法详述
你真的了解 gif 吗？分析 gif 文件和一些奇怪的 gif 特性
GIF Codec – LZW Compression Algorithm 12月 20 2017 LZW算法
参考文献：
[1] 徐秉铮,吴立忠,Victor,等. 中文文本压缩的LZW算法[J]. 华南理工大学学报（自然科学版）,1989,17(3): 1-9.
[2] 华强. 中西文文本压缩的LZWCH算法[J]. 计算机工程与应用,1999,(3): 22-23,35.
[3] 陈庆辉,陈小松,韩德良. 中文文本压缩的LZW算法[J]. 计算机工程与应用,2014,(3): 112-116.
[4] 武彦霞. 基于LZW字典压缩算法的改进研究[D]. 江苏科技大学,2024.
[5] 肖志文,陈伟,梁久祯,等. 基于LZW算法的中文文本压缩算法[C]//2007北京地区高校研究生学术交流会通信与信息技术会议. 2008-01.
[6] 王安. 基于LZW压缩算法的数字图像加密研究[D]. 重庆大学,2013.
[7] 成小勇. LZW数据压缩的改进与加密研究[D]. 东南大学,2022.
[8] Dahua Xie, C.-C. Jay Kuo. Secure Lempel-Ziv Compression with Embedded Encryption[J]. Proc. SPIE, 2005, 5681:318-327.
[9] Jiantao Zhou, Oscar C. Au, Xiaopeng Fan and P. Hon-Wah Wong. Secure Lempel-Ziv-Welch (LZW) algorithm with random dictionary insertion and permutation[C] in Proceedings of 2008 IEEE International Conference on Multimedia and Expo (ICME`2008), 2008, 245-248.
[10] Shujun Li, Chengqing Li, J. C.‑C. Kuo. On the security of a secure Lempel–Ziv–Welch (LZW) algorithm[C]//Proc. 2011 IEEE Int. Conf. on Multimedia and Expo (ICME), Barcelona, Spain, 2011: 1–5.
[11] Hermassi H, Rhouma R, Belghith S. Joint compression and encryption using chaotically mutated Huffman trees[J]. Communications in Nonlinear Science & Numerical Simulation, 2010, 15(10): 2987-2999.
[12] Liu Y, Li B, Zhang Y, et al. A Huffman-Based Joint Compression and Encryption Scheme for Secure Data Storage Using Physical Unclonable Functions[J]. Electronics, 2021, 10(11): 1267.
| Symbol | String |
|---|---|
| 0 | a |
| 1 | b |
| 2 | n |
| Step | P | C | P+C | P+C in Dict ？ | Action | Output |
|---|---|---|---|---|---|---|
| 1 | - | a | a | Yes | 更新 P=a | - |
| 2 | a | b | ab | No | 添加 3 → ab，更新 P=b | 0 |
| 3 | b | a | ba | No | 添加 4 → ba，更新 P=a | 1 |
| 4 | a | b | ab | Yes | 更新 P=ab | - |
| 5 | ab | n | abn | No | 添加 5 → abn，更新 P=n | 3 |
| 6 | n | a | na | No | 添加 6 → na，更新 P=a | 2 |
| 7 | a | b | ab | Yes | 更新 P=ab | - |
| 8 | ab | a | aba | No | 添加 7 → aba，更新 P=a | 3 |
| 9 | a | b | ab | Yes | 更新 P=ab | - |
| 10 | ab | a | aba | Yes | 更新 P=aba | - |
| 11 | aba | n | aban | No | 添加 8 → aban，更新 P=n | 7 |
| 12 | n | - | - | - | - | 2 |
| Symbol | String |
|---|---|
| 0 | a |
| 1 | b |
| 2 | n |
| 3 | ab |
| 4 | ba |
| 5 | abn |
| 6 | na |
| 7 | aba |
| 8 | aban |
| Symbol | String |
|---|---|
| 0 | a |
| 1 | b |
| 2 | n |
| Step | pW | cW | cW in Dict ？ | Action | Output |
|---|---|---|---|---|---|
| 1 | - | 0 | Yes | C=a，pW=0 | a |
| 2 | 0 | 1 | Yes | P=a，C=b，P+C=ab，添加 3 → ab | b |
| 3 | 1 | 3 | Yes | P=b，C=a，P+C=ba，添加 4 → ba | ab |
| 4 | 3 | 2 | Yes | P=ab，C=n，P+C=abn，添加 5 → abn | n |
| 5 | 2 | 3 | Yes | P=n，C=a，P+C=na，添加 6 → an | ab |
| 6 | 3 | 7 | No | P=ab，C=a，P+C=aba，添加 7 → aba | aba |
| 7 | 7 | 2 | Yes | P=aba，C=n，P+C=aban，添加 8 → aban | n |
| Step | 已有字符串 P | 读到的字符 C | Output | 新增映射 |
|---|---|---|---|---|
| 1 | a | b | 0 (a → 0) | 添加 3 → ab |
| 2 | b | a | 1 (b → 1) | 添加 4 → ba |
| 3 | ab | n | 3 (ab → 3) | 添加 5 → abn |
| 4 | n | a | 2 (n → 2) | 添加 6 → na |
| 5 | ab | a | 3 (ab → 3) | 添加 7 → aba |
| 6 | aba | n | 7 (aba → 7) | 添加 8 → aban |
| 7 | n | - | 2 (n → 2) | - |
| Step | 读到的字符 | 字典是否存在 | Output | 新增映射 |
|---|---|---|---|---|
| 1 | 0 | Yes | a | - |
| 2 | 1 | Yes | b | 添加 3 → ab |
| 3 | 3 | Yes | ab | 添加 4 → ba |
| 4 | 2 | Yes | n | 添加 5 → abn |
| 5 | 3 | Yes | ab | 添加 6 → an |
| 6 | 7 | No | ab + a | 添加 7 → aba |
| 7 | 2 | Yes | n | 添加 8 → aban |
| 比较维度 | 西文文本 | 中文文本 |
|---|---|---|
| 字符集与编码 | 字符集小，编码简单，单字符占字节少 | 字符集大，编码复杂，单字符占字节多 |
| 语言结构与语法规则 | 词与词间用空格等分隔符分开，词边界清晰，语法规则固定 | 需分词，语法灵活，分析难度大 |
| 统计特性 | 字符出现频率相对分散，不同字符使用频率有差异但不悬殊 | 不同汉字使用频率差异极大，常用字频率高，生僻字频率低 |
| 搜索方式 | 优点 | 缺点 |
|---|---|---|
| 串行搜索 | 逻辑简单、易于实现 | 搜索延时长、占用硬件资源较多 |
| 并行搜索 | 搜索速度快、存储单元利用率高 | 控制逻辑复杂、编码复杂 |
| Hash 表搜索 | 搜索延时短、实时性强 | 占用硬件资源、存在哈希冲突（无法避免） |
| 存储结构 | 使用场景 | 优点 | 缺点 |
|---|---|---|---|
| Trie 树 | 高频前缀重复的短字符串 内存充足场景 | 天然支持前缀匹配 无需处理哈希冲突 插入/查询复杂度稳定 | 内存占用高 字符集大时空间爆炸（如Unicode） |
| 动态数组+哈希表 | 通用文本压缩 中等规模数据 | 查找速度快 动态扩展灵活 实现简单 | 哈希冲突影响性能 内存占用较高（需存储完整字符串） |
| 有限自动机（DFA） | 高吞吐量实时压缩（如网络流） 固定模式字符串快速匹配 | 状态转移加速匹配 适合硬件加速 | 构建和维护复杂度高 内存占用极高 |
| 更新方式 | 优点 | 缺点 |
|---|---|---|
| DR | 简单、快速 | 压缩比波动大 |
| DD | 平滑过渡 | 占用双倍内存 |
| FIFO | 实现容易 | 容易误删高频条目 |
| LRU | 压缩率高 | 实现复杂，速度慢 |
| 语言 | 版本 |
|---|---|
| Python | 3.10.2 |
| GCC | 8.1.0 |
| Java | 23.0.1 |
| JavaScript | 20.18.1 |
| Go | 1.24.2 |
| Matlab | - |
import sysimport osimport timefrom collections import deque# 常量定义MAX_BITS = 19MAX_SIZE = 1 << MAX_BITS # 524288CHINESE_DICT = "的一是了我不人在他有这个上们来到时大地为子中你说生国年着就那和要她出也得里后自以会家可下而过天去能对小多然于心学么之都好看起发当没成只如事把还用第样道想作种开美总从无情己面最女但现前些所同日手又行意动\ 方期它头经长儿回位分爱老因很给名法间斯知世什两次使身者被高已亲其进此话常与活正感见明问力理尔点文几定本公特做外孩相西果走将月十实向声车全信重三机工物气每并别真打太新比才便夫再书部水像眼等体却加电主界门\ 利海受听表德少克代员许稜先口由死安写性马光白或住难望教命花结乐色更拉东神记处让母父应直字场平报友关放至张认接告入笑内英军候民岁往何度山觉路带万男边风解叫任金快原吃妈变通师立象数四失满战远格士音轻目条呢\ 病始达深完今提求清王化空业思切怎非找片罗钱紶吗语元喜曾离飞科言干流欢约各即指合反题必该论交终林请医晚制球决窢传画保读运及则房早院量苦火布品近坐产答星精视五连司巴奇管类未朋且婚台夜青北队久乎越观落尽形影\ 红爸百令周吧识步希亚术留市半热送兴造谈容极随演收首根讲整式取照办强石古华諣拿计您装似足双妻尼转诉米称丽客南领节衣站黑刻统断福城故历惊脸选包紧争另建维绝树系伤示愿持千史谁准联妇纪基买志静阿诗独复痛消社算\ 义竟确酒需单治卡幸兰念举仅钟怕共毛句息功官待究跟穿室易游程号居考突皮哪费倒价图具刚脑永歌响商礼细专黄块脚味灵改据般破引食仍存众注笔甚某沉血备习校默务土微娘须试怀料调广蜖苏显赛查密议底列富梦错座参八除跑"class LZW: def __init__(self): self.dict_nodes = [] # 存储字典节点 (parent, ch) self.hash_table = {} # 哈希表 (parent, ch) -> index self.queue = deque() # FIFO队列 self.next_code = 0 # 下一个可用索引 def dict_init(self): """初始化字典（包含单字节字符和中文字典）""" self.dict_nodes = [(-1, 0)] + [(0, 0)] * (MAX_SIZE - 1) # 预分配空间 self.hash_table.clear() self.queue.clear() self.next_code = 1 # 初始化单字节字符（0-255） for ch in range(256): self.dict_nodes[self.next_code] = (0, ch) self.hash_table[(0, ch)] = self.next_code self.queue.append(self.next_code) self.next_code += 1 # 初始化中文字典 for c in CHINESE_DICT: utf8_bytes = c.encode('utf-8') parent = 0 for byte in utf8_bytes: key = (parent, byte) if key in self.hash_table: parent = self.hash_table[key] else: self._add_node(parent, byte) def _add_node(self, parent, ch): """内部方法：添加新节点（含FIFO替换）""" if self.next_code < MAX_SIZE: idx = self.next_code self.next_code += 1 else: # FIFO替换旧节点 idx = self.queue.popleft() old_parent, old_ch = self.dict_nodes[idx] del self.hash_table[(old_parent, old_ch)] # 添加新节点 self.dict_nodes[idx] = (parent, ch) self.hash_table[(parent, ch)] = idx self.queue.append(idx) return idx @staticmethod def _pack_bits(codes): """将代码列表打包为位流字节""" bitbuf = 0 bits = 0 out = bytearray() for code in codes: bitbuf = (bitbuf << MAX_BITS) | code bits += MAX_BITS while bits >= 8: bits -= 8 out.append((bitbuf >> bits) & 0xFF) bitbuf &= (1 << bits) - 1 # 保留剩余位 if bits > 0: # 处理剩余位 out.append((bitbuf << (8 - bits)) & 0xFF) return bytes(out) @staticmethod def _unpack_bits(data): """将位流字节解包为代码列表""" codes = [] bitbuf = 0 bits = 0 for byte in data: bitbuf = (bitbuf << 8) | byte bits += 8 while bits >= MAX_BITS: bits -= MAX_BITS codes.append((bitbuf >> bits) & ((1 << MAX_BITS) - 1)) bitbuf &= (1 << bits) - 1 # 保留剩余位 return codes def compress(self, data): """压缩数据""" self.dict_init() codes = [] parent = 0 # 初始父节点为根节点 for byte in data: key = (parent, byte) if key in self.hash_table: parent = self.hash_table[key] else: codes.append(parent) self._add_node(parent, byte) parent = self.hash_table[(0, byte)] # 单字节字符必然存在 if parent != 0: # 输出最后一个父节点 codes.append(parent) return self._pack_bits(codes) def decompress(self, data): """解压数据""" self.dict_init() codes = self._unpack_bits(data) if not codes: return b'' out = [] prev_code = codes[0] # 处理第一个代码 current_str = self._get_string(prev_code) out.append(current_str) first_ch = current_str[0] if current_str else 0 # 处理后续代码 for code in codes[1:]: if code == self.next_code: # 特殊情况处理 prev_str = self._get_string(prev_code) current_str = prev_str + bytes([first_ch]) else: current_str = self._get_string(code) out.append(current_str) first_ch = current_str[0] if current_str else 0 self._add_node(prev_code, first_ch) # 添加新条目 prev_code = code return b''.join(out) def _get_string(self, code): """根据代码获取对应的字符串""" stack = [] cur = code while cur != 0: stack.append(self.dict_nodes[cur][1]) cur = self.dict_nodes[cur][0] stack.reverse() return bytes(stack)def main(): # if len(sys.argv) < 2: # print(f"用法: {sys.argv[0]} <输入文件路径>") # return # input_path = sys.argv[1] input_path = r"D:\tmp\TheCountofMonteCristo.txt" dir_path, filename = os.path.split(input_path) base_name = os.path.splitext(filename)[0] comp_path = os.path.join(dir_path, f"{base_name}.lzw") decomp_path = os.path.join(dir_path, f"{base_name}.dec") # 读取输入文件 with open(input_path, 'rb') as f: in_data = f.read() in_len = len(in_data) # 压缩 lzw = LZW() t0 = time.time() comp_data = lzw.compress(in_data) t1 = time.time() with open(comp_path, 'wb') as f: f.write(comp_data) comp_len = len(comp_data) print(f"压缩完成: {in_len} -> {comp_len} bytes, 用时 {t1-t0:.3f}s") # 解压 lzw = LZW() t2 = time.time() decomp_data = lzw.decompress(comp_data) t3 = time.time() with open(decomp_path, 'wb') as f: f.write(decomp_data) decomp_len = len(decomp_data) print(f"解压完成: {decomp_len} bytes, 用时 {t3-t2:.3f}s") # 校验 if decomp_data == in_data: print("校验通过") else: print("校验失败!")if __name__ == "__main__": main()import sysimport osimport timefrom collections import deque# 常量定义MAX_BITS = 19MAX_SIZE = 1 << MAX_BITS # 524288CHINESE_DICT = "的一是了我不人在他有这个上们来到时大地为子中你说生国年着就那和要她出也得里后自以会家可下而过天去能对小多然于心学么之都好看起发当没成只如事把还用第样道想作种开美总从无情己面最女但现前些所同日手又行意动\ 方期它头经长儿回位分爱老因很给名法间斯知世什两次使身者被高已亲其进此话常与活正感见明问力理尔点文几定本公特做外孩相西果走将月十实向声车全信重三机工物气每并别真打太新比才便夫再书部水像眼等体却加电主界门\ 利海受听表德少克代员许稜先口由死安写性马光白或住难望教命花结乐色更拉东神记处让母父应直字场平报友关放至张认接告入笑内英军候民岁往何度山觉路带万男边风解叫任金快原吃妈变通师立象数四失满战远格士音轻目条呢\ 病始达深完今提求清王化空业思切怎非找片罗钱紶吗语元喜曾离飞科言干流欢约各即指合反题必该论交终林请医晚制球决窢传画保读运及则房早院量苦火布品近坐产答星精视五连司巴奇管类未朋且婚台夜青北队久乎越观落尽形影\ 红爸百令周吧识步希亚术留市半热送兴造谈容极随演收首根讲整式取照办强石古华諣拿计您装似足双妻尼转诉米称丽客南领节衣站黑刻统断福城故历惊脸选包紧争另建维绝树系伤示愿持千史谁准联妇纪基买志静阿诗独复痛消社算\ 义竟确酒需单治卡幸兰念举仅钟怕共毛句息功官待究跟穿室易游程号居考突皮哪费倒价图具刚脑永歌响商礼细专黄块脚味灵改据般破引食仍存众注笔甚某沉血备习校默务土微娘须试怀料调广蜖苏显赛查密议底列富梦错座参八除跑"class LZW: def __init__(self): self.dict_nodes = [] # 存储字典节点 (parent, ch) self.hash_table = {} # 哈希表 (parent, ch) -> index self.queue = deque() # FIFO队列 self.next_code = 0 # 下一个可用索引 def dict_init(self): """初始化字典（包含单字节字符和中文字典）""" self.dict_nodes = [(-1, 0)] + [(0, 0)] * (MAX_SIZE - 1) # 预分配空间 self.hash_table.clear() self.queue.clear() self.next_code = 1 # 初始化单字节字符（0-255） for ch in range(256): self.dict_nodes[self.next_code] = (0, ch) self.hash_table[(0, ch)] = self.next_code self.queue.append(self.next_code) self.next_code += 1 # 初始化中文字典 for c in CHINESE_DICT: utf8_bytes = c.encode('utf-8') parent = 0 for byte in utf8_bytes: key = (parent, byte) if key in self.hash_table: parent = self.hash_table[key] else: self._add_node(parent, byte) def _add_node(self, parent, ch): """内部方法：添加新节点（含FIFO替换）""" if self.next_code < MAX_SIZE: idx = self.next_code self.next_code += 1 else: # FIFO替换旧节点 idx = self.queue.popleft() old_parent, old_ch = self.dict_nodes[idx] del self.hash_table[(old_parent, old_ch)] # 添加新节点 self.dict_nodes[idx] = (parent, ch) self.hash_table[(parent, ch)] = idx self.queue.append(idx) return idx @staticmethod def _pack_bits(codes): """将代码列表打包为位流字节""" bitbuf = 0 bits = 0 out = bytearray() for code in codes: bitbuf = (bitbuf << MAX_BITS) | code bits += MAX_BITS while bits >= 8: bits -= 8 out.append((bitbuf >> bits) & 0xFF) bitbuf &= (1 << bits) - 1 # 保留剩余位 if bits > 0: # 处理剩余位 out.append((bitbuf << (8 - bits)) & 0xFF) return bytes(out) @staticmethod def _unpack_bits(data): """将位流字节解包为代码列表""" codes = [] bitbuf = 0 bits = 0 for byte in data: bitbuf = (bitbuf << 8) | byte bits += 8 while bits >= MAX_BITS: bits -= MAX_BITS codes.append((bitbuf >> bits) & ((1 << MAX_BITS) - 1)) bitbuf &= (1 << bits) - 1 # 保留剩余位 return codes def compress(self, data): """压缩数据""" self.dict_init() codes = [] parent = 0 # 初始父节点为根节点 for byte in data: key = (parent, byte) if key in self.hash_table: parent = self.hash_table[key] else: codes.append(parent) self._add_node(parent, byte) parent = self.hash_table[(0, byte)] # 单字节字符必然存在 if parent != 0: # 输出最后一个父节点 codes.append(parent) return self._pack_bits(codes) def decompress(self, data): """解压数据""" self.dict_init() codes = self._unpack_bits(data) if not codes: return b'' out = [] prev_code = codes[0] # 处理第一个代码 current_str = self._get_string(prev_code) out.append(current_str) first_ch = current_str[0] if current_str else 0 # 处理后续代码 for code in codes[1:]: if code == self.next_code: # 特殊情况处理 prev_str = self._get_string(prev_code) current_str = prev_str + bytes([first_ch]) else: current_str = self._get_string(code) out.append(current_str) first_ch = current_str[0] if current_str else 0 self._add_node(prev_code, first_ch) # 添加新条目 prev_code = code return b''.join(out) def _get_string(self, code): """根据代码获取对应的字符串""" stack = [] cur = code while cur != 0: stack.append(self.dict_nodes[cur][1]) cur = self.dict_nodes[cur][0] stack.reverse() return bytes(stack)def main(): # if len(sys.argv) < 2: # print(f"用法: {sys.argv[0]} <输入文件路径>") # return # input_path = sys.argv[1] input_path = r"D:\tmp\TheCountofMonteCristo.txt" dir_path, filename = os.path.split(input_path) base_name = os.path.splitext(filename)[0] comp_path = os.path.join(dir_path, f"{base_name}.lzw") decomp_path = os.path.join(dir_path, f"{base_name}.dec") # 读取输入文件 with open(input_path, 'rb') as f: in_data = f.read() in_len = len(in_data) # 压缩 lzw = LZW() t0 = time.time() comp_data = lzw.compress(in_data) t1 = time.time() with open(comp_path, 'wb') as f: f.write(comp_data) comp_len = len(comp_data) print(f"压缩完成: {in_len} -> {comp_len} bytes, 用时 {t1-t0:.3f}s") # 解压 lzw = LZW() t2 = time.time() decomp_data = lzw.decompress(comp_data) t3 = time.time() with open(decomp_path, 'wb') as f: f.write(decomp_data) decomp_len = len(decomp_data) print(f"解压完成: {decomp_len} bytes, 用时 {t3-t2:.3f}s") # 校验 if decomp_data == in_data: print("校验通过") else: print("校验失败!")if __name__ == "__main__": main()/* * lzw_fast.c —— LZW 压缩/解压（变长编码，19 bit，FIFO 替换，哈希表查询，Trie 树结构），支持中文初始字典 * 编译： gcc -std=c99 -O3 -o lzw_fast lzw_fast.c */#include <stdio.h>#include <stdlib.h>#include <stdint.h>#include <string.h>#include <time.h>#include <ctype.h>#include <windows.h>#include <wchar.h>#include <locale.h>/* ---------- 参数与宏 ---------- */#define MAX_BITS 19#define MAX_SIZE (1u << MAX_BITS) /* 524 288 */#define HASH_SIZE (1u << 20) /* 1 048 576，需为 2^n *//* ---------- 数据结构 ---------- */typedef struct{ int32_t parent; /* 父节点索引，-1 表示根 */ uint8_t ch; /* 本节点对应字符（0‑255） */} Node;/* ---------- 函数原型声明 ---------- */static void dict_init(void);static int32_t add_node(int32_t parent, uint8_t ch);static void pack_bits(const int32_t *codes, size_t n, uint8_t **out_buf, size_t *out_len);static int32_t *unpack_bits(const uint8_t *data, size_t len, size_t *out_n);static void compress_file(const uint8_t *in, size_t in_len, uint8_t **out, size_t *out_len);static void decompress_file(const uint8_t *in, size_t in_len, uint8_t **out_buf, size_t *out_len);static uint8_t *read_file(const char *path, size_t *len);static void write_file(const char *path, const uint8_t *buf, size_t len);/* ---------- 全局变量 ---------- */static Node dict[MAX_SIZE]; /* 字典条目数组 */static int32_t hash_parent[HASH_SIZE]; /* 哈希键 (parent,char) */static uint16_t hash_char[HASH_SIZE];static int32_t hash_val[HASH_SIZE]; /* 存入的 index，-1 表示空槽 */static int32_t queue[MAX_SIZE]; /* FIFO 队列保存 index */static int32_t q_head = 0, q_tail = 0; /* 环形队列指针 */static int32_t next_code; /* 下一个可用索引 *//* ---------- 哈希工具 ---------- */static inline uint32_t hash_func(int32_t parent, uint8_t ch){ return ((uint32_t)parent * 131u + ch) & (HASH_SIZE - 1);}static void hash_clear(void){ memset(hash_val, 0xFF, sizeof(hash_val));}static int32_t hash_find(int32_t parent, uint8_t ch){ uint32_t pos = hash_func(parent, ch); while (hash_val[pos] != -1) { if (hash_parent[pos] == parent && hash_char[pos] == ch) return hash_val[pos]; pos = (pos + 1) & (HASH_SIZE - 1); } return -1;}static void hash_insert(int32_t parent, uint8_t ch, int32_t idx){ uint32_t pos = hash_func(parent, ch); while (hash_val[pos] != -1) pos = (pos + 1) & (HASH_SIZE - 1); hash_parent[pos] = parent; hash_char[pos] = ch; hash_val[pos] = idx;}/* ---------- 字典初始化 ---------- */static void dict_init(void){ setlocale(LC_ALL, ""); // 设置本地编码 hash_clear(); dict[0].parent = -1; dict[0].ch = 0; next_code = 1; q_head = q_tail = 0; for (int i = 0; i < 256; ++i) { dict[next_code].parent = 0; dict[next_code].ch = (uint8_t)i; hash_insert(0, (uint8_t)i, next_code); queue[q_tail++] = next_code; ++next_code; } const wchar_t *chinese_dict = L"的一是了我不人在他有这个上们来到时大地为子中你说生国年着就那和要她出也得里后自以会家可下而过天去能对小多然于心学么之都好看起发当没成只如事把还用第样道想作种开美总从无情己面最女但现前些所同日手又行意动\ 方期它头经长儿回位分爱老因很给名法间斯知世什两次使身者被高已亲其进此话常与活正感见明问力理尔点文几定本公特做外孩相西果走将月十实向声车全信重三机工物气每并别真打太新比才便夫再书部水像眼等体却加电主界门\ 利海受听表德少克代员许稜先口由死安写性马光白或住难望教命花结乐色更拉东神记处让母父应直字场平报友关放至张认接告入笑内英军候民岁往何度山觉路带万男边风解叫任金快原吃妈变通师立象数四失满战远格士音轻目条呢\ 病始达深完今提求清王化空业思切怎非找片罗钱紶吗语元喜曾离飞科言干流欢约各即指合反题必该论交终林请医晚制球决窢传画保读运及则房早院量苦火布品近坐产答星精视五连司巴奇管类未朋且婚台夜青北队久乎越观落尽形影\ 红爸百令周吧识步希亚术留市半热送兴造谈容极随演收首根讲整式取照办强石古华諣拿计您装似足双妻尼转诉米称丽客南领节衣站黑刻统断福城故历惊脸选包紧争另建维绝树系伤示愿持千史谁准联妇纪基买志静阿诗独复痛消社算\ 义竟确酒需单治卡幸兰念举仅钟怕共毛句息功官待究跟穿室易游程号居考突皮哪费倒价图具刚脑永歌响商礼细专黄块脚味灵改据般破引食仍存众注笔甚某沉血备习校默务土微娘须试怀料调广蜖苏显赛查密议底列富梦错座参八除跑"; for (const wchar_t *p = chinese_dict; *p; ++p) { char utf8[4] = {0}; int len = wctomb(utf8, *p); int32_t parent = 0; for (int i = 0; i < len; ++i) { int32_t nxt = hash_find(parent, (uint8_t)utf8[i]); if (nxt == -1) nxt = add_node(parent, (uint8_t)utf8[i]); parent = nxt; } }}/* ---------- 添加节点 / FIFO 替换 ---------- */static int32_t add_node(int32_t parent, uint8_t ch){ int32_t idx; if (next_code < MAX_SIZE) { idx = next_code++; } else { idx = queue[q_head]; q_head = (q_head + 1) % MAX_SIZE; int32_t op = dict[idx].parent; uint8_t oc = dict[idx].ch; uint32_t pos = hash_func(op, oc); while (!(hash_parent[pos] == op && hash_char[pos] == oc)) pos = (pos + 1) & (HASH_SIZE - 1); hash_val[pos] = -1; uint32_t nxt = (pos + 1) & (HASH_SIZE - 1); while (hash_val[nxt] != -1) { int32_t tp = hash_parent[nxt]; uint8_t tc = hash_char[nxt]; int32_t tv = hash_val[nxt]; hash_val[nxt] = -1; hash_insert(tp, tc, tv); nxt = (nxt + 1) & (HASH_SIZE - 1); } } dict[idx].parent = parent; dict[idx].ch = ch; hash_insert(parent, ch, idx); queue[q_tail] = idx; q_tail = (q_tail + 1) % MAX_SIZE; return idx;}/* ---------- 位流打包 ---------- */static void pack_bits(const int32_t *codes, size_t n, uint8_t **out_buf, size_t *out_len){ uint32_t bitbuf = 0; int bits = 0; size_t cap = n * (MAX_BITS + 7) / 8 + 4; uint8_t *out = (uint8_t *)malloc(cap); size_t len = 0; for (size_t i = 0; i < n; ++i) { bitbuf = (bitbuf << MAX_BITS) | (uint32_t)codes[i]; bits += MAX_BITS; while (bits >= 8) { bits -= 8; out[len++] = (bitbuf >> bits) & 0xFF; } } if (bits) { out[len++] = (bitbuf << (8 - bits)) & 0xFF; } *out_buf = out; *out_len = len;}/* ---------- 位流拆包 ---------- */static int32_t *unpack_bits(const uint8_t *data, size_t len, size_t *out_n){ size_t cap = len * 8 / MAX_BITS + 4; int32_t *codes = (int32_t *)malloc(cap * sizeof(int32_t)); size_t n = 0; uint32_t bitbuf = 0; int bits = 0; for (size_t i = 0; i < len; ++i) { bitbuf = (bitbuf << 8) | data[i]; bits += 8; while (bits >= MAX_BITS) { bits -= MAX_BITS; codes[n++] = (bitbuf >> bits) & ((1u << MAX_BITS) - 1); } } *out_n = n; return codes;}/* ---------- 压缩 ---------- */static void compress_file(const uint8_t *in, size_t in_len, uint8_t **out, size_t *out_len){ int32_t *codes = (int32_t *)malloc((in_len + 1) * sizeof(int32_t)); size_t n_codes = 0; int32_t parent = 0; for (size_t i = 0; i < in_len; ++i) { uint8_t c = in[i]; int32_t nxt = hash_find(parent, c); if (nxt != -1) { parent = nxt; } else { codes[n_codes++] = parent; add_node(parent, c); parent = hash_find(0, c); } } if (parent != 0) codes[n_codes++] = parent; pack_bits(codes, n_codes, out, out_len); free(codes);}/* ---------- 解压 ---------- */static void decompress_file(const uint8_t *in, size_t in_len, uint8_t **out_buf, size_t *out_len){ size_t n_codes; int32_t *codes = unpack_bits(in, in_len, &n_codes); size_t cap = 4096; uint8_t *out = (uint8_t *)malloc(cap); size_t len = 0; int32_t prev_code = 0; uint8_t first_ch = 0; static uint8_t stack[MAX_SIZE]; int top; for (size_t i = 0; i < n_codes; ++i) { int32_t code = codes[i]; top = 0; int32_t cur = code; if (code == next_code && prev_code != 0) { cur = prev_code; stack[top++] = first_ch; } while (cur != 0) { stack[top++] = dict[cur].ch; cur = dict[cur].parent; } first_ch = stack[top - 1]; if (len + (size_t)top > cap) { do { cap <<= 1; } while (len + (size_t)top > cap); out = (uint8_t *)realloc(out, cap); } for (int j = top - 1; j >= 0; --j) out[len++] = stack[j]; if (prev_code != 0) { add_node(prev_code, first_ch); } prev_code = code; } free(codes); *out_buf = out; *out_len = len;}/* ---------- 文件辅助 ---------- */static uint8_t *read_file(const char *path, size_t *len){ FILE *fp = fopen(path, "rb"); if (!fp) { perror(path); exit(1); } fseek(fp, 0, SEEK_END); *len = ftell(fp); fseek(fp, 0, SEEK_SET); uint8_t *buf = (uint8_t *)malloc(*len); fread(buf, 1, *len, fp); fclose(fp); return buf;}static void write_file(const char *path, const uint8_t *buf, size_t len){ FILE *fp = fopen(path, "wb"); if (!fp) { perror(path); exit(1); } fwrite(buf, 1, len, fp); fclose(fp);}/* ---------- 主程序 ---------- */int main(int argc, char *argv[]){ const char *input_path; char *comp_path, *decomp_path; char *filename, *dir_path, *last_sep, *dot_pos; SetConsoleOutputCP(CP_UTF8); if (argc >= 2) { input_path = argv[1]; } else { fprintf(stderr, "用法: %s <输入文件路径>\n", argv[0]); return 1; } last_sep = strrchr(input_path, '/'); if (!last_sep) last_sep = strrchr(input_path, '\\'); if (last_sep) { size_t dir_len = last_sep - input_path + 1; dir_path = (char *)malloc(dir_len); strncpy(dir_path, input_path, dir_len); filename = last_sep + 1; } else { dir_path = (char *)"."; filename = (char *)input_path; } dot_pos = strrchr(filename, '.'); if (dot_pos) { size_t base_len = dot_pos - filename; char *base_filename = (char *)malloc(base_len + 1); strncpy(base_filename, filename, base_len); base_filename[base_len] = '\0'; filename = base_filename; } size_t fn_len = strlen(filename); comp_path = (char *)malloc(strlen(dir_path) + fn_len + 5); decomp_path = (char *)malloc(strlen(dir_path) + fn_len + 5); snprintf(comp_path, strlen(dir_path) + fn_len + 5, "%s%s.lzw", dir_path, filename); snprintf(decomp_path, strlen(dir_path) + fn_len + 5, "%s%s.dec", dir_path, filename); size_t in_len; uint8_t *in_buf = read_file(input_path, &in_len); dict_init(); clock_t t0 = clock(); uint8_t *comp_buf; size_t comp_len; compress_file(in_buf, in_len, &comp_buf, &comp_len); clock_t t1 = clock(); write_file(comp_path, comp_buf, comp_len); printf("压缩完成: %zu -> %zu bytes, 用时 %.3f s\n", in_len, comp_len, (double)(t1 - t0) / CLOCKS_PER_SEC); dict_init(); clock_t t2 = clock(); uint8_t *decomp_buf; size_t decomp_len; decompress_file(comp_buf, comp_len, &decomp_buf, &decomp_len); clock_t t3 = clock(); write_file(decomp_path, decomp_buf, decomp_len); printf("解压完成: %zu bytes, 用时 %.3f s\n", decomp_len, (double)(t3 - t2) / CLOCKS_PER_SEC); if (decomp_len != in_len || memcmp(in_buf, decomp_buf, in_len) != 0) { fprintf(stderr, "校验失败!\n"); return 1; } puts("校验通过"); free(in_buf); free(comp_buf); free(decomp_buf); free(dir_path); free(comp_path); free(decomp_path); if (dot_pos) free(filename); return 0;}/* * lzw_fast.c —— LZW 压缩/解压（变长编码，19 bit，FIFO 替换，哈希表查询，Trie 树结构），支持中文初始字典 * 编译： gcc -std=c99 -O3 -o lzw_fast lzw_fast.c */#include <stdio.h>#include <stdlib.h>#include <stdint.h>#include <string.h>#include <time.h>#include <ctype.h>#include <windows.h>#include <wchar.h>#include <locale.h>/* ---------- 参数与宏 ---------- */#define MAX_BITS 19#define MAX_SIZE (1u << MAX_BITS) /* 524 288 */#define HASH_SIZE (1u << 20) /* 1 048 576，需为 2^n *//* ---------- 数据结构 ---------- */typedef struct{ int32_t parent; /* 父节点索引，-1 表示根 */ uint8_t ch; /* 本节点对应字符（0‑255） */} Node;/* ---------- 函数原型声明 ---------- */static void dict_init(void);static int32_t add_node(int32_t parent, uint8_t ch);static void pack_bits(const int32_t *codes, size_t n, uint8_t **out_buf, size_t *out_len);static int32_t *unpack_bits(const uint8_t *data, size_t len, size_t *out_n);static void compress_file(const uint8_t *in, size_t in_len, uint8_t **out, size_t *out_len);static void decompress_file(const uint8_t *in, size_t in_len, uint8_t **out_buf, size_t *out_len);static uint8_t *read_file(const char *path, size_t *len);static void write_file(const char *path, const uint8_t *buf, size_t len);/* ---------- 全局变量 ---------- */static Node dict[MAX_SIZE]; /* 字典条目数组 */static int32_t hash_parent[HASH_SIZE]; /* 哈希键 (parent,char) */static uint16_t hash_char[HASH_SIZE];static int32_t hash_val[HASH_SIZE]; /* 存入的 index，-1 表示空槽 */static int32_t queue[MAX_SIZE]; /* FIFO 队列保存 index */static int32_t q_head = 0, q_tail = 0; /* 环形队列指针 */static int32_t next_code; /* 下一个可用索引 *//* ---------- 哈希工具 ---------- */static inline uint32_t hash_func(int32_t parent, uint8_t ch){ return ((uint32_t)parent * 131u + ch) & (HASH_SIZE - 1);}static void hash_clear(void){ memset(hash_val, 0xFF, sizeof(hash_val));}static int32_t hash_find(int32_t parent, uint8_t ch){ uint32_t pos = hash_func(parent, ch); while (hash_val[pos] != -1) { if (hash_parent[pos] == parent && hash_char[pos] == ch) return hash_val[pos]; pos = (pos + 1) & (HASH_SIZE - 1); } return -1;}static void hash_insert(int32_t parent, uint8_t ch, int32_t idx){ uint32_t pos = hash_func(parent, ch); while (hash_val[pos] != -1) pos = (pos + 1) & (HASH_SIZE - 1); hash_parent[pos] = parent; hash_char[pos] = ch; hash_val[pos] = idx;}/* ---------- 字典初始化 ---------- */static void dict_init(void){ setlocale(LC_ALL, ""); // 设置本地编码 hash_clear(); dict[0].parent = -1; dict[0].ch = 0; next_code = 1; q_head = q_tail = 0; for (int i = 0; i < 256; ++i) { dict[next_code].parent = 0; dict[next_code].ch = (uint8_t)i; hash_insert(0, (uint8_t)i, next_code); queue[q_tail++] = next_code; ++next_code; } const wchar_t *chinese_dict = L"的一是了我不人在他有这个上们来到时大地为子中你说生国年着就那和要她出也得里后自以会家可下而过天去能对小多然于心学么之都好看起发当没成只如事把还用第样道想作种开美总从无情己面最女但现前些所同日手又行意动\ 方期它头经长儿回位分爱老因很给名法间斯知世什两次使身者被高已亲其进此话常与活正感见明问力理尔点文几定本公特做外孩相西果走将月十实向声车全信重三机工物气每并别真打太新比才便夫再书部水像眼等体却加电主界门\ 利海受听表德少克代员许稜先口由死安写性马光白或住难望教命花结乐色更拉东神记处让母父应直字场平报友关放至张认接告入笑内英军候民岁往何度山觉路带万男边风解叫任金快原吃妈变通师立象数四失满战远格士音轻目条呢\ 病始达深完今提求清王化空业思切怎非找片罗钱紶吗语元喜曾离飞科言干流欢约各即指合反题必该论交终林请医晚制球决窢传画保读运及则房早院量苦火布品近坐产答星精视五连司巴奇管类未朋且婚台夜青北队久乎越观落尽形影\ 红爸百令周吧识步希亚术留市半热送兴造谈容极随演收首根讲整式取照办强石古华諣拿计您装似足双妻尼转诉米称丽客南领节衣站黑刻统断福城故历惊脸选包紧争另建维绝树系伤示愿持千史谁准联妇纪基买志静阿诗独复痛消社算\ 义竟确酒需单治卡幸兰念举仅钟怕共毛句息功官待究跟穿室易游程号居考突皮哪费倒价图具刚脑永歌响商礼细专黄块脚味灵改据般破引食仍存众注笔甚某沉血备习校默务土微娘须试怀料调广蜖苏显赛查密议底列富梦错座参八除跑"; for (const wchar_t *p = chinese_dict; *p; ++p) { char utf8[4] = {0}; int len = wctomb(utf8, *p); int32_t parent = 0; for (int i = 0; i < len; ++i) { int32_t nxt = hash_find(parent, (uint8_t)utf8[i]); if (nxt == -1) nxt = add_node(parent, (uint8_t)utf8[i]); parent = nxt; } }}/* ---------- 添加节点 / FIFO 替换 ---------- */static int32_t add_node(int32_t parent, uint8_t ch){ int32_t idx; if (next_code < MAX_SIZE) { idx = next_code++; } else { idx = queue[q_head]; q_head = (q_head + 1) % MAX_SIZE; int32_t op = dict[idx].parent; uint8_t oc = dict[idx].ch; uint32_t pos = hash_func(op, oc); while (!(hash_parent[pos] == op && hash_char[pos] == oc)) pos = (pos + 1) & (HASH_SIZE - 1); hash_val[pos] = -1; uint32_t nxt = (pos + 1) & (HASH_SIZE - 1); while (hash_val[nxt] != -1) { int32_t tp = hash_parent[nxt]; uint8_t tc = hash_char[nxt]; int32_t tv = hash_val[nxt]; hash_val[nxt] = -1; hash_insert(tp, tc, tv); nxt = (nxt + 1) & (HASH_SIZE - 1); } } dict[idx].parent = parent; dict[idx].ch = ch; hash_insert(parent, ch, idx); queue[q_tail] = idx; q_tail = (q_tail + 1) % MAX_SIZE; return idx;}/* ---------- 位流打包 ---------- */static void pack_bits(const int32_t *codes, size_t n, uint8_t **out_buf, size_t *out_len){ uint32_t bitbuf = 0; int bits = 0; size_t cap = n * (MAX_BITS + 7) / 8 + 4; uint8_t *out = (uint8_t *)malloc(cap); size_t len = 0; for (size_t i = 0; i < n; ++i) { bitbuf = (bitbuf << MAX_BITS) | (uint32_t)codes[i]; bits += MAX_BITS; while (bits >= 8) { bits -= 8; out[len++] = (bitbuf >> bits) & 0xFF; } } if (bits) { out[len++] = (bitbuf << (8 - bits)) & 0xFF; } *out_buf = out; *out_len = len;}/* ---------- 位流拆包 ---------- */static int32_t *unpack_bits(const uint8_t *data, size_t len, size_t *out_n){ size_t cap = len * 8 / MAX_BITS + 4; int32_t *codes = (int32_t *)malloc(cap * sizeof(int32_t)); size_t n = 0; uint32_t bitbuf = 0; int bits = 0; for (size_t i = 0; i < len; ++i) { bitbuf = (bitbuf << 8) | data[i]; bits += 8; while (bits >= MAX_BITS) { bits -= MAX_BITS; codes[n++] = (bitbuf >> bits) & ((1u << MAX_BITS) - 1); } } *out_n = n; return codes;}/* ---------- 压缩 ---------- */static void compress_file(const uint8_t *in, size_t in_len, uint8_t **out, size_t *out_len){ int32_t *codes = (int32_t *)malloc((in_len + 1) * sizeof(int32_t)); size_t n_codes = 0; int32_t parent = 0; for (size_t i = 0; i < in_len; ++i) { uint8_t c = in[i]; int32_t nxt = hash_find(parent, c); if (nxt != -1) { parent = nxt; } else { codes[n_codes++] = parent; add_node(parent, c); parent = hash_find(0, c); } } if (parent != 0) codes[n_codes++] = parent; pack_bits(codes, n_codes, out, out_len); free(codes);}/* ---------- 解压 ---------- */static void decompress_file(const uint8_t *in, size_t in_len, uint8_t **out_buf, size_t *out_len){ size_t n_codes; int32_t *codes = unpack_bits(in, in_len, &n_codes); size_t cap = 4096; uint8_t *out = (uint8_t *)malloc(cap); size_t len = 0; int32_t prev_code = 0; uint8_t first_ch = 0; static uint8_t stack[MAX_SIZE]; int top; for (size_t i = 0; i < n_codes; ++i) { int32_t code = codes[i]; top = 0; int32_t cur = code; if (code == next_code && prev_code != 0) { cur = prev_code; stack[top++] = first_ch; } while (cur != 0) { stack[top++] = dict[cur].ch; cur = dict[cur].parent; } first_ch = stack[top - 1]; if (len + (size_t)top > cap) { do { cap <<= 1; } while (len + (size_t)top > cap); out = (uint8_t *)realloc(out, cap); } for (int j = top - 1; j >= 0; --j) out[len++] = stack[j]; if (prev_code != 0) { add_node(prev_code, first_ch); } prev_code = code; } free(codes); *out_buf = out; *out_len = len;}/* ---------- 文件辅助 ---------- */static uint8_t *read_file(const char *path, size_t *len){ FILE *fp = fopen(path, "rb"); if (!fp) { perror(path); exit(1); } fseek(fp, 0, SEEK_END); *len = ftell(fp); fseek(fp, 0, SEEK_SET); uint8_t *buf = (uint8_t *)malloc(*len); fread(buf, 1, *len, fp); fclose(fp); return buf;}static void write_file(const char *path, const uint8_t *buf, size_t len){ FILE *fp = fopen(path, "wb"); if (!fp) { perror(path); exit(1); } fwrite(buf, 1, len, fp); fclose(fp);}/* ---------- 主程序 ---------- */int main(int argc, char *argv[]){ const char *input_path; char *comp_path, *decomp_path; char *filename, *dir_path, *last_sep, *dot_pos; SetConsoleOutputCP(CP_UTF8); if (argc >= 2) { input_path = argv[1]; } else { fprintf(stderr, "用法: %s <输入文件路径>\n", argv[0]); return 1; } last_sep = strrchr(input_path, '/'); if (!last_sep) last_sep = strrchr(input_path, '\\'); if (last_sep) { size_t dir_len = last_sep - input_path + 1; dir_path = (char *)malloc(dir_len); strncpy(dir_path, input_path, dir_len); filename = last_sep + 1; } else { dir_path = (char *)"."; filename = (char *)input_path; } dot_pos = strrchr(filename, '.'); if (dot_pos) { size_t base_len = dot_pos - filename; char *base_filename = (char *)malloc(base_len + 1); strncpy(base_filename, filename, base_len); base_filename[base_len] = '\0'; filename = base_filename; } size_t fn_len = strlen(filename); comp_path = (char *)malloc(strlen(dir_path) + fn_len + 5); decomp_path = (char *)malloc(strlen(dir_path) + fn_len + 5); snprintf(comp_path, strlen(dir_path) + fn_len + 5, "%s%s.lzw", dir_path, filename); snprintf(decomp_path, strlen(dir_path) + fn_len + 5, "%s%s.dec", dir_path, filename); size_t in_len; uint8_t *in_buf = read_file(input_path, &in_len); dict_init(); clock_t t0 = clock(); uint8_t *comp_buf; size_t comp_len; compress_file(in_buf, in_len, &comp_buf, &comp_len); clock_t t1 = clock(); write_file(comp_path, comp_buf, comp_len); printf("压缩完成: %zu -> %zu bytes, 用时 %.3f s\n", in_len, comp_len, (double)(t1 - t0) / CLOCKS_PER_SEC); dict_init(); clock_t t2 = clock(); uint8_t *decomp_buf; size_t decomp_len; decompress_file(comp_buf, comp_len, &decomp_buf, &decomp_len); clock_t t3 = clock(); write_file(decomp_path, decomp_buf, decomp_len); printf("解压完成: %zu bytes, 用时 %.3f s\n", decomp_len, (double)(t3 - t2) / CLOCKS_PER_SEC); if (decomp_len != in_len || memcmp(in_buf, decomp_buf, in_len) != 0) { fprintf(stderr, "校验失败!\n"); return 1; } puts("校验通过"); free(in_buf); free(comp_buf); free(decomp_buf); free(dir_path); free(comp_path); free(decomp_path); if (dot_pos) free(filename); return 0;}import java.io.*;import java.nio.file.Files;import java.nio.file.Paths;import java.util.*;public class LZW { private static final int MAX_BITS = 19; private static final int MAX_SIZE = 1 << MAX_BITS; // 524288 private static final int HASH_SIZE = 1 << 20; // 1048576 // 中文字典 private static final String CHINESE_DICT = "的一是了我不人在他有这个上们来到时大地为子中你说生国年着就那和要她出也得里后自以会家可下而过天去能对小多然于心学么之都好看起发当没成只如事把还用第样道想作种开美总从无情己面最女但现前些所同日手又行意动" + "方期它头经长儿回位分爱老因很给名法间斯知世什两次使身者被高已亲其进此话常与活正感见明问力理尔点文几定本公特做外孩相西果走将月十实向声车全信重三机工物气每并别真打太新比才便夫再书部水像眼等体却加电主界门" + "利海受听表德少克代员许稜先口由死安写性马光白或住难望教命花结乐色更拉东神记处让母父应直字场平报友关放至张认接告入笑内英军候民岁往何度山觉路带万男边风解叫任金快原吃妈变通师立象数四失满战远格士音轻目条呢" + "病始达深完今提求清王化空业思切怎非找片罗钱紶吗语元喜曾离飞科言干流欢约各即指合反题必该论交终林请医晚制球决窢传画保读运及则房早院量苦火布品近坐产答星精视五连司巴奇管类未朋且婚台夜青北队久乎越观落尽形影" + "红爸百令周吧识步希亚术留市半热送兴造谈容极随演收首根讲整式取照办强石古华諣拿计您装似足双妻尼转诉米称丽客南领节衣站黑刻统断福城故历惊脸选包紧争另建维绝树系伤示愿持千史谁准联妇纪基买志静阿诗独复痛消社算" + "义竟确酒需单治卡幸兰念举仅钟怕共毛句息功官待究跟穿室易游程号居考突皮哪费倒价图具刚脑永歌响商礼细专黄块脚味灵改据般破引食仍存众注笔甚某沉血备习校默务土微娘须试怀料调广蜖苏显赛查密议底列富梦错座参八除跑"; // 使用原始类型数组替代对象数组，减少内存使用 private final int[] dictParent = new int[MAX_SIZE]; private final byte[] dictChar = new byte[MAX_SIZE]; private final int[] hashParent = new int[HASH_SIZE]; private final byte[] hashChar = new byte[HASH_SIZE]; private final int[] hashVal = new int[HASH_SIZE]; private final int[] queue = new int[MAX_SIZE]; private int qHead = 0, qTail = 0; private int nextCode; // 初始化字典 private void dictInit() { Arrays.fill(hashVal, -1); Arrays.fill(dictParent, -1); Arrays.fill(dictChar, (byte)0); // 初始化根节点 dictParent[0] = -1; dictChar[0] = 0; nextCode = 1; qHead = qTail = 0; // 初始化单字节字符 for (int i = 0; i < 256; i++) { dictParent[nextCode] = 0; dictChar[nextCode] = (byte)i; hashInsert(0, (byte)i, nextCode); queue[qTail++] = nextCode; nextCode++; } // 初始化中文字典 try { for (char c : CHINESE_DICT.toCharArray()) { byte[] utf8 = String.valueOf(c).getBytes("UTF-8"); int parent = 0; for (byte b : utf8) { int next = hashFind(parent, b); if (next == -1) { next = addNode(parent, b); } parent = next; } } } catch (UnsupportedEncodingException e) { System.err.println("UTF-8编码不支持"); } } // 优化的哈希函数 private int hashFunc(int parent, byte ch) { return ((parent * 131 + (ch & 0xFF)) & (HASH_SIZE - 1)); } // 优化的哈希查找 private int hashFind(int parent, byte ch) { int pos = hashFunc(parent, ch); while (hashVal[pos] != -1) { if (hashParent[pos] == parent && hashChar[pos] == ch) { return hashVal[pos]; } pos = (pos + 1) & (HASH_SIZE - 1); } return -1; } // 优化的哈希插入 private void hashInsert(int parent, byte ch, int idx) { int pos = hashFunc(parent, ch); while (hashVal[pos] != -1) { pos = (pos + 1) & (HASH_SIZE - 1); } hashParent[pos] = parent; hashChar[pos] = ch; hashVal[pos] = idx; } // 优化的节点添加 private int addNode(int parent, byte ch) { int idx; if (nextCode < MAX_SIZE) { idx = nextCode++; } else { idx = queue[qHead]; qHead = (qHead + 1) % MAX_SIZE; // 移除旧映射 int oldParent = dictParent[idx]; byte oldCh = dictChar[idx]; int pos = hashFunc(oldParent, oldCh); while (!(hashParent[pos] == oldParent && hashChar[pos] == oldCh)) { pos = (pos + 1) & (HASH_SIZE - 1); } hashVal[pos] = -1; // 重新哈希 int nextPos = (pos + 1) & (HASH_SIZE - 1); while (hashVal[nextPos] != -1) { int tp = hashParent[nextPos]; byte tc = hashChar[nextPos]; int tv = hashVal[nextPos]; hashVal[nextPos] = -1; hashInsert(tp, tc, tv); nextPos = (nextPos + 1) & (HASH_SIZE - 1); } } dictParent[idx] = parent; dictChar[idx] = ch; hashInsert(parent, ch, idx); queue[qTail] = idx; qTail = (qTail + 1) % MAX_SIZE; return idx; } // 优化的位流打包 private byte[] packBits(int[] codes) { ByteArrayOutputStream out = new ByteArrayOutputStream(codes.length * 3); // 预分配空间 int bitBuf = 0; int bits = 0; for (int code : codes) { bitBuf = (bitBuf << MAX_BITS) | (code & ((1 << MAX_BITS) - 1)); bits += MAX_BITS; while (bits >= 8) { bits -= 8; out.write((bitBuf >> bits) & 0xFF); } } if (bits > 0) { out.write((bitBuf << (8 - bits)) & 0xFF); } return out.toByteArray(); } // 优化的位流拆包 private int[] unpackBits(byte[] data) { int[] codes = new int[data.length * 8 / MAX_BITS + 1]; // 预分配空间 int codeCount = 0; int bitBuf = 0; int bits = 0; for (byte b : data) { bitBuf = (bitBuf << 8) | (b & 0xFF); bits += 8; while (bits >= MAX_BITS) { bits -= MAX_BITS; codes[codeCount++] = (bitBuf >> bits) & ((1 << MAX_BITS) - 1); } } return Arrays.copyOf(codes, codeCount); } // 优化的压缩方法 public byte[] compress(byte[] input) { int[] codes = new int[input.length]; // 预分配空间 int codeCount = 0; int parent = 0; for (byte c : input) { int next = hashFind(parent, c); if (next != -1) { parent = next; } else { codes[codeCount++] = parent; addNode(parent, c); parent = hashFind(0, c); } } if (parent != 0) { codes[codeCount++] = parent; } return packBits(Arrays.copyOf(codes, codeCount)); } // 优化的解压方法 public byte[] decompress(byte[] input) { int[] codes = unpackBits(input); ByteArrayOutputStream out = new ByteArrayOutputStream(input.length * 2); // 预分配空间 int prevCode = 0; byte firstCh = 0; byte[] stack = new byte[MAX_SIZE]; for (int code : codes) { int top = 0; int cur = code; if (code == nextCode && prevCode != 0) { cur = prevCode; stack[top++] = firstCh; } while (cur != 0) { stack[top++] = dictChar[cur]; cur = dictParent[cur]; } firstCh = stack[top - 1]; for (int j = top - 1; j >= 0; j--) { out.write(stack[j]); } if (prevCode != 0) { addNode(prevCode, firstCh); } prevCode = code; } return out.toByteArray(); } // 工具方法：读取文件 private static byte[] readFile(String path) throws IOException { return Files.readAllBytes(Paths.get(path)); } // 工具方法：写入文件 private static void writeFile(String path, byte[] data) throws IOException { Files.write(Paths.get(path), data); } public static void main(String[] args) throws IOException { String inputPath; if (args.length == 0) { inputPath = "D:\\test\\Twilight.txt"; System.out.println("未指定输入路径，使用默认路径: " + inputPath); } else if (args.length == 1) { inputPath = args[0]; } else { System.err.println("错误：参数过多，用法: java LZW [输入文件路径]"); return; } String baseName = new File(inputPath).getName().replaceFirst("[.][^.]+$", ""); String compPath = baseName + ".lzw"; String decompPath = baseName + ".dec"; LZW compressor = new LZW(); compressor.dictInit(); // 压缩 byte[] input = readFile(inputPath); long start = System.currentTimeMillis(); byte[] compressed = compressor.compress(input); long compressTime = System.currentTimeMillis() - start; writeFile(compPath, compressed); System.out.printf("压缩完成: %d -> %d bytes, 用时 %.3fs\n", input.length, compressed.length, compressTime / 1000.0); // 解压 compressor = new LZW(); compressor.dictInit(); start = System.currentTimeMillis(); byte[] decompressed = compressor.decompress(compressed); long decompressTime = System.currentTimeMillis() - start; writeFile(decompPath, decompressed); System.out.printf("解压完成: %d bytes, 用时 %.3fs\n", decompressed.length, decompressTime / 1000.0); // 校验 if (Arrays.equals(input, decompressed)) { System.out.println("校验通过"); } else { System.out.println("校验失败!"); } }}import java.io.*;import java.nio.file.Files;import java.nio.file.Paths;import java.util.*;public class LZW { private static final int MAX_BITS = 19; private static final int MAX_SIZE = 1 << MAX_BITS; // 524288 private static final int HASH_SIZE = 1 << 20; // 1048576 // 中文字典 private static final String CHINESE_DICT = "的一是了我不人在他有这个上们来到时大地为子中你说生国年着就那和要她出也得里后自以会家可下而过天去能对小多然于心学么之都好看起发当没成只如事把还用第样道想作种开美总从无情己面最女但现前些所同日手又行意动" + "方期它头经长儿回位分爱老因很给名法间斯知世什两次使身者被高已亲其进此话常与活正感见明问力理尔点文几定本公特做外孩相西果走将月十实向声车全信重三机工物气每并别真打太新比才便夫再书部水像眼等体却加电主界门" + "利海受听表德少克代员许稜先口由死安写性马光白或住难望教命花结乐色更拉东神记处让母父应直字场平报友关放至张认接告入笑内英军候民岁往何度山觉路带万男边风解叫任金快原吃妈变通师立象数四失满战远格士音轻目条呢" + "病始达深完今提求清王化空业思切怎非找片罗钱紶吗语元喜曾离飞科言干流欢约各即指合反题必该论交终林请医晚制球决窢传画保读运及则房早院量苦火布品近坐产答星精视五连司巴奇管类未朋且婚台夜青北队久乎越观落尽形影" + "红爸百令周吧识步希亚术留市半热送兴造谈容极随演收首根讲整式取照办强石古华諣拿计您装似足双妻尼转诉米称丽客南领节衣站黑刻统断福城故历惊脸选包紧争另建维绝树系伤示愿持千史谁准联妇纪基买志静阿诗独复痛消社算" + "义竟确酒需单治卡幸兰念举仅钟怕共毛句息功官待究跟穿室易游程号居考突皮哪费倒价图具刚脑永歌响商礼细专黄块脚味灵改据般破引食仍存众注笔甚某沉血备习校默务土微娘须试怀料调广蜖苏显赛查密议底列富梦错座参八除跑"; // 使用原始类型数组替代对象数组，减少内存使用 private final int[] dictParent = new int[MAX_SIZE]; private final byte[] dictChar = new byte[MAX_SIZE]; private final int[] hashParent = new int[HASH_SIZE]; private final byte[] hashChar = new byte[HASH_SIZE]; private final int[] hashVal = new int[HASH_SIZE]; private final int[] queue = new int[MAX_SIZE]; private int qHead = 0, qTail = 0; private int nextCode; // 初始化字典 private void dictInit() { Arrays.fill(hashVal, -1); Arrays.fill(dictParent, -1); Arrays.fill(dictChar, (byte)0); // 初始化根节点 dictParent[0] = -1; dictChar[0] = 0; nextCode = 1; qHead = qTail = 0; // 初始化单字节字符 for (int i = 0; i < 256; i++) { dictParent[nextCode] = 0; dictChar[nextCode] = (byte)i; hashInsert(0, (byte)i, nextCode); queue[qTail++] = nextCode; nextCode++; } // 初始化中文字典 try { for (char c : CHINESE_DICT.toCharArray()) { byte[] utf8 = String.valueOf(c).getBytes("UTF-8"); int parent = 0; for (byte b : utf8) { int next = hashFind(parent, b); if (next == -1) { next = addNode(parent, b); } parent = next; } } } catch (UnsupportedEncodingException e) { System.err.println("UTF-8编码不支持"); } } // 优化的哈希函数 private int hashFunc(int parent, byte ch) { return ((parent * 131 + (ch & 0xFF)) & (HASH_SIZE - 1)); } // 优化的哈希查找 private int hashFind(int parent, byte ch) { int pos = hashFunc(parent, ch); while (hashVal[pos] != -1) { if (hashParent[pos] == parent && hashChar[pos] == ch) { return hashVal[pos]; } pos = (pos + 1) & (HASH_SIZE - 1); } return -1; } // 优化的哈希插入 private void hashInsert(int parent, byte ch, int idx) { int pos = hashFunc(parent, ch); while (hashVal[pos] != -1) { pos = (pos + 1) & (HASH_SIZE - 1); } hashParent[pos] = parent; hashChar[pos] = ch; hashVal[pos] = idx; } // 优化的节点添加 private int addNode(int parent, byte ch) { int idx; if (nextCode < MAX_SIZE) { idx = nextCode++; } else { idx = queue[qHead]; qHead = (qHead + 1) % MAX_SIZE; // 移除旧映射 int oldParent = dictParent[idx]; byte oldCh = dictChar[idx]; int pos = hashFunc(oldParent, oldCh); while (!(hashParent[pos] == oldParent && hashChar[pos] == oldCh)) { pos = (pos + 1) & (HASH_SIZE - 1); } hashVal[pos] = -1; // 重新哈希 int nextPos = (pos + 1) & (HASH_SIZE - 1); while (hashVal[nextPos] != -1) { int tp = hashParent[nextPos]; byte tc = hashChar[nextPos]; int tv = hashVal[nextPos]; hashVal[nextPos] = -1; hashInsert(tp, tc, tv); nextPos = (nextPos + 1) & (HASH_SIZE - 1); } } dictParent[idx] = parent; dictChar[idx] = ch; hashInsert(parent, ch, idx); queue[qTail] = idx; qTail = (qTail + 1) % MAX_SIZE; return idx; } // 优化的位流打包 private byte[] packBits(int[] codes) { ByteArrayOutputStream out = new ByteArrayOutputStream(codes.length * 3); // 预分配空间 int bitBuf = 0; int bits = 0; for (int code : codes) { bitBuf = (bitBuf << MAX_BITS) | (code & ((1 << MAX_BITS) - 1)); bits += MAX_BITS; while (bits >= 8) { bits -= 8; out.write((bitBuf >> bits) & 0xFF); } } if (bits > 0) { out.write((bitBuf << (8 - bits)) & 0xFF); } return out.toByteArray(); } // 优化的位流拆包 private int[] unpackBits(byte[] data) { int[] codes = new int[data.length * 8 / MAX_BITS + 1]; // 预分配空间 int codeCount = 0; int bitBuf = 0; int bits = 0; for (byte b : data) { bitBuf = (bitBuf << 8) | (b & 0xFF); bits += 8; while (bits >= MAX_BITS) { bits -= MAX_BITS; codes[codeCount++] = (bitBuf >> bits) & ((1 << MAX_BITS) - 1); } } return Arrays.copyOf(codes, codeCount); } // 优化的压缩方法 public byte[] compress(byte[] input) { int[] codes = new int[input.length]; // 预分配空间 int codeCount = 0; int parent = 0; for (byte c : input) { int next = hashFind(parent, c); if (next != -1) { parent = next; } else { codes[codeCount++] = parent; addNode(parent, c); parent = hashFind(0, c); } } if (parent != 0) { codes[codeCount++] = parent; } return packBits(Arrays.copyOf(codes, codeCount)); } // 优化的解压方法 public byte[] decompress(byte[] input) { int[] codes = unpackBits(input); ByteArrayOutputStream out = new ByteArrayOutputStream(input.length * 2); // 预分配空间 int prevCode = 0; byte firstCh = 0; byte[] stack = new byte[MAX_SIZE]; for (int code : codes) { int top = 0; int cur = code; if (code == nextCode && prevCode != 0) { cur = prevCode; stack[top++] = firstCh; } while (cur != 0) { stack[top++] = dictChar[cur]; cur = dictParent[cur]; } firstCh = stack[top - 1]; for (int j = top - 1; j >= 0; j--) { out.write(stack[j]); } if (prevCode != 0) { addNode(prevCode, firstCh); } prevCode = code; } return out.toByteArray(); } // 工具方法：读取文件 private static byte[] readFile(String path) throws IOException { return Files.readAllBytes(Paths.get(path)); } // 工具方法：写入文件 private static void writeFile(String path, byte[] data) throws IOException { Files.write(Paths.get(path), data); } public static void main(String[] args) throws IOException { String inputPath; if (args.length == 0) { inputPath = "D:\\test\\Twilight.txt"; System.out.println("未指定输入路径，使用默认路径: " + inputPath); } else if (args.length == 1) { inputPath = args[0]; } else { System.err.println("错误：参数过多，用法: java LZW [输入文件路径]"); return; } String baseName = new File(inputPath).getName().replaceFirst("[.][^.]+$", ""); String compPath = baseName + ".lzw"; String decompPath = baseName + ".dec"; LZW compressor = new LZW(); compressor.dictInit(); // 压缩 byte[] input = readFile(inputPath); long start = System.currentTimeMillis(); byte[] compressed = compressor.compress(input); long compressTime = System.currentTimeMillis() - start; writeFile(compPath, compressed); System.out.printf("压缩完成: %d -> %d bytes, 用时 %.3fs\n", input.length, compressed.length, compressTime / 1000.0); // 解压 compressor = new LZW(); compressor.dictInit(); start = System.currentTimeMillis(); byte[] decompressed = compressor.decompress(compressed); long decompressTime = System.currentTimeMillis() - start; writeFile(decompPath, decompressed); System.out.printf("解压完成: %d bytes, 用时 %.3fs\n", decompressed.length, decompressTime / 1000.0); // 校验 if (Arrays.equals(input, decompressed)) { System.out.println("校验通过"); } else { System.out.println("校验失败!"); } }}const fs = require('fs');// LZW 压缩器实现class LZW { // 常量定义 static MAX_BITS = 19; static MAX_SIZE = 1 << LZW.MAX_BITS; // 524288 static HASH_SIZE = 1 << 20; // 1048576 // 中文字典 static CHINESE_DICT = "的一是了我不人在他有这个上们来到时大地为子中你说生国年着就那和要她出也得里后自以会家可下而过天去能对小多然于心学么之都好看起发当没成只如事把还用第样道想作种开美总从无情己面最女但现前些所同日手又行意动" + "方期它头经长儿回位分爱老因很给名法间斯知世什两次使身者被高已亲其进此话常与活正感见明问力理尔点文几定本公特做外孩相西果走将月十实向声车全信重三机工物气每并别真打太新比才便夫再书部水像眼等体却加电主界门" + "利海受听表德少克代员许稜先口由死安写性马光白或住难望教命花结乐色更拉东神记处让母父应直字场平报友关放至张认接告入笑内英军候民岁往何度山觉路带万男边风解叫任金快原吃妈变通师立象数四失满战远格士音轻目条呢" + "病始达深完今提求清王化空业思切怎非找片罗钱紶吗语元喜曾离飞科言干流欢约各即指合反题必该论交终林请医晚制球决窢传画保读运及则房早院量苦火布品近坐产答星精视五连司巴奇管类未朋且婚台夜青北队久乎越观落尽形影" + "红爸百令周吧识步希亚术留市半热送兴造谈容极随演收首根讲整式取照办强石古华諣拿计您装似足双妻尼转诉米称丽客南领节衣站黑刻统断福城故历惊脸选包紧争另建维绝树系伤示愿持千史谁准联妇纪基买志静阿诗独复痛消社算" + "义竟确酒需单治卡幸兰念举仅钟怕共毛句息功官待究跟穿室易游程号居考突皮哪费倒价图具刚脑永歌响商礼细专黄块脚味灵改据般破引食仍存众注笔甚某沉血备习校默务土微娘须试怀料调广蜖苏显赛查密议底列富梦错座参八除跑"; constructor() { // 使用 TypedArray 优化性能 this.dictParent = new Int32Array(LZW.MAX_SIZE); this.dictChar = new Uint8Array(LZW.MAX_SIZE); this.hashParent = new Int32Array(LZW.HASH_SIZE); this.hashChar = new Uint8Array(LZW.HASH_SIZE); this.hashVal = new Int32Array(LZW.HASH_SIZE); this.queue = new Int32Array(LZW.MAX_SIZE); this.qHead = 0; this.qTail = 0; this.nextCode = 0; } // 初始化字典 dictInit() { // 初始化数组 this.hashVal.fill(-1); this.dictParent.fill(-1); this.dictChar.fill(0); // 初始化根节点 this.dictParent[0] = -1; this.dictChar[0] = 0; this.nextCode = 1; this.qHead = this.qTail = 0; // 初始化单字节字符 for (let i = 0; i < 256; i++) { this.dictParent[this.nextCode] = 0; this.dictChar[this.nextCode] = i; this.hashInsert(0, i, this.nextCode); this.queue[this.qTail++] = this.nextCode; this.nextCode++; } // 初始化中文字典 for (const c of LZW.CHINESE_DICT) { const utf8 = new TextEncoder().encode(c); let parent = 0; for (const b of utf8) { let next = this.hashFind(parent, b); if (next === -1) { next = this.addNode(parent, b); } parent = next; } } } // 哈希函数 hashFunc(parent, ch) { return ((parent * 131 + ch) & (LZW.HASH_SIZE - 1)); } // 哈希查找 hashFind(parent, ch) { let pos = this.hashFunc(parent, ch); while (this.hashVal[pos] !== -1) { if (this.hashParent[pos] === parent && this.hashChar[pos] === ch) { return this.hashVal[pos]; } pos = (pos + 1) & (LZW.HASH_SIZE - 1); } return -1; } // 哈希插入 hashInsert(parent, ch, idx) { let pos = this.hashFunc(parent, ch); while (this.hashVal[pos] !== -1) { pos = (pos + 1) & (LZW.HASH_SIZE - 1); } this.hashParent[pos] = parent; this.hashChar[pos] = ch; this.hashVal[pos] = idx; } // 添加节点 addNode(parent, ch) { let idx; if (this.nextCode < LZW.MAX_SIZE) { idx = this.nextCode++; } else { idx = this.queue[this.qHead]; this.qHead = (this.qHead + 1) % LZW.MAX_SIZE; // 移除旧映射 const oldParent = this.dictParent[idx]; const oldCh = this.dictChar[idx]; let pos = this.hashFunc(oldParent, oldCh); while (!(this.hashParent[pos] === oldParent && this.hashChar[pos] === oldCh)) { pos = (pos + 1) & (LZW.HASH_SIZE - 1); } this.hashVal[pos] = -1; // 重新哈希 let nextPos = (pos + 1) & (LZW.HASH_SIZE - 1); while (this.hashVal[nextPos] !== -1) { const tp = this.hashParent[nextPos]; const tc = this.hashChar[nextPos]; const tv = this.hashVal[nextPos]; this.hashVal[nextPos] = -1; this.hashInsert(tp, tc, tv); nextPos = (nextPos + 1) & (LZW.HASH_SIZE - 1); } } this.dictParent[idx] = parent; this.dictChar[idx] = ch; this.hashInsert(parent, ch, idx); this.queue[this.qTail] = idx; this.qTail = (this.qTail + 1) % LZW.MAX_SIZE; return idx;}// 位流打包packBits(codes) { const out = new Uint8Array(codes.length * 3); // 增加缓冲区大小 let outPos = 0; let bitBuf = 0; let bits = 0; for (const code of codes) { bitBuf = (bitBuf << LZW.MAX_BITS) | (code & ((1 << LZW.MAX_BITS) - 1)); bits += LZW.MAX_BITS; while (bits >= 8) { bits -= 8; out[outPos++] = (bitBuf >> bits) & 0xFF; } } // 处理剩余位 if (bits > 0) { out[outPos++] = (bitBuf << (8 - bits)) & 0xFF; } return out.slice(0, outPos);}// 位流拆包unpackBits(data) { const codes = new Int32Array(data.length * 8 / LZW.MAX_BITS + 1); let codeCount = 0; let bitBuf = 0; let bits = 0; for (const byte of data) { bitBuf = (bitBuf << 8) | byte; bits += 8; while (bits >= LZW.MAX_BITS) { bits -= LZW.MAX_BITS; codes[codeCount++] = (bitBuf >> bits) & ((1 << LZW.MAX_BITS) - 1); }}// 处理剩余位if (bits >= LZW.MAX_BITS) { codes[codeCount++] = (bitBuf >> (bits - LZW.MAX_BITS)) & ((1 << LZW.MAX_BITS) - 1);}return codes.slice(0, codeCount);}// 压缩compress(input) { const codes = new Int32Array(input.length); let codeCount = 0; let parent = 0; for (const byte of input) { const next = this.hashFind(parent, byte); if (next !== -1) { parent = next; } else { codes[codeCount++] = parent; this.addNode(parent, byte); parent = this.hashFind(0, byte); }}if (parent !== 0) { codes[codeCount++] = parent;}return this.packBits(codes.slice(0, codeCount));}// 解压decompress(input) { const codes = this.unpackBits(input); const out = new Uint8Array(input.length * 4); // 增加缓冲区大小 let outPos = 0; let prevCode = 0; let firstCh = 0; const stack = new Uint8Array(LZW.MAX_SIZE); for (const code of codes) { let top = 0; let cur = code; if (code === this.nextCode && prevCode !== 0) { cur = prevCode; stack[top++] = firstCh; } else if (code > this.nextCode) { throw new Error('无效的压缩数据'); } while (cur !== 0) { stack[top++] = this.dictChar[cur]; cur = this.dictParent[cur]; } firstCh = stack[top - 1]; for (let j = top - 1; j >= 0; j--) { out[outPos++] = stack[j]; } if (prevCode !== 0 && this.nextCode < LZW.MAX_SIZE) { this.addNode(prevCode, firstCh); } prevCode = code; } return out.slice(0, outPos);}}// 使用示例async function main() { try { // 读取文件 const inputPath = process.argv[2] || 'Twilight.txt'; const input = await fs.promises.readFile(inputPath); const baseName = inputPath.replace(/\.[^/.]+$/, ''); const compPath = baseName + '.lzw'; const decompPath = baseName + '.dec'; // 压缩 const compressor = new LZW(); compressor.dictInit(); const startCompress = performance.now(); const compressed = compressor.compress(input); const compressTime = performance.now() - startCompress; await fs.promises.writeFile(compPath, compressed); console.log(`压缩完成: ${input.length} -> ${compressed.length} bytes, 用时 ${(compressTime/1000).toFixed(3)}s`); // 解压 const decompressor = new LZW(); decompressor.dictInit(); const startDecompress = performance.now(); const decompressed = decompressor.decompress(compressed); const decompressTime = performance.now() - startDecompress; await fs.promises.writeFile(decompPath, decompressed); console.log(`解压完成: ${decompressed.length} bytes, 用时 ${(decompressTime/1000).toFixed(3)}s`);// 校验if (input.length !== decompressed.length) { console.log(`长度不匹配: 原始=${input.length}, 解压=${decompressed.length}`);}let diffCount = 0;for (let i = 0; i < Math.min(input.length, decompressed.length); i++) { if (input[i] !== decompressed[i]) { diffCount++; if (diffCount <= 10) { console.log(`位置 ${i}: 原始=${input[i]}, 解压=${decompressed[i]}`);}}}if (diffCount > 0) { console.log(`共发现 ${diffCount} 处差异`); } else { console.log('校验通过');}} catch (error) { console.error('错误:', error.message);}}// 如果直接运行此文件if (require.main === module) { main();}// 导出 LZW 类module.exports = LZW; const fs = require('fs');// LZW 压缩器实现class LZW { // 常量定义 static MAX_BITS = 19; static MAX_SIZE = 1 << LZW.MAX_BITS; // 524288 static HASH_SIZE = 1 << 20; // 1048576 // 中文字典 static CHINESE_DICT = "的一是了我不人在他有这个上们来到时大地为子中你说生国年着就那和要她出也得里后自以会家可下而过天去能对小多然于心学么之都好看起发当没成只如事把还用第样道想作种开美总从无情己面最女但现前些所同日手又行意动" + "方期它头经长儿回位分爱老因很给名法间斯知世什两次使身者被高已亲其进此话常与活正感见明问力理尔点文几定本公特做外孩相西果走将月十实向声车全信重三机工物气每并别真打太新比才便夫再书部水像眼等体却加电主界门" + "利海受听表德少克代员许稜先口由死安写性马光白或住难望教命花结乐色更拉东神记处让母父应直字场平报友关放至张认接告入笑内英军候民岁往何度山觉路带万男边风解叫任金快原吃妈变通师立象数四失满战远格士音轻目条呢" + "病始达深完今提求清王化空业思切怎非找片罗钱紶吗语元喜曾离飞科言干流欢约各即指合反题必该论交终林请医晚制球决窢传画保读运及则房早院量苦火布品近坐产答星精视五连司巴奇管类未朋且婚台夜青北队久乎越观落尽形影" + "红爸百令周吧识步希亚术留市半热送兴造谈容极随演收首根讲整式取照办强石古华諣拿计您装似足双妻尼转诉米称丽客南领节衣站黑刻统断福城故历惊脸选包紧争另建维绝树系伤示愿持千史谁准联妇纪基买志静阿诗独复痛消社算" + "义竟确酒需单治卡幸兰念举仅钟怕共毛句息功官待究跟穿室易游程号居考突皮哪费倒价图具刚脑永歌响商礼细专黄块脚味灵改据般破引食仍存众注笔甚某沉血备习校默务土微娘须试怀料调广蜖苏显赛查密议底列富梦错座参八除跑"; constructor() { // 使用 TypedArray 优化性能 this.dictParent = new Int32Array(LZW.MAX_SIZE); this.dictChar = new Uint8Array(LZW.MAX_SIZE); this.hashParent = new Int32Array(LZW.HASH_SIZE); this.hashChar = new Uint8Array(LZW.HASH_SIZE); this.hashVal = new Int32Array(LZW.HASH_SIZE); this.queue = new Int32Array(LZW.MAX_SIZE); this.qHead = 0; this.qTail = 0; this.nextCode = 0; } // 初始化字典 dictInit() { // 初始化数组 this.hashVal.fill(-1); this.dictParent.fill(-1); this.dictChar.fill(0); // 初始化根节点 this.dictParent[0] = -1; this.dictChar[0] = 0; this.nextCode = 1; this.qHead = this.qTail = 0; // 初始化单字节字符 for (let i = 0; i < 256; i++) { this.dictParent[this.nextCode] = 0; this.dictChar[this.nextCode] = i; this.hashInsert(0, i, this.nextCode); this.queue[this.qTail++] = this.nextCode; this.nextCode++; } // 初始化中文字典 for (const c of LZW.CHINESE_DICT) { const utf8 = new TextEncoder().encode(c); let parent = 0; for (const b of utf8) { let next = this.hashFind(parent, b); if (next === -1) { next = this.addNode(parent, b); } parent = next; } } } // 哈希函数 hashFunc(parent, ch) { return ((parent * 131 + ch) & (LZW.HASH_SIZE - 1)); } // 哈希查找 hashFind(parent, ch) { let pos = this.hashFunc(parent, ch); while (this.hashVal[pos] !== -1) { if (this.hashParent[pos] === parent && this.hashChar[pos] === ch) { return this.hashVal[pos]; } pos = (pos + 1) & (LZW.HASH_SIZE - 1); } return -1; } // 哈希插入 hashInsert(parent, ch, idx) { let pos = this.hashFunc(parent, ch); while (this.hashVal[pos] !== -1) { pos = (pos + 1) & (LZW.HASH_SIZE - 1); } this.hashParent[pos] = parent; this.hashChar[pos] = ch; this.hashVal[pos] = idx; } // 添加节点 addNode(parent, ch) { let idx; if (this.nextCode < LZW.MAX_SIZE) { idx = this.nextCode++; } else { idx = this.queue[this.qHead]; this.qHead = (this.qHead + 1) % LZW.MAX_SIZE; // 移除旧映射 const oldParent = this.dictParent[idx]; const oldCh = this.dictChar[idx]; let pos = this.hashFunc(oldParent, oldCh); while (!(this.hashParent[pos] === oldParent && this.hashChar[pos] === oldCh)) { pos = (pos + 1) & (LZW.HASH_SIZE - 1); } this.hashVal[pos] = -1; // 重新哈希 let nextPos = (pos + 1) & (LZW.HASH_SIZE - 1); while (this.hashVal[nextPos] !== -1) { const tp = this.hashParent[nextPos]; const tc = this.hashChar[nextPos]; const tv = this.hashVal[nextPos]; this.hashVal[nextPos] = -1; this.hashInsert(tp, tc, tv); nextPos = (nextPos + 1) & (LZW.HASH_SIZE - 1); } } this.dictParent[idx] = parent; this.dictChar[idx] = ch; this.hashInsert(parent, ch, idx); this.queue[this.qTail] = idx; this.qTail = (this.qTail + 1) % LZW.MAX_SIZE; return idx;}// 位流打包packBits(codes) { const out = new Uint8Array(codes.length * 3); // 增加缓冲区大小 let outPos = 0; let bitBuf = 0; let bits = 0; for (const code of codes) { bitBuf = (bitBuf << LZW.MAX_BITS) | (code & ((1 << LZW.MAX_BITS) - 1)); bits += LZW.MAX_BITS; while (bits >= 8) { bits -= 8; out[outPos++] = (bitBuf >> bits) & 0xFF; } } // 处理剩余位 if (bits > 0) { out[outPos++] = (bitBuf << (8 - bits)) & 0xFF; } return out.slice(0, outPos);}// 位流拆包unpackBits(data) { const codes = new Int32Array(data.length * 8 / LZW.MAX_BITS + 1); let codeCount = 0; let bitBuf = 0; let bits = 0; for (const byte of data) { bitBuf = (bitBuf << 8) | byte; bits += 8; while (bits >= LZW.MAX_BITS) { bits -= LZW.MAX_BITS; codes[codeCount++] = (bitBuf >> bits) & ((1 << LZW.MAX_BITS) - 1); }}// 处理剩余位if (bits >= LZW.MAX_BITS) { codes[codeCount++] = (bitBuf >> (bits - LZW.MAX_BITS)) & ((1 << LZW.MAX_BITS) - 1);}return codes.slice(0, codeCount);}// 压缩compress(input) { const codes = new Int32Array(input.length); let codeCount = 0; let parent = 0; for (const byte of input) { const next = this.hashFind(parent, byte); if (next !== -1) { parent = next; } else { codes[codeCount++] = parent; this.addNode(parent, byte); parent = this.hashFind(0, byte); }}if (parent !== 0) { codes[codeCount++] = parent;}return this.packBits(codes.slice(0, codeCount));}// 解压decompress(input) { const codes = this.unpackBits(input); const out = new Uint8Array(input.length * 4); // 增加缓冲区大小 let outPos = 0; let prevCode = 0; let firstCh = 0; const stack = new Uint8Array(LZW.MAX_SIZE); for (const code of codes) { let top = 0; let cur = code; if (code === this.nextCode && prevCode !== 0) { cur = prevCode; stack[top++] = firstCh; } else if (code > this.nextCode) { throw new Error('无效的压缩数据'); } while (cur !== 0) { stack[top++] = this.dictChar[cur]; cur = this.dictParent[cur]; } firstCh = stack[top - 1]; for (let j = top - 1; j >= 0; j--) { out[outPos++] = stack[j]; } if (prevCode !== 0 && this.nextCode < LZW.MAX_SIZE) { this.addNode(prevCode, firstCh); } prevCode = code; } return out.slice(0, outPos);}}// 使用示例async function main() { try { // 读取文件 const inputPath = process.argv[2] || 'Twilight.txt'; const input = await fs.promises.readFile(inputPath); const baseName = inputPath.replace(/\.[^/.]+$/, ''); const compPath = baseName + '.lzw'; const decompPath = baseName + '.dec'; // 压缩 const compressor = new LZW(); compressor.dictInit(); const startCompress = performance.now(); const compressed = compressor.compress(input); const compressTime = performance.now() - startCompress;
