Пользователь
57,4
рейтинг
1 марта 2013 в 11:16

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

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

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

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

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

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

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



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

Файл: 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
карма
751,5
рейтинг 57,4
Пользователь
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (42)

  • –41
    Это все фигня, вот у Алексея Бабушкина алгоритм сжимает с 2Гб в 2Кб.
    А самое главное, он поделился своим секретом. Надо данные перевести в HEX, а потом DEC. А когда получите большое число, надо прибавить нолик в начало, и найти такое число, которое при деление на что-то, получит такое же число :) Обычно на это, у Алексея уходило около 2х часов, но он пообещал исправить алгоритм.
    Взято со страницы ВК: vk.com/mefistofell
    • +63
      Изначально хотел в топик добавить про Бабушкина, а потом думаю — зачем, всё равно появится в первом комментарии. :)
    • +30
      Когда в соответствующем топике шло обсуждение, я по-быстрому набросал программку, представляющую длинную десятичную дробь в виде максимально короткой обыкновенной (и, думаю, не я один — многие хотя бы попробовали поиграться с подборщиком дробей).
      По результатам «исследования» хотел даже написать статью на Хабр, но потом решил, что пользы от такой статьи ноль. Но, если кратко, результат таков.
      За некоторыми исключениями, в общем случае в обыкновенной дроби получается ровно столько же цифр, сколько и в десятичной, например:
      0.55 = 5/9

      0.123 = 8/65

      0.1235=11/89

      1513748957234095723948572348957234589
      23759823495723489572349572358973248977 =
      6451435714817374103222462663515810501 / 42618927557217687537475866931148217146

      Значительный выигрыш можно получить при сжатии периодических дробей вида 0.X(Y)n с повторяющимся «хвостом», а также в некоторых частных случаях, довольно редких:
      0.55555555555 = 5/9

      1234567 = 10/81

      111111111111111111166666666666688888888888888888
      888555555555555555555559999999999977777777777666
      666666666666888888888888888999999999966677777555
      554444444466666669000000000004444444444444433333 =
      40794740312874221278684064243002291903427193257
      006746411080848729199282910340405775349993739573 / 367152662815867991324580246779013200935991442325
      290302640364562363935155639050137213967980478817

      Причём от длины дроби этот самый выигрыш никак не зависит (последний пример особенно показателен, когда дробь с громаднейшим количеством повторений даёт выигрыш в 1 цифру). Если посмотреть статистику распределения «выигрышных» дробей на числовой оси, получается довольно удручающая картина: видно, что некоторое сжатие возможно всего в 2.7% случаев, причём эти счастливые случаи распределены весьма равномерно, и из них подавляющее большинство даёт выигрыш всего 1 цифру (по-видимому, это связано с тем, что у обыкновенных дробей нет ограничений по точности — переводя их в десятичные, можно вычислить сколь угодно много знаков после запятой).
      Переход к восьмеричной системе счисления никак не поменял общей картины (а переделывать библиотеку BigNumber под двоичные и шестнадцатеричные числа мне было откровенно лень).
      В итоге, даже очень хитро извратившись (например, нарезав файл на кусочки небольшой длины и переведя в дробь каждый кусочек), получим крайне ничтожный выигрыш, который нацело съедают два факта:
      • Необходимо хранить длину каждого кусочка, иначе мы просто не поймём, сколько знаков после запятой нужно вычислять при распаковке
      • Коль размеры чисел в обыкновенной дроби различны, нам как-то нужно указывать их длины (или позицию символа дроби "/" в строке)

      Тем не менее, на основе этой «идеи» возможно написать алгоритм, по эффективности сжатия близкий к RLE.
      • +2
        Насколько я знаю существует оптимальный способ представления дробей! И намного красивее и не зависит от системы исчесления.
        Непрерывная дробь (цепная дробь). Доказано, что частичные дроби дают наилучшее приближение в виде простых дробей для иррациональных чисел. + Квадратные корни представимы в виде периодической цепной дроби, что позволяет существенно сжать информацию.
        В общем, если есть необходимость записать огромную в дробь в компактной записи используйте ряд коэфициентов цепной дроби.

        Существует хорошая книга Арнольда по этому поводу www.mccme.ru/mmmf-lectures/books/books/book.14.pdf.
        • 0
          Есть арифметическое кодирование, которое в результате некоторых преобразований превращает любую последовательность данных в некую рациональную дробь (возможно, довольно длинную). Дальше мы приближаем нашу дробь двоичной дробью и получаем выходной файл.

          Арифметическое сжатие – самое эффективное сжатие (даже теоретически – доказано, что лучше нельзя), не учитывающее последовательности символом (все символы сжимаются независимо).
  • +4
    Судя по времени работы и использованию эвристики, алгоритм скорее надо сравнивать с PPM, PAQ и подобным семейством.
    • +5
      Интереса ради запаковал тестовые файлы с помощью PPMd (есть в 7zip):
      Canterbury:
          Zopfli - 669,993
          PPMd   - 574,757
      enwik8:
          Zopfli - 34,995,756
          PPMd   - 22,506,231
      

      В этой категории от алгоритма тоже толку мало.
      • +4
        Вы забываете об обратной совместимости. ppmd не распакуется как любой зип.
        • 0
          Достаточно подключить Zopfli на сервере.

          Как я понял, получается не простой *zip, а все-таки собственный формат.
          Если это не так, то да, зачитываем в плюс алгоритма. Вот только относительная степень сжатия все равно столь мала, что он имеет смысл только на десятках и сотнях гигабит, imo.
          • +3
            на сервере для сжатия, распаковывает его просто браузер
      • +5
        Алгоритм интересен тем, что в браузере уже есть его реализация, чего не скажешь о PPM.
        • +4
          Google ничего не стоит в один момент добавить в Chrome и на свои CDN новый алгоритм. Они проделывали это тысячу раз начиная с транспортного уровня (quic), заканчивая webm, webp, spdy, NaCl, dart, и т. д. Стандарт HTTP предусматривает поле Accept-Encoding, которое сейчас обычно «gzip, deflate» и никто не запрещает сделать «ppmd, gzip, deflate». Тысячи сайтов, которые в хроме дают на четверть меньше трафика для скриптов — чем не конкурентное преимущество? Вопрос не в том, что нет реализации, а в том, что нет алгоритма-кандидата, который бы обеспечивал хорошее соотношение затрат на распаковку и степени сжатия. Что PPMd, что LZMA(2), оба расжимаются значительно медленнее gzip. Остаются вариации PPM? Появление новых алгоритмов в Accept-Encoding это только вопрос времени.
          • +3
            Они уже добавляли bzip2 (убрали) и sdch (добавили, но никто не использует). Это ещё не факт, что будут пользоваться.
      • +1
        Не совсем корректно сравнивать контекстно-независимый алгоритм deflate и контекстно-зависимый PPMd на текстовых данных.
        Я понимаю, что все хотят использовать zopfli на стороне сервера и сжимать html, js и сss.

        Нужно бы на бинарных данных проверить (любят на Firefox тестировать, кажется).
        • 0
          Тестовый набор Canterbury содержит в себе бинарные файлы. На нем тоже есть сравнение.
          • 0
            Я уже посмотрел – там один xls-файл бинарный. Но он составляет только треть архива. Остальное – чистые тексты.
            • 0
              Эмм… А ptt5, sum? Суммарно 56% выходит. Понятно, что мелкие архивы, но все же.
              • +1
                Значит, не заметил. Прошу прощения.
                Всё равно zopfli выглядит какой-то тупиковой веткой.
                • 0
                  Вот с этим согласен.
                • 0
                  Скорее не тупиковой веткой, а собственно тупиком, т.е. логичным (и возможно последним?) пределом развития deflate-подобных алгоритмов.
  • +4
    Статику хорошо будет жать, а вот на лету со 100 кратным увеличением нагрузки — как-то сомнительно.
    • +2
      Некая компрессия в браузере смысл имеет, но, все же, жать даже gzip-9 стандартные динамические (т.к. сжатие будет происходить на каждый запрос) страницы сайта — уже барство, ибо загрузка сервера выше и дольше, а скорость загрузки при этом у клиента меняется в сравнении с gzip-5 не сильно.

      На этом фоне заторомозить сжатие страницы еще во много раз — идея очень редко нужная, ибо уж очень нечастая задача ее оправдывает.

      gzip_static, соглашусь, более вероятный кандидат для использования нового алгоритма. Другое дело, что, если при сжатии «обычным» и новым алгоритмами (и учитывая их разницу во времени работы) разница в кол-ве пакетов для передачи того же файла будет или очень небольшой, или ее вообще не будет, то смысла возиться нет вообще — а, судя по тестам, так оно почти со всеми страницами и будет.
  • +2
    так себе результаты

    на jquery-1.8.3-min разница в 120 байт (7z gz ultra против -i1000)
    на 40kb css файле на 60% состоящем из base64 разница 300 байт

    даже для gzip_static, я бы не стал возиться
    • 0
      Думаю, смысл использования от использования данного алгоритма сжатия будет лишь у проектов, у которых огромный трафик, например Google или Facebook.
      • +7
        Ещё для CDN для того же jQuery и т.п., типа ajax.googleapis.com. Там столько трафика, что даже 3% это уже дофига.
        • 0
          Больше % экономии можно добиться хорошей настройкой работы с TCP протоколом, например, отсылать ACK и FIN вместе с данными (TCP_CORK).
  • +3
    Deflate-алгоритмы сжатия не являются лидерами по качеству / скорости / ресурсоемкости
    Хотя хорошая интегральная характеристика по этим трем компонентам и привела к повсеместному распространению
    • 0
      … а так же популярность формата zip в досовские времена
      • +3
        между прочим, архиваторы pkzip/pkunzip в «ранние досовские времена» использовали другие методы сжатия.
        ru.wikipedia.org/wiki/Pkzip
        Deflate появился только в 93-ем году, к тому времени «зипование» уже было популярным явлением
        (Ой, щас буду вспоминать White Bear BBS — держите меня семеро!)
        Были всякие ARJ / LHA / PKARC / HA и ACB
        • 0
          Не сыпьте соль на рану… ARJ… моя преееелесть… ^^
        • +2
          Из перечисленных вами только HA резко выделялся во времена BBS. Ой, как же тяжело он на моем 286 он распаковывался… Но вся литература обычно как раз сисопами и жалась в HA. Как сейчас помню: скачал «Лабиринт отражений», и пару минут наблюдал «HA 0.99 © Harri Hirvola»
          • +1
            ha — реализация ppm ;)
  • –3
    Картинка смешная — четыре символа заменяются на шесть, что как бы намекает на то что это не сжатие совсем, а наоборот символов стало на 33% больше.
    • 0
      А что короче между «лето» и [4,12]? :)
      Там же образное отображение идеи, а не побайтный дамп.
      Если взять подход RLE, то [4,12] превращается в 2 байта. При исходных 4 (ABCD).
  • +3
    Для Джавовских JAR и Андройдовских APK отлично подойдет же!
  • 0
    Мне одному кажется, что результаты в сравнении с ресурсоемкостью алгоритма настолько сомнительны, что так и остался бы алгоритм никому не известным, если бы не имя Google?
  • +2
    Кстати, на основе этого Zopfli можно написать улучшенный вариант PNGOUT/OptiPNG! Вот и профит от него для Web-а будет.
    • +1
      уже сделано PNGZopfli
      И я уже тестирую для внедрения в Image Catalyst
      • 0
        Прекрасный проект, и прекрасное применение данного алгоритма! Плюс вам в карму, и семь футов под килем!
  • 0
    (ошибся уровнем, комментарий адресовался Lorents
  • 0
    FAIL
    13:~# wget https://zopfli.googlecode.com/files/zopfli-1.0.0.zip
    13:~# unzip zopfli-1.0.0.zip
    13:~# zip -9 -r test.zip zopfli-1.0.0
    13:~# ls -l zopfli-1.0.0.zip test.zip
    -rw-r--r-- 1 root root 57822 Май 27 16:07 test.zip
    -rw-r--r-- 1 root root 57873 Апр 25 20:11 zopfli-1.0.0.zip
    
  • –1
    Забавно, что все еще имеет смысл накатить поверх deflopt'ом

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.