Lossless GIF recompression via exhaustive search
The article describes a method for lossless GIF recompression by exhaustively searching for the optimal LZW encoding parameters, resulting in smaller file sizes without any loss of image quality.
Background
- GIF is a 1987 image format that supports only 256 colors per frame and uses LZW compression—an algorithm patented until 2004, which historically slowed adoption of better formats.
- Because GIF is still widely used for short animations and memes, any technique that shrinks GIF files without changing what they look like (lossless recompression) can save bandwidth and storage at scale.
- Exhaustive search means trying every possible compression parameter combination (e.g., LZW dictionary sizes, color table ordering) to find the smallest valid file—something typically too slow to do at runtime, but feasible for one-off optimization.
- Prior tools like gifsicle or ImageMagick apply heuristic compression; this post explores whether brute-force enumeration can beat them.