吉夫LZW压缩

Question

http://giflib.sourceforge.net/whatsinagif/lzw_image_data.html

我在阅读本页，了解吉夫的LZW压缩。它示出了从它的样本图像的编码代码：

＃4＃1＃6＃6＃2＃9＃9 ..

可变长度压缩成字节后，就变成：

8C 2D 99 ..

这意味着：

＃4 - 3比特

＃1 - 3比特

＃6 - 3个比特

＃6 - 3比特

＃2 - 4位

＃9 - 4比特

该压缩图像数据是正确的，因为我生成的吉夫样品图像使用Photoshop和验证的二进制内容。

它清楚地表明位大小增加发生在输出代码＃2

然而，这是怎么一回事位大小增加页面会谈： When you are encoding the data, you increase your code size as soon as your write out the code equal to 2^(current code size)-1

Jumping back to our sample image, we see that we have a minimum code size value of 2 which means out first code size will be 3 bits long. Out first three codes, #1 #6 and #6, would be coded as 001 110 and 110. If you see at Step 6 of the encoding, we added a code of #7 to our code table. This is our clue to increase our code size because 7 is equal to 2^3-1 (where 3 is our current code size). Thus, the next code we write out, #2, will use the new code size of 4 and therefore look like 0010.

但其编码表中，第6步是将条目＃7添加到LZW词典中，但为输出添加的代码是第一个＃6。根据算法，这两个＃6应该是每个4位，但他们怎么实际上是3位？

本页面 https://www.eecis.udel.edu/~amer/CISC651/lzw.and.gif.explained.html

它说，关于位大小相同的事情If you're encoding, you start with a compression size of (N+1) bits, and, whenever you output the code (2**(compression size)-1), you bump the compression size up one bit

这样有什么不好？

Answer 1

查看您再次链接到页面上的示例：图像仅有4种颜色，即LZW压缩器以3位代码开始。该字典到目前为止包含6个条目：文字0..3，清除代码4和EOI代码5.前两个代码输出是清除代码4和文字1.这就是所有GIF LZW流开始的方式。现在开始压缩，因为图像以1的运行开始。在写入数据流之后再添加2个代码，8个字典插槽耗尽，代码大小增加到4.因此，下一个代码 - 文字2 - 被写为4位数字。

如你所见，没有什么是错的。这就是GIF用4色图像工作的方式。