Комментарии 12
Статьи про новые модные алгоритмы сжатия обычно не обходятся без сравнительных таблиц. А уж перевед статьи с непереведённой сутью алгоритма — это вообще арт-хаус :)
Привожу ссылку на сравнение (осторожно, от самого гугла, может быть предвзято): www.gstatic.com/b/brotlidocs/brotli-2015-09-22.pdf
Привожу ссылку на сравнение (осторожно, от самого гугла, может быть предвзято): www.gstatic.com/b/brotlidocs/brotli-2015-09-22.pdf
Спасибо за дополнение.
Скорость сжатия удручает, по сравнению с тем же LZMA.
Ну если взять 9 степень сжатия, то скорость превышает весь LZMA (да и всех остальных, кроме deflate:1), как и степень сжатия, ну а скорость распаковки вообще прекрасная.
Если сравнить скорости Brotli и Deflate (остальные не конкуренты) в html-тесте, то в зависимости от коэффициента сжатия, получится:
Brotli:1 коэффициент сжатия 5.217, скорость запаковки 145.2, скорость распаковки 508.4
Deflate:9 сжатие 5.528, скорость запаковки 146, распаковки 484.1
То есть на самом деле они очень близки.
Brotli:1 коэффициент сжатия 5.217, скорость запаковки 145.2, скорость распаковки 508.4
Deflate:9 сжатие 5.528, скорость запаковки 146, распаковки 484.1
То есть на самом деле они очень близки.
Вот тут www.gstatic.com/b/brotlidocs/brotli-2015-09-22.pdf видно, что при распаковке/запаковке HTML на разных языках brotli-1 эффективнее deflate-1, а brotli-9 эффективнее deflate-9 при сравнимой скорости сжатия и лучшей скорости распаковки. Остальные алгоритмы сильно проигрывают по скорости в этом случае.
Mozilla 3 дня пилила тикет 366559, и сегодня там его пометили как FIXED. По идее в Firefox 44 данный алгоритм сжатия будет поддерживаться как один из методов сжатия содержимого для HTTPS трафика. Для HTTP поддержку пока что не включили из-за того, что якобы Accept-Encoding, отличное от «deflate, gzip», сводит с ума некоторые прокси.
Кстати, этот же алгоритм используется и в формате шрифтов WOFF 2.
Кстати, этот же алгоритм используется и в формате шрифтов WOFF 2.
zopfli совместим с gzip, brotli — нет. ждем поддержки в бразуерах.
Довольно голословно. Deflate как раз и есть LZ77 и хаффман, за счёт чего повышена эффективность?
Общее соображение: brotli совершенно явно затачивался на текстовые данные. Естественно, тест от Google содержит исключительно тексты. (Интересно, кстати, что PPMd, который на текстах рвёт LZMA по качеству сжатия, в сравнении даже не упомянут — хотя 7-Zip, который там упомянут, его вполне реализует.)
В 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 может иметь несколько деревьев Хаффмана в одном блоке и при кодировании/декодировании байта смотрит на два предыдущих байта. Для текста это сильно помогает.
Формат позволяет иметь несколько наборов деревьев Хаффмана и дёшево переключаться между ними. «Язык» текста, «язык» HTML-тегов, «язык» скриптов на HTML-странице, «язык» inline CSS имеют довольно разные свойства. deflate придётся либо смешивать всё это, либо при переключении каждый раз заново выписывать дерево.
Это аргумент исключительно супротив deflate с его максимальным LZ77-окном в 32K. В том же LZMA можно выставить окно чуть ли не до гигабайта. (Окно в данном контексте — максимально возможный диапазон для ссылок назад, фрагмент исходного файла, в котором упаковщик ищет переиспользуемые последовательности байт и который должен держать в памяти распаковщик. deflate, на минуточку, создавался в те времена, когда 640K хватало всем.)
Особенность кодирования. В deflate, грубо говоря, две базовых команды — «запиши литерал» (значение, непосредственно закодированное в команде) и «скопируй последовательность байт такой-то длины с таким-то смещением назад». Литералы и длины подвешены на одном и том же дереве Хаффмана; распаковщик читает код из этого дерева, если значение <256, это литерал, если >256, это ссылка (ровно 256 — конец блока). В brotli одна базовая команда — «запиши столько-то литералов, они закодированы дальше, и потом скопируй последовательность байт такой-то длины с таким-то смещением назад». При этом литералы висят на своём собственном дереве, а на дереве длин расположены пары из длины цепочки литералов и длины ссылки назад (поэтому «joint distribution»). В отличие от предыдущих пунктов, априори неочевидно, насколько это полезно и полезно ли вообще (если длины на самом деле независимы, улучшения не будет, а дерево сильно раздуется), но раз его включили, то какой-то выигрыш, наверное, есть.
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»). В отличие от предыдущих пунктов, априори неочевидно, насколько это полезно и полезно ли вообще (если длины на самом деле независимы, улучшения не будет, а дерево сильно раздуется), но раз его включили, то какой-то выигрыш, наверное, есть.
после «булки хлеба» перестал читать ;-)
Чисто ради интереса хотелось бы посмотреть как он справляется не с web/html контентом, а в качестве архиватора общего назначения, разные бинарные файлы, в сравнении с zip/rar/7zip.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Brotli — новый алгоритм сжатия веб-данных от Google