Project Nayuki

GIF optimizer (Java)


The GIF image file format uses Lempel-Ziv-Welch (LZW) compression to encode the pixel data. While there is only one correct way to decompress a given piece of LZW data, there are many valid ways to compress data using the LZW scheme.

One way to optimize the size of the compressed bit stream is to carefully chose when to clear the dictionary during stream processing. It appears that popular GIF encoders only clear the dictionary according to fixed rules instead of adaptively, thus my encoder will produce smaller files by exploiting this choice. It shows that existing GIF encoders have not explored the full potential of the GIF format.

But practically speaking, PNG is far superior to GIF in compression and features (such as true color and partial transparency, but lacking animation). This development here can be considered an exercise to show that more compression can be squeezed out of GIF than is typically possible. At the same time though, the general concept of choosing where to {clear the dictionary / split compression blocks} to optimize the size is applicable to many compression formats.

The optimization implemented here is based on two key ideas: After a Clear code, the way the rest of the input data is compressed does not depend on the earlier already-processed part. If we gather information about the compressed size of the input data range [i × blocksize, j × blocksize) for all possible values of i and j (which has time complexity Ω(blocksize−2)), then we can use dynamic programming to deduce the optimal points to split the input data into blocks. (Note that the compressed blocks need not be of uniform length. There is a numerical example at the bottom of the page to illustrate this algorithm.)

Source code

Main programs:

Usage: java OptimizeGif [Options] Input.gif Output.gif

This program reads the given input GIF, optimizes all the LZW data blocks, and writes a new output GIF file. The pixel data, palettes, structures, metadata, arrangement, and structures are left changed.

Usage: java WriteGif [Options] Input.bmp/png/gif Output.gif

This program reads the given input image and writes an output GIF file with identical pixel content. The image must have 256 or fewer unique colors. For detailed options and limitations, see the header comment in the source code.

(Note: Do not process input images that are 8-bit grayscale-paletted; please convert them to 24-bit RGB first. This is because Java’s ImageIO returns a BufferedImage which has a bug with regards to gamma correction, resulting in a washed-out output image.)

Required libraries:

Warning: This code is not production-level quality. It could crash at random times and/or corrupt data silently. Nayuki provides no warranty or compensation for any losses incurred.

Sample images and benchmarks


Color photo – landscape:

Real-life photographic content with many colors and minor dithering. (Source)

Format, method File size Bar graph
BMP, 8-bit263 222
GIF, IrfanView184 279
GIF, Adobe Photoshop184 282
GIF, uncompressed298 032
GIF, Nayuki monolithic329 326
GIF, Nayuki blocksize=32768214 534
GIF, Nayuki blocksize=4096181 956
GIF, Nayuki blocksize=512181 371
GIF, Nayuki blocksize=64181 095
PNG, OptiPNG -o7161 256

Discussion: Monolithic compression performs very poorly because the LZW dictionary is built from the colors in the top of image (sky blue), but the bottom of the image has no such colors (green). Furthermore the dictionary stops growing after 4096 entries, which means multi-pixel entries with green cannot be added. So the bottom is encoded using literal symbols but with an expanded bit width, thus wasting lots of space and performing even worse than the uncompressed GIF.

Color photo – portrait:

Real-life photographic content with many colors and minor dithering. (Source)

Format, method File size Bar graph
BMP, 8-bit263 222
GIF, IrfanView191 012
GIF, Adobe Photoshop190 918
GIF, uncompressed298 032
GIF, Nayuki monolithic312 528
GIF, Nayuki blocksize=32768220 031
GIF, Nayuki blocksize=4096189 407
GIF, Nayuki blocksize=512188 590
GIF, Nayuki blocksize=64188 218
PNG, OptiPNG -o7160 533

Discussion: Monolithic compression performs poorly here too, and the file sizes have the same pattern as the landscape photo.

Grayscale text

Grayscale anti-aliased Latin-alphabet text. (Document source)

Format, method File size Bar graph
BMP, 8-bit263 222
GIF, IrfanView59 702
GIF, Adobe Photoshop59 735
GIF, uncompressed298 032
GIF, Nayuki monolithic51 544
GIF, Nayuki blocksize=3276851 544
GIF, Nayuki blocksize=409651 021
GIF, Nayuki blocksize=51250 808
GIF, Nayuki blocksize=6450 793
PNG, OptiPNG -o730 697

Discussion: This image is very compressible, as seen in the stark difference between the compressed GIF and PNG files versus the uncompressed GIF and BMP files.

Monochrome text

Simple black-and-white text without smoothing. (Text sources: English, Chinese, Arabic)

Format, method File size Bar graph
BMP, 1-bit32 830
GIF, IrfanView19 237
GIF, Adobe Photoshop19 243
GIF, uncompressed148 068
GIF, Nayuki monolithic19 204
GIF, Nayuki blocksize=3276818 612
GIF, Nayuki blocksize=409618 526
GIF, Nayuki blocksize=51218 511
GIF, Nayuki blocksize=6418 505
PNG, OptiPNG -o714 826

Discussion: The uncompressed GIF is exceedingly inefficient (compared to the 8-bit case) because the encoder needs to emit a Clear code every 2 symbols; furthermore each symbol is encoded with 3 bits, not 2. The uncompressed BMP reference shows that the GIF compressed size is around 50%.

Vertically varying noise

This tests whether clearing the dictionary as the colors change vertically can help compression. (Image generated by Nayuki)

Format, method File size Bar graph
BMP, 8-bit263 222
GIF, IrfanView220 936
GIF, Adobe Photoshop221 090
GIF, uncompressed298 032
GIF, Nayuki monolithic372 435
GIF, Nayuki blocksize=32768284 308
GIF, Nayuki blocksize=4096218 329
GIF, Nayuki blocksize=512217 369
GIF, Nayuki blocksize=64217 074
PNG, OptiPNG -o7177 536

Discussion: Because the range of colors varies vertically, it is advantageous to periodically clear the dictionary to remove patterns that contain colors that are not used in subsequent lines.

Horizontally varying noise

This tests whether the advantage is nullified compared to the vertically varying case, because every line will cover most of the color range. (Image generated by Nayuki)

Format, method File size Bar graph
BMP, 8-bit263 222
GIF, IrfanView322 769
GIF, Adobe Photoshop322 810
GIF, uncompressed298 032
GIF, Nayuki monolithic308 301
GIF, Nayuki blocksize=32768308 025
GIF, Nayuki blocksize=4096307 352
GIF, Nayuki blocksize=512306 535
GIF, Nayuki blocksize=64291 939
GIF, Nayuki custom tiled216 720
PNG, OptiPNG -o7224 173

Discussion: We see that LZW compression is very difficult to do effectively in this case. Nearly all the compressors fall apart and do worse than the dumb uncompressed encoding, except my encoder with blocksize=64 which performs better.

However, by splitting the image into thin vertical strips and compressing each strip independently, it is possible to circumvent the problem and achieve decent compression just like the vertically varying case. In fact it is surprising that this beats PNG compression. This tiled image was created manually using a custom program (not published). The downside is that many (but not all) GIF decoders are broken and incorrectly assume that the image is an animation where each strip is a new frame, even though the duration of each strip is supposed to be exactly zero.

Uniform random noise

The worst case possible, where the expected size must be at least 262 144 bytes as dictated by information entropy. (Image generated by Nayuki)

Format, method File size Bar graph
BMP, 8-bit263 222
GIF, IrfanView361 091
GIF, Adobe Photoshop361 078
GIF, uncompressed298 032
GIF, Nayuki monolithic374 053
GIF, Nayuki blocksize=32768372 735
GIF, Nayuki blocksize=4096361 891
GIF, Nayuki blocksize=512312 777
GIF, Nayuki blocksize=64297 402
PNG, OptiPNG -o7262 759

Discussion: There are absolutely no patterns in the data, and the performance comes down to how badly the compression method adds overhead and how badly it uses inefficient encodings.

Overall observations and notes

Optimization algorithm example

Here is a small artificial example to illustrate the optimization technique. In the following table, the row represents the block offset and the column represents the number of blocks of input data to encode. For example, the table says it takes 20 bits to encode the input range starting at block 3 and running for 2 blocks.


We can use dynamic programming to distill this information into better information. The next table describes the minimum number of bits to encode the input data starting at block i and going to the end of the data, assuming that the dictionary can be cleared at various points during encoding. It also describes the number of blocks to encode starting at the current offset to achieve this minimum size, such that afterwards the dictionary is cleared and a new block would begin.

Start offset (blocks)012345
Minimum encoded size605040302010
Num blocks to encode133221

Based on these numbers, a final optimal encoding will split the input into these block ranges: [0,1), [1,4), [4,6). Or to state it compactly, the set of block boundaries will be {0, 1, 4, 6}. The encoded size will be 10 + 30 + 20, which is less than the size 70 we would get if we started at block 0 and encoded all the way to the end without clearing the dictionary (the monolithic encoding).

Note: In addition to controlling blocks / the Clear code, another way to optimize GIF compression is to do the LZW encoding differently – to use “flexible parsing” (described in various research papers) instead of greedy matching.

More info