java - 位打包 LZW 短语编号

Question

我目前正在研究 LZW 压缩的 Java 实现。到目前为止，我的编码器按其应有的方式工作。读取文件并输出短语编号，该编号将通过管道传送到位打包器。

我现在必须将这些短语编号打包到一个文件中，但我不确定如何进行此过程。此外，我们为编码设置的最大位数为 20。因此，当编码的数字超过编码所需的 20 位时，我们会重置 trie 并开始构建一个新的。

所以我们必须位打包的第一组数字是 0-255 然后是 256-511 等等，所以我知道有些会被打包为 8 位，然后是 9 位，依此类推。

如果可以就从哪里开始以及查看什么内容提供任何指导，这可能会有所帮助，我们将不胜感激

Answer 1

LZW 压缩通常以比符号大小大一的位数开始。因此，如果符号是 8 位值，则初始位大小通常为 9。这对于字面值 0..255 和字典中的前 256 个代码来说就足够了。通常，LZW 也有一些特殊的预定义代码，例如“清除”代码和“停止”代码，它们作为符号 0x100 和 0x101 附加到符号集中。它们不是严格要求的，但非常有用。

此外，您还有最大位数来限制字典的增长。在你的例子中，它是 20，所以你的字典最多可以容纳 1048576 个条目。要编写可变长度位代码，您需要使用足够宽的寄存器来容纳最大位数。对于您的情况，32 位或 64 位无符号整数是合适的。 (如果您的目标是 64 位处理器，请使用后者。)因此，基本上，您维护一个位移计数器，最初设置为 0，并将位移位/写入寄存器，直到溢出。然后将整个寄存器写入流并移位/复制剩余的位。最后，您必须将寄存器中的最新位刷新到流中(如果有)。

真的就是这么简单。您不需要任何特殊的位计数处理，因为 LZW 读取器和写入器对于何时增加位计数达成了一致。一些 LZW 实现(例如 TIFF 6.0)会在编写适合旧大小的最后代码之前增加计数(所谓的“早期更改”)。其他的(例如 GIF)则在之后增加它，这样效率更高。您可以自由选择所写入符号的位顺序。只需要编码器和解码器对此达成一致即可。现有的 LZW 实现再次使用不同的位顺序:GIF 从最低有效位到最高有效位写入它们，TIFF 6.0 则相反。 LSB 到 MSB 变体通常更容易实现。

请注意，这是一个常见的误解，认为字典满了就需要立即清除。实际上，我发现在大多数情况下，如果您继续填充目录，发出最大宽度代码直到最后，LZW 压缩要好得多。这是因为字典现在反射(reflect)了输入流的统计分布并发出有效的代码。仅当分布随时间发生显着变化时才需要清除，因此字典变得不充分。

常见的 GIF 和 TIFF 的 LZW 解码器经常会在字典填满后自动清除字典，而不是等待清除代码。这是“坏习惯”，甚至在最新 GIF 规范附带的注释中明确表示不赞成，但可惜的是，如果编码器想要与所有读者兼容，那么它不应该用清晰的代码进行赌博。