[原创] 信息编码之 LZW 压缩算法

最近发现一个在线塔防策略游戏网站：8a3K9s2c8@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 位）就能唯一表示一个编号（>2^{24} \gt 200000224>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，完整的字典如表

...(已截断)

---
来源: 看雪论坛
原文链接: https://bbs.kanxue.com/thread-287837.htm

我嘞个甘油三酯

太强了