Новый алгоритм Zopfli улучшает сжатие zlib на 3-8%

Один из сотрудников Google в свободное время разработал новый алгоритм сжатия Zopfli ^[1], который на 3,7-8,3% эффективнее, чем стандартная библиотека zlib на максимальном уровне сжатия. Изначально алгоритм создавался для формата сжатия без потерь WebP, но его можно применять и для другого контента.

Новый алгоритм является реализацией стандартных алгоритмов Deflate, поэтому он совместим с zlib и gzip, а разархивирование данных уже поддерживается всеми браузерами. Достаточно подключить Zopfli на сервере. Например, его можно использовать с веб-сервером Nginx без изменений в модуле gzip ^[2], просто указав новый «прекомпрессор».

Правда, сжатие с помощью Zopfli требует примерно в 100 больше ресурсов, чем zlib, зато декомпрессия в браузере осуществляется с той же скоростью.

В статье (pdf) ^[3] Автор объясняет, за счёт каких оптимизаций удалось достигнуть повышения уровня сжатия. Как известно, Deflate использует комбинацию алгоритма Хаффмана и алгоритма LZ77. Первый кодирует символы сообщения кодами переменной длины, в зависимости от частоты встречаемости этих символов. Второй работает по принципу «скользящего окна», когда второе и последующие вхождения некоторой строки символов в сообщении заменяются ссылками на её первое вхождение. Существующие реализации Deflate применяют различные эвристики для поиска подходящих вхождений и оптимизации анализа данных перед кодированием, чтобы понять, какой метод лучше применять в каждом случае, с построением хеш-таблицы. Уровень сжатия (от -1 до -9) определяет количество времени и ресурсов, которое выделяется для использования эвристик, обычно путём изменения размеров строк для поиска в хеш-таблице.

Как сказано в статье автора, Zopfli использует более ресурсоёмкие техники сжатия, основанные на моделировании энтропии и алгоритме поиска кратчайшего пути в графе всех возможных представлений Deflate.

Zopfli позволяет указывать уровни сжатия от 5 до 2000. В статье (pdf) ^[3] приводится сравнение уровня сжатия в разных тестах.

На реальных файлах, например, несжатом jQuery, сравнение архиваторов выглядит примерно так ^[4]:

Файл: 268381 байт
Zopfli (-i1000) 75730 байт, 950 мс
Gzip (-9) 79388 байт, 30 мс

Правда, по времени Zopfli проигрывает всем, он рабоатет примерно в 81 раз медленнее самого быстрого алгоритма gzip-9. Опять же нужно подчеркнуть, что декомпрессия в браузере осуществляется с такой же скоростью.

Установка и использование Zopfli:

git clone https://code.google.com/p/zopfli/
cd zopfli
make
chmod +x zopfli
./zopfli >FILENAME>

Автор: alizar

Источник ^[5]