Сжать GIF без потерь полным перебором: история ZGIF

GIF внутри использует LZW, а не DEFLATE, и это влияет на то, как его сжимать. Существующий flexiGIF уже умеет гибкий разбор с заглядыванием вперёд, но иногда делает хуже: занятый слот в словаре потом аукается. Автор задался вопросом, какой LZW-поток для картинки минимален в принципе, и написал ZGIF, который ищет этот минимум полным перебором. По духу это Zopfli, только для LZW.

Путь к рабочей версии занял несколько подходов, от поиска A* через динамическое программирование к гибриду с отсечением:
🔘первая реализация на Python сжимала картинку 16 на 16 пикселей, всего 256 байт, за 30 минут;
🔘после оптимизаций то же самое стало занимать 4 минуты;
🔘с отсечением и заглядыванием на один шаг скорость упала до 4 секунд;
🔘результат при этом всё равно плотнее, чем у существующих инструментов.

Сохранять тем, кто любит алгоритмы сжатия и истории про то, как наивная идея «давайте переберём всё» доводится до практичной скорости.

Полная статья: https://blog.arusekk.pl/posts/lossless-gif-recompression/

@prog_stuff