Talk:LZW compression: Difference between revisions
Nitpicky details
(Nitpicky details) |
|||
Line 1:
==Details of LZW==
The task currently does not actually specify the LZW algorithm to be implemented. Instead, it defers to whatever is currently present in the Wikipedia presentation of the algorithm. This has left some compatibility details unspecified. (As near as I can tell, none of the implementations here include support for these issues.) But the task page is also back-linked from wikipedia, and someone should take responsibility for mentioning these things:
(1) One consequence is that the implementations do not include the LZW bitpacking algorithm. Instead, they represent the numbers which would be fed to that algorithm. The bitpacking algorithm shifts indices into position to take advantage of all guaranteed zeros in the representation of the previous index. (This probably suggests a little-endian representation of the indices.)
(2) Another consequence is that the implementations tend to not include the LZW clear code. LZW may limit the size of the dictionary (12 bit indices in the GIF standard, apparently 32 bit indices in the LZW file format, though I haven't investigated that closely enough to be sure). When the dictionary size is reached, the encoder emits the clear code (0x100 for the usual ANSI LZW dictionary) and reverts the dictionary to its original state. (And, of course, the decoder must do the same at that point.)
(3) Another issue is that the LZW file format begins with a three byte sequence (0x1F 0x9d bitwidth where only the low five bits of bitwidth are significant). Again, not represented in this task.
(At the time I am writing this, this is an first draft describing these issues. I (or someone) should probably track down a historically valid LZW implementation and verify the correctness of the description of this description.)
==Task and example==
The task talks about compression, but I've seen a lot of examples implement both compression and decompression; should we create a new task (LZW decompression) where to move the decompression related code, or change this one and add decompression to those examples that still does not implement it? --[[User:ShinTakezou|ShinTakezou]] 16:51, 31 January 2009 (UTC)
| |||