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

然后，等于255的每个字段都表示连续字节的出现，sum将是要添加的元素；字节0表示sum的结束。

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

Answer 1

LZW有一个可预测的下一个数据块大小。因此，您的编码器应该保存保存当前代码所需的位数。您的解码器应该计算下一段代码的位数，并读取该位数。

所以你的解码器看起来就像

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

压缩算法在通用情况下从来不起作用。LZW适用于高度重复的数据。对于不重复的数据，压缩后的数据大小总是大于初始数据大小。