java - LZW - 压缩率

Question

好吧，我必须使用 LZW 算法制作一个 PPM 图像压缩器，我理解该算法和代码并实现了一个字符串版本(在 Java 中，用于测试)。

最大的问题是压缩，因为如果我有:

输入:ABCDABCDABCDABCD

输出:65 66 67 68 256 258 260 259 257 68

至于我的输入，我有 16 个字符，如果我只是将输出保存为文本文件，则没有压缩，因为有 34 个字符。所以我想我会保存为二进制文件，然后在我的文件的一个字节中刻录每个字段，但是存在字段 >= 256 的问题。我也想到了将一些字段设置为值时发生的想法大于 255 之类的东西。 :

(在这种情况下，我将删除字典中的 255 字段和 0)

65 66 67 68 256 258，将是:

65 66 67 68 255 1 0 255 3 0

那么每个字段等于 255 表示出现了连续的字节和 sum 将是要添加的元素； byte 0表示sum结束。

问题是即使这样我的输出也会大于输入，压缩没有意义。然后我会问你是否有办法解决这个问题。

Answer 1

LZW 具有可预测的下一个数据 block 大小。所以你的编码器应该保存保存当前代码所需的位数。您的解码器应该计算下一个代码的位数并读取该位数。

所以你的解码器看起来像

while (read next block){
   read next block bits size
   decode character block
   update dictionary
   next block bits size = dictionary next code bit size
}

压缩算法永远不会在通用情况下起作用。 LZW 适用于高度重复的数据。对于非重复数据，压缩后的数据大小将始终大于初始数据大小。