c - 文件压缩和代码

Question

我正在实现一个版本的 lzw。假设我从 10 位代码开始，并在我最大限度地使用代码时增加。例如，在 1024 代码之后，我需要 11 位来表示 1025。问题在于表示移位。

如何告诉 decode 我更改了代码大小？我考虑过使用 00，但程序无法区分 00 作为增量和 00 只是代码零的两个实例。

有什么建议么？

Answer 1

你没有。当字典已满时，您将转换为新大小。解码器的字典是与编码器的字典同步构建的，因此它们会同时被填满，并且解码器将在编码器完成时准确地转换到新的大小。

您必须发送代码以表示更改的时间是当您完全填满字典时 - 您已经使用了所有可用的最大代码。在这种情况下，您通常希望继续使用字典，直到/除非压缩率开始下降，然后清除字典并重新开始。您确实需要放置一些标记以告知何时发生。通常，您为此目的保留单个最大的代码，但您不用于任何其他目的的任何代码都可以使用。

编辑：顺便说一句，请注意您通常希望从比输入代码大一码的代码开始，因此如果您要压缩 8 位字节，您希望从 9 位代码开始。

Answer 2

这是 LZW 算法的一部分。

解压缩时，您会再次自动构建代码字典。当一个新代码恰好填满当前位数时，代码大小必须增加。

有关详细信息，请参阅维基百科。

Answer 3

^{当您为 2 n} -1创建代码时，您增加了位数。因此，当您创建代码 1023 时，请立即增加位大小。您可以从GIF 压缩方案中获得更好的描述。请注意，这是一个专利方案（部分原因是 PNG 的创建）。该专利现在可能已经过期。

Answer 4

由于解码器构建与压缩器相同的表，因此它的表在到达最后一个元素时已满（在您的示例中为 1023），因此，解码器知道下一个元素将是 11 位。