3

这个问题可能并不严格限于 LZW 算法，可能会涵盖 LZ77 和 LZ78 的其他实现：

我一直在尝试编写一个涉及 LZW 字典编码方案的压缩/解压缩实用程序。问题是我发现在编码阶段写出每个代码字（或“代码”）之后有必要包含一个定界字符（空格）。我一直在这样做，因为我不能假设输出直接流式传输到解码器，并且可以存储在压缩文件中以便稍后解码（在这种情况下，解码器将需要某种方法来检测分离的内容码字 - 分隔符）。

我最近被告知这是不必要的，并且解码器应该能够动态地“计算”每次要读取多少压缩文件，大概是基于先前读取的代码。据说这将消除（昂贵的）在每个代码之后插入额外字节的需要。

我只是不确定解码器如何解决这个问题。也许了解它如何工作的人可以向我解释一下？谢谢。

编辑：

字典是一个将“输入字符串”映射到整数（代码）的哈希表，并且随着更多的输入数据被读入而以通常的方式构建。代码被写出到压缩文件中。解码器从压缩文件中读取每个代码（整数），并在其字典中查找要输出的关联字符串，或者如果该代码没有条目，那么它会以通常的方式确定字符串应该是什么并更新它的字典。

“为什么文件是流式传输或存储的？” 如果编码器的输出一次将一个代码流式传输到解码器，则解码器可以在接收到每个代码时对其进行处理。但是，如果编码器将所有代码写入一个文件（压缩文件），然后将该文件馈送到解码器，那么解码器如何知道一个代码从哪里开始，另一个代码从哪里开始。该文件将只是一个混搭的数字序列。

例如：分隔压缩文件：127 32 45 22 228 122 209.... 非分隔压缩文件：127324522228122209...

-抢

4

2 回答 2

2

在 LZW 中，字典不与压缩文件一起存储。（或者字典是文件，取决于您的观点。）写入文件的每个值都根据其位置具有预定义的位宽。例如，它可以从成对的 9 位字典索引开始，然后是 8 位数据，直到在切换到 10 位索引时索引用尽（发生在精确位置）。

细节取决于您如何实现压缩。有些做一个恒定的 12 位索引。但在任何情况下都不需要额外的分隔符。

此外，由于数据未在 8 位边界上对齐，因此如果您尚未正确读取数据，则无法检测分隔符！

编辑：

如果您希望 LZW 压缩算法实际生成比输入更小的数据，那么您应该做几件事。

首先，您必须将文件编写为二进制而不是文本。将其写为文本将扩大而不是缩小文件的大小。值 127 可以存储在二进制 (01111111) 的单个字节中，但需要四个字节的 UTF-8 和分隔空间（“127” = 00110001 00110010 00110111 00100000）。

其次，LZW 设计用于处理大于 1 字节但小于 2 字节的代码值，因此您必须进行一些位旋转才能正确输出数据。单个字节仅足以对前 256 个隐式定义的表条目进行编码。另一位将为您提供另外 256 个条目，但 9 位索引表中的条目很快就会用尽。使用 12 位，您可以获得 4096 个表条目，这是一个合理的表大小。如果您要使用两个完整字节，那么您将拥有一个包含 65 K 条目的相当大的表。这样做的问题是，如果您没有使用表空间的全部容量，那么您就是在浪费位。输出中会有很多位始终为零，这对您的压缩比非常不利。

第三，流式编码器/解码器不能一次处理单个值，因为编码数据与字节边界重叠。如果使用恒定的 12 位代码大小，则可以一次处理两个编码值的某个倍数。但总的来说，该算法旨在处理完整的文件。

于 2011-04-19T18:17:38.510 回答
1

使用 LZW，在读取文件时会生成码本，从而无需分隔符。随着每个字符被添加到 LZW 输出，它会从 8 位转换为更高的值（通常为 10 或 12 位），以便为码本留出空间。例如：

banana

在 LZW 中，b已经在码本中（参考 2），所以继续ba。 ba不在密码本中，所以添加它。

输出当前是

ba有一个密码本

27 =ba

（1-26 是 az 的索引）

接下来它保留a并读取n-> an。这也不在密码本中，因此被添加。

输出当前是

ban有一个密码本

27 = ba 28 =an

重复直到结束。结果是：

bana29有一个密码本

27 = ba 28 = an 29 =na

无需添加分隔符，因为在解码单词时，码本中已经存在bana29查找。29

我希望这有助于解释为什么不需要使用 LZW 进行分隔

于 2011-04-19T18:25:34.073 回答