- https://www.google.com/patents/US7696906 (Apr 13, 2010)
- https://www.google.com/patents/US20100039300 (Feb 18, 2010)
- Jacob Ziv and Abraham Lempel
- IEEE Transactions on Information Theory, Sep. 1978, pp. 530-536, vol. 24, No. 5.
- http://ieeexplore.ieee.org/document/1055934/
- Terry Welch
- Computer Volume: 17, Issue: 6, June 1984
- http://ieeexplore.ieee.org/document/1659158/
- Nelson, M.R.
- Dr. Dobb's Journal, October 1989.
- http://marknelson.us/1989/10/01/lzw-data-compression/
- http://marknelson.us/2011/11/08/lzw-revisited/ (in November 8th, 2011)
- https://web.archive.org/web/20150428121506/http://oldwww.rasip.fer.hr:80/research/compress/algorithms/fund/lz/lzw.html
- https://web.archive.org/web/20150428140733/http://oldwww.rasip.fer.hr:80/research/compress/algorithms/fund/lz/lz78.html
- https://web.archive.org/web/20150428140733/http://oldwww.rasip.fer.hr:80/research/compress/algorithms/fund/lz/lz77.html
Variable-Length-Code LZW for GIF
number of bits, the number of bits per LZW code is increased by one.
Main differences
2 ^ <CODE SIZE>
. For example if the code size indicated was 4 (image was 4 bits/pixel) the Clear code value would be 16 (10000 binary). The Clear code can appear at any point in the image data stream and therefore requires the LZW algorithm to process succeeding codes as if a new data stream was starting. Encoders should output a Clear code as the first code of each image data stream.<Clear code> + 1
.<Clear code> + 2
. (<Clear code> + 1
is "End of Information code")<CODE SIZE> + 1
bits per code, up to 12 bits per code. This defines a maximum code value of 4095(0xFFF). Whenever the LZW code value would exceed the current code length, the code length is increased by one. The packing/unpacking of these codes must then be altered to reflect the new code length.Clear Code
As the specification says, they may appear at anytime. There is not a requirement to send a clear code when the string table is full.
It is the encoder's decision as to when the table should be cleared. When the table is full, the encoder can chose to use the table as is, making no changes to it until the encoder chooses to clear it. The encoder during this time sends out codes that are of the maximum Code Size.
As we can see from the above, when the decoder's table is full, **it must not change the table until a clear code is received. ** The Code Size is that of the maximum Code Size. Processing other than this is done normally.
How to build byte array from variable-length-codes
Because the LZW compression used for GIF creates a series of variable length codes, of between 3 and 12 bits each, these codes must be reformed into aseries of 8-bit bytes that will be the characters actually stored or transmitted. This provides additional compression of the image. The codes are formed into a stream of bits as if they were packed right to left and then picked off 8 bits at a time to be output.
Assuming a character array of 8 bits per character and using 5 bit codes to be packed, an example layout would be similar to:
Note that the physical packing arrangement will change as the number of bits per compression code change but the concept remains the same.
https://www.w3.org/Graphics/GIF/spec-gif89a.txt