Google Zopfli – приятное сжатие, стыд о скорости

Google предлагает нам новый инструмент сжатия без потерь под названием Zopfli. он может создавать zip-файлы размером до 5% без каких-либо негативных последствий для конечного пользователя. Есть одна загвоздка – Zopfli работает намного медленнее, чем ваш средний почтовый индекс.

Алгоритмы сжатия часто асимметричны в отношении нагрузки, которую они возлагают на компрессор и декомпрессор. Если вы можете сэкономить еще несколько байтов, усердно работая с компрессором, это может быть большим преимуществом для декомпрессора без дополнительной работы. То же самое и с алгоритмом Deflate на основе LZ77, который используется рядом программ сжатия – Pkzip и т. Д. – для создания файлов в формате zip.

LZ77 или Liv-Zempel 77 – это метод сжатия на основе словаря, который сканирует исходный файл и создает словарь битовых шаблонов, которые повторяются в файле. Сжатие достигается заменой битовых шаблонов в файле ссылкой на словарь фиксированного размера. Это хорошо работает на практике и является основой метода Deflate, который сначала использует сжатие LZ77, за которым следует кодирование Хаффмана.

Насколько эффективен LZ77, зависит от размера и частоты словарных статей. Если вы замените множество подстрок словарными ссылками, то то, сколько памяти вы сэкономите, будет зависеть от их размера и от того, сколько раз они встречаются в исходном файле. Качество сжатия зависит от того, как вы выбираете словарные статьи.

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

Если вы потратите больше времени на сжатие, вы сможете достичь более высоких степеней сжатия без необходимости каким-либо образом изменять инструменты распаковки.

На практике Deflate еще более сложен, потому что он использует два метода сжатия, LZ77 и кодирование Хаффмана, и оба могут быть настроены, чтобы изменить степень сжатия.

Zopfli назван в честь рецепта швейцарского хлеба – почему я не уверен. Это программа на языке C с открытым исходным кодом, которую вы можете использовать для реализации вашей собственной версии алгоритма сжатия. Он позволяет уменьшить размер сжатого файла на 3–8% за счет применения метода исчерпывающего поиска лучшего словаря. Он основан на итеративном моделировании энтропии и поиске кратчайшего пути для нахождения пути с низкой стоимостью битов через граф всех возможных представлений данных с дефляцией.

После сжатия файла с помощью Zopfli его можно распаковать с помощью стандартной декомпрессии gzip, Zip, PNG или HTTP. Другими словами, выигрывают все, а файлы меньшего размера означают более быструю загрузку, меньшую пропускную способность и более длительное время автономной работы на мобильных устройствах.

Теперь о недостатках.

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

Добавить комментарий