Так как веб-сайты и онлайн-сервисы с каждым годом становятся все «тяжелее», возрастает необходимость и сжатия данных в вебе. По этой причине Google выпустил новый алгоритм сжатия данных для веб-сайтов — Brotli, что в переводе с швейцарского немецкого означает «маленькая булка хлеба». Алгоритм уже доступен широкой аудитории на GitHub.
Brotli имеет открытый исходный код и позволяет сжимать данные на 20-26% эффективнее, чем его предшественник от Google, алгоритм Zopfli (тоже хлебопекарная продукция из Швейцарии, больше всего похожая внешне на нашу булку-плетенку). Оба алгоритма имеют банальную и простую цель — помочь быстрее загружать веб-страницы.
Разработка Google позволяет сжимать данные без потерь, используя комбинацию алгоритмов LZ77 и кодирование Хаффмана, что ставит Brotli в один ряд с лучшими на данный момент методами общего сжатия данных. В тоже время Brotli работает лучше, чем LZMA и bzip2, а по заверению Google по скорости работы новый алгоритм можно сравнить с Deflate ZLIB.
Особенно остро вопрос сжатия данных стоит для мобильных пользователей и в Google надеются, что разработанная и там технология будет в будущем повсеместно интегрирована в веб-браузеры, что позволит загружать страницы быстрее. В свою очередь это повлечет экономию заряда батареи и снизит объемы веб-трафика.
Возникает вопрос, как именно Google добился подобного сжатия данных, на что они дают следующий ответ (в оригинале, дабы избежать разночтений при переводе):
The higher data density is achieved by a 2nd order context modeling, re-use of entropy codes, larger memory window of past data and joint distribution codes.
Тут можно ознакомиться со сравнением эффективности Brotli и других алгоритмов, которое подготовил Google (ссылку предоставил пользователь evnuh).
Комментарии (12)
VEG
23.09.2015 17:21Mozilla 3 дня пилила тикет 366559, и сегодня там его пометили как FIXED. По идее в Firefox 44 данный алгоритм сжатия будет поддерживаться как один из методов сжатия содержимого для HTTPS трафика. Для HTTP поддержку пока что не включили из-за того, что якобы Accept-Encoding, отличное от «deflate, gzip», сводит с ума некоторые прокси.
Кстати, этот же алгоритм используется и в формате шрифтов WOFF 2.
Deamhan
23.09.2015 20:37+2Довольно голословно. Deflate как раз и есть LZ77 и хаффман, за счёт чего повышена эффективность?
grechnik
24.09.2015 00:45+12Общее соображение: brotli совершенно явно затачивался на текстовые данные. Естественно, тест от Google содержит исключительно тексты. (Интересно, кстати, что PPMd, который на текстах рвёт LZMA по качеству сжатия, в сравнении даже не упомянут — хотя 7-Zip, который там упомянут, его вполне реализует.)
2nd order context modeling
В deflate дерево Хаффмана фиксировано в пределах блока. В английском языке самые частые буквы — 'e' и 't', а 'h' замыкает первую десятку; deflate отразит это короткими кодами для 'e' и 't' и кодом подлиннее для 'h'. Однако, если последняя прочитанная буква — 't', то вероятность получить следующей букву 'h' резко повышается, и вот это deflate не способен осознать при кодировании литералов (конечно, артикль «the», начиная со второго вхождения, будет заменён на ссылку назад… но этого мало).
С русским языком с учётом UTF-8 всё ещё хуже — алгоритмы сжатия оперируют байтами, а не символами. В строке D0 A5 D0 B0 D0 B1 D1 80 D0 B0 D1 85 D0 B0 D0 B1 D1 80 deflate смешает в одну кучу D0/D1 и 80/Bx и будет плохо сжимать и то, и другое. Статистика для 'Ё' (D0 81) и 'с' (D1 81) смешивается, и так далее.
brotli может иметь несколько деревьев Хаффмана в одном блоке и при кодировании/декодировании байта смотрит на два предыдущих байта. Для текста это сильно помогает.
re-use of entropy codes
Формат позволяет иметь несколько наборов деревьев Хаффмана и дёшево переключаться между ними. «Язык» текста, «язык» HTML-тегов, «язык» скриптов на HTML-странице, «язык» inline CSS имеют довольно разные свойства. deflate придётся либо смешивать всё это, либо при переключении каждый раз заново выписывать дерево.
larger memory window of past data
Это аргумент исключительно супротив deflate с его максимальным LZ77-окном в 32K. В том же LZMA можно выставить окно чуть ли не до гигабайта. (Окно в данном контексте — максимально возможный диапазон для ссылок назад, фрагмент исходного файла, в котором упаковщик ищет переиспользуемые последовательности байт и который должен держать в памяти распаковщик. deflate, на минуточку, создавался в те времена, когда 640K хватало всем.)
joint distribution codes
Особенность кодирования. В deflate, грубо говоря, две базовых команды — «запиши литерал» (значение, непосредственно закодированное в команде) и «скопируй последовательность байт такой-то длины с таким-то смещением назад». Литералы и длины подвешены на одном и том же дереве Хаффмана; распаковщик читает код из этого дерева, если значение <256, это литерал, если >256, это ссылка (ровно 256 — конец блока). В brotli одна базовая команда — «запиши столько-то литералов, они закодированы дальше, и потом скопируй последовательность байт такой-то длины с таким-то смещением назад». При этом литералы висят на своём собственном дереве, а на дереве длин расположены пары из длины цепочки литералов и длины ссылки назад (поэтому «joint distribution»). В отличие от предыдущих пунктов, априори неочевидно, насколько это полезно и полезно ли вообще (если длины на самом деле независимы, улучшения не будет, а дерево сильно раздуется), но раз его включили, то какой-то выигрыш, наверное, есть.
Lerg
24.09.2015 03:08+1Чисто ради интереса хотелось бы посмотреть как он справляется не с web/html контентом, а в качестве архиватора общего назначения, разные бинарные файлы, в сравнении с zip/rar/7zip.
evnuh
Статьи про новые модные алгоритмы сжатия обычно не обходятся без сравнительных таблиц. А уж перевед статьи с непереведённой сутью алгоритма — это вообще арт-хаус :)
Привожу ссылку на сравнение (осторожно, от самого гугла, может быть предвзято): www.gstatic.com/b/brotlidocs/brotli-2015-09-22.pdf
ragequit
Спасибо за дополнение.
PaulZi
Скорость сжатия удручает, по сравнению с тем же LZMA.
Rasifiel
Ну если взять 9 степень сжатия, то скорость превышает весь LZMA (да и всех остальных, кроме deflate:1), как и степень сжатия, ну а скорость распаковки вообще прекрасная.
nitso
Если сравнить скорости Brotli и Deflate (остальные не конкуренты) в html-тесте, то в зависимости от коэффициента сжатия, получится:
Brotli:1 коэффициент сжатия 5.217, скорость запаковки 145.2, скорость распаковки 508.4
Deflate:9 сжатие 5.528, скорость запаковки 146, распаковки 484.1
То есть на самом деле они очень близки.
alexeibs
Вот тут www.gstatic.com/b/brotlidocs/brotli-2015-09-22.pdf видно, что при распаковке/запаковке HTML на разных языках brotli-1 эффективнее deflate-1, а brotli-9 эффективнее deflate-9 при сравнимой скорости сжатия и лучшей скорости распаковки. Остальные алгоритмы сильно проигрывают по скорости в этом случае.