Brotli

Brotli — это алгоритм сжатия данных без потерь, разработанный компанией Google. Он относится к классу алгоритмов, основанных на комбинации LZ77-подобного кодирования (словарное сжатие) и контекстного моделирования с использованием кода Хаффмана второго порядка. Brotli предназначен для достижения высокой степени сжатия, особенно для текстовых данных и веб-контента, при относительно высокой скорости распаковки.

История

Разработка Brotli началась в 2013 году как внутренний проект Google. Первоначально алгоритм был реализован в рамках библиотеки сжатия Zopfli, которая, в свою очередь, была улучшенной версией Deflate (алгоритма, используемого в gzip и PNG). Однако Zopfli был ориентирован на максимальное сжатие за счёт очень медленного кодирования, что делало его непригодным для динамического сжатия в реальном времени.

В сентябре 2015 года Google выпустил первую стабильную версию Brotli (RFC 7932). Алгоритм был назван в честь швейцарской выпечки — брёли (нем. Brötli). В отличие от Zopfli, Brotli был спроектирован с нуля для обеспечения высокой степени сжатия при умеренной скорости кодирования и высокой скорости декодирования. Это достигалось за счёт использования статического словаря, содержащего часто встречающиеся в веб-контенте фразы и слова на разных языках, и более сложного контекстного моделирования.

В 2016 году Brotli был включён в стандарт HTTP/2 как один из рекомендованных методов сжатия. В 2020 году вышла версия 2.0 (RFC 8996), которая, однако, не получила широкого распространения из-за патентных ограничений и сложностей с реализацией. Основная версия Brotli остаётся версией 1.x.

Алгоритм сжатия

Brotli использует двухэтапный подход к сжатию, комбинируя словарное сжатие с энтропийным кодированием.

Словарное сжатие (LZ77)

На первом этапе алгоритм ищет повторяющиеся последовательности байт во входных данных. В отличие от классического LZ77, Brotli использует не только динамический словарь (словарь, построенный из ранее обработанных данных), но и статический, предопределённый словарь. Этот статический словарь содержит около 13 000 наиболее часто встречающихся в веб-контенте слов и фраз на разных языках, включая английский, русский, китайский, японский и другие. При обнаружении совпадения с любым из этих словарей, алгоритм кодирует его как ссылку на соответствующую запись, что значительно повышает степень сжатия для текстовых данных.

Контекстное моделирование

После словарного сжатия Brotli применяет контекстное моделирование второго порядка. Это означает, что вероятность следующего символа (или кодового слова) зависит не только от предыдущего символа, но и от контекста — например, от того, является ли текущий символ частью литерала (неповторяющейся последовательности) или частью ссылки на словарь. Алгоритм использует несколько контекстных моделей, которые выбираются в зависимости от типа данных (текст, HTML, CSS, JavaScript и т.д.).

Кодирование Хаффмана

Для финального кодирования используется статический код Хаффмана. В отличие от динамического кодирования Хаффмана, используемого в gzip, Brotli предварительно вычисляет оптимальные кодовые таблицы на основе статистики входных данных. Это позволяет достичь более высокой степени сжатия, но требует больше времени на этапе кодирования.

Характеристики

Степень сжатия

Brotli обеспечивает значительно более высокую степень сжатия по сравнению с gzip (обычно на 15–25% лучше для текстовых данных) и Deflate (на 20–30% лучше). Для веб-контента, такого как HTML, CSS и JavaScript, Brotli может сжимать данные в 2–3 раза сильнее, чем gzip. Однако для уже сжатых данных (например, JPEG, PNG, MP3) Brotli не даёт преимущества, так как они уже содержат мало избыточности.

Скорость

Скорость кодирования Brotli значительно ниже, чем у gzip, особенно на высоких уровнях сжатия (уровни 9–11). Это делает его малопригодным для динамического сжатия в реальном времени, но идеальным для статического сжатия контента, который будет многократно запрашиваться (например, статические файлы на веб-сервере). Скорость декодирования, напротив, очень высока — она сопоставима со скоростью декодирования gzip и Deflate. Это делает Brotli удобным для клиентских устройств, где распаковка происходит на стороне браузера.

Уровни сжатия

Brotli поддерживает 11 уровней сжатия (от 0 до 11), где 0 — минимальное сжатие, 11 — максимальное. Уровни 0–4 обеспечивают быстрое кодирование с умеренным сжатием, уровни 5–9 — хороший баланс, уровни 10–11 — максимальное сжатие за счёт очень медленного кодирования. По умолчанию в большинстве реализаций используется уровень 6.

Применение

Веб-серверы и браузеры

Основное применение Brotli — сжатие веб-контента. Все современные браузеры (Google Chrome, Mozilla Firefox, Apple Safari, Microsoft Edge) поддерживают распаковку Brotli с 2015–2016 годов. Веб-серверы (Apache, Nginx, IIS) также поддерживают Brotli, обычно через модули или плагины. Для использования Brotli необходимо, чтобы клиент (браузер) в HTTP-запросе указал заголовок Accept-Encoding: br, а сервер отвечал с заголовком Content-Encoding: br.

Статическое сжатие

Brotli часто используется для предварительного сжатия статических файлов (HTML, CSS, JavaScript) на этапе сборки веб-приложения. Это позволяет снизить размер передаваемых данных без увеличения нагрузки на сервер во время обработки запросов. Например, инструменты сборки, такие как Webpack, Gulp или Vite, могут автоматически создавать Brotli-сжатые версии файлов.

Сжатие в HTTP/2 и HTTP/3

Brotli является рекомендованным методом сжатия для HTTP/2 и HTTP/3. В этих протоколах сжатие может применяться не только к телу ответа, но и к заголовкам (через HPACK или QPACK), но Brotli используется именно для сжатия тела.

Другие применения

Помимо веба, Brotli используется в некоторых системах хранения данных (например, в базах данных) и в архиваторах (например, в 7-Zip). Однако он не так распространён, как gzip или LZMA, из-за более высокой сложности кодирования.

Критика

Основная критика Brotli связана с его медленной скоростью кодирования на высоких уровнях сжатия. Это делает его непригодным для динамического сжатия в реальном времени, например, для сжатия потокового видео или аудио. Также Brotli требует больше памяти для кодирования и декодирования по сравнению с gzip, что может быть проблемой для устройств с ограниченными ресурсами.

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

Интересные факты

• Название «Brotli» происходит от швейцарского немецкого слова «Brötli» (булочка), что является отсылкой к названию другого алгоритма сжатия Google — Zopfli (назван в честь швейцарской выпечки Zopf).
• В 2015 году Google опубликовал Brotli под лицензией Apache 2.0, что способствовало его широкому распространению.
• Brotli был включён в стандарт HTTP/2 в 2016 году, а затем и в HTTP/3.
• В 2020 году вышла версия Brotli 2.0, которая предлагала ещё более высокую степень сжатия, но не получила поддержки из-за патентных ограничений и сложностей с реализацией.

Источники

• RFC 7932 — Brotli Compressed Data Format
• RFC 8996 — Brotli Compressed Data Format (версия 2.0)
• Google Brotli — официальная документация и исходный код
• Статья «Brotli: A New Compression Algorithm for the Web» на сайте Google Developers
• Сравнительный анализ алгоритмов сжатия gzip, Deflate и Brotli в различных исследованиях