如果 LZW 算法中的字典大小已满怎么办？

Question

我一直在研究 LZW 压缩，有一件事我无法满足自己，那就是在 LZW 中构建字典时，其最大限制设置为 4096 个条目。这是为什么 ？。此外，如果字典已满，则字典将被重置，但如果在重置字典之前字典中存在接下来要阅读的几个字符，该怎么办。这是限制吗？还是我的理解不正确？

Answer 1

字典大小受限于输出符号大小。12 位可以编码 4096 个不同的值。这是讲义和简单/作业实现的常见选择。

\n\n

然而，可以使用比源位多的任何符号位：16 位符号将允许 65k 字典条目。位越多，当前字典中可以存在的条目就越多，这可以增加 \xe2\x80\x9cmaximum\xe2\x80\x9d 压缩。相反，当每个输出符号较大时，它可能会降低压缩率，特别是对于较小的输入（生成字典的时间不足）和更加随机的数据（重新使用字典中的符号的能力降低）。实际上，19-20 位似乎是有用的限制²，而 16 位符号自然与字节对齐。

\n\n

还可以根据映射符号¹的当前数量的 log2 来设置自适应符号大小- 但随着数据大小的增加，这种好处就会消失，因为字典很快就会填满。它也很大程度上被霍夫曼编码所取代。

\n\n

当字典被“重置”时，它实际上与压缩多个数据块并附加压缩输出相同：字典是分开的。但是，数据可以根据数据填充字典的时间动态地\xe2\x80\x9csplit\xe2\x80\x9d，而不是每X 个字节的输入。由于符号大小是固定的，因此在做出决定之前确保字典已填满会更有效。

\n\n

重置字典的主要目的是避免 \xe2\x80\x9c 将符号固定为输入的一部分中的数据特征，而这对于以后的数据可能不正确。压缩器可以使用单个非重置字典，一旦字典满就重置字典，当字典\xe2\x80\x99s满并且遇到压缩下降时重置字典，等等：目标是实现域/参数内的最高压缩。

\n\n

AlessioLangiu在“基于字典的文本压缩的解析最优性\xe2\x80\x94the Zip case”中简要讨论了许多 LZ77/LZ78/LZW 变体（以及它们使用的优化） ；这些摘录包含许多有趣的细节，可供进一步研究。

\n\n

^{1 R. Nigel Horspool 的}《Improving LZW》详细介绍了自适应符号大小。Nigel 的《The Effect of Non-Greedy Parsing\nin Ziv-Lempel CompressionMethods》compress论文还包括对\'s 处理的总结字典重置。

\n\n

^{2 Yair Wiseman 的}“LZW 和 LZSS 数据压缩的相对效率”包含符号大小与压缩效率的示例图。该图高度依赖于数据。

\n