Question posted in 
If I have a gif89a which has multiple image blocks that are identical (and small, say 40×40 or 1600 pixels in size), should these continue to increase the final size of the gif file (assuming a sane encoder)?
I’m trying to understand how the LZW compression works. According to the W3C spec, I thought the entire data stream itself (consisting of multiple image blocks) should be be compressed, and thus repeating the same image frame multiple times would incur very little overhead (just the size of the symbol for the the repeated image block). This does not seem to be the case, and I’ve tested with several encoders (Gimp, Photoshop).
Is this to be expected with all encoders, or are these two just doing it poorly?
With gimp, my test gif was 23k in size when it had 240 identical image blocks, and 58k in size with 500 image blocks, which seems less impressive than my intuition is telling me (my intuition’s pretty dumb, so I won’t be shocked if/when someone tells me it’s incredibly wrong).
[edit]I need to expand on what it is I’m getting at, I think, to receive a proper answer. I am wanting to handcraft a gif image (and possibly write an encoder if I’m up to it) that will take advantage of some quirks to compress it better than would happen otherwise.
I would like to include multiple sub-images in the gif that are used repeatedly in a tiling fashion. If the image is large (in this case, 1700×2200), gif can’t compress the tiles well because it doesn’t see them as tiles, it rasters from the top left to the bottom right, and at most a 30 pixel horizontal slice of any given tile will be given a symbol and compressed, and not the 30×35 tile itself.
The tiles themselves are just the alphabet and some punctuation in this case, from a scan of a magazine. Of course in the original scan, each “a” is slightly different than every other, which doesn’t help for compression, and there’s plenty of noise in the scan too, and that can’t help.
As each tile will be repeated somewhere in the image anywhere from dozens to hundreds of times, and each is 30 or 40 times as large as any given slice of a tile, it looks like there are some gains to be had (supposing the gif file format can be bent towards my goals).
I’ve hand-created another gif in gimp, that uses 25 sub-images repeatedly (about 700 times, but I lost count). It is 90k in size unzipped, but zipping it drops it back down to 11k. This is true even though each sub-image has a different top/left coordinate (but that’s only what, 4 bytes up in the header of the sub-image).
In comparison, a visually identical image with a single frame is 75k. This image gains nothing from being zipped.
There are other problems I’ve yet to figure out with the file (it’s gif89a, and treats this as an animation even though I’ve set each frame to be 0ms in length, so you can’t see it all immediately). I can’t even begin to think how you might construct an encoder to do this… it would have to select the best-looking (or at least one of the better-looking) versions of any glyph, and then figure out the best x,y to overlay it even though it doesn’t always line up very well.
It’s primary use (I believe) would be for magazines scanned in as cbr/cbz ebooks.
I’m also going to embed my hand-crafted gif, it’s easier to see what I’m getting at than to read my writing as I stumble over the explanation:
2
Answers
LZW (and GIF) compression is one-dimensional. An image is treated as a stream of symbols where any area-to-area (blocks in your terminology) symmetry is not used. An animated GIF image is just a series of images that are compressed independently and can be applied to the “main” image with various merging options. Animated GIF was more like a hack than a standard and it wasn’t well thought out for efficiency in image size.
There is a good explanation for why you see smaller files after ZIP’ing your GIF with repeated blocks. ZIP files utilize several techniques which include a “repeated block” type of compression which could do well with small (<32K) blocks (or small distances separating) identical LZW data.
GIF-generating software can’t overcome the basic limitation of how GIF images are compressed without writing a new standard. A slightly better approach is used by PNG which uses simple 2-dimensional filters to take advantage of horizontal and vertical symmetries and then compresses the result with FLATE compression. It sounds like what you’re looking for is a more fractal or video approach which can have the concept of a set of compressed primitives that can be repeated at different positions in the final image. GIF and PNG cannot accomplish this.
GIF compression is stream-based. That means to maximize compression, you need to maximize the repeatability of the stream. Rather than square tiles, I’d use narrow strips to minimize the amount of data that passes before it starts repeating then keep the repeats within the same stream.
The LZW code size is capped at 12 bits, which means the compression table fills up relatively quickly. A typical encoder will output a clear code when this happens so that the compression can start over, giving good adaptability to fresh content. If you do your own custom encoder you can skip the clear code and keep reusing the existing table for higher compression results.
The GIF spec does not specify the behavior when a delay time of 0 is given, so you’re at the mercy of the decoder implementation. For consistent results you should use a delay of 1 and accept that the entire image won’t show up immediately.