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

Question

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

Answer 1

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

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

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

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

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

在 "On parsing optimality for dictionary-based text compression—the Zip case" 中简要讨论了许多 LZ77/LZ78/LZW 变体(以及它们使用的优化)作者:阿莱西奥·兰久；这些摘录包含许多有趣的细节，可用于进一步的研究。

¹ "Improving LZW' R. Nigel Horspool 详细介绍了自适应符号大小。奈杰尔的 "The Effect of Non-Greedy Parsingin Ziv-Lempel Compression Methods"论文还总结了 compress 对字典重置的处理。

² "The Relative Efficiency of Data Compression by LZW and LZSS"由 Yair Wiseman 撰写，包含符号大小与压缩效率的示例图。该图高度依赖于数据。