Как патенты на LZW привели к gzip, а веб к Brotli

gzip и Brotli часто ставят рядом как старый и новый алгоритмы, после чего сравнение сводят к одному проценту экономии. Такое описание пропускает главное: gzip появился как практический выход из патентной проблемы вокруг Unix-утилиты compress, а Brotli создавался для более плотного представления данных, передаваемых через интернет. Оба формата используют идеи семейства Lempel-Ziv, поэтому Brotli продолжает прежнюю линию развития, а не начинает историю сжатия заново.

Почему GNU понадобилась замена compress

В 1980-е годы в Unix широко применялась утилита compress, работавшая на алгоритме LZW. Заявки на связанные с ним патенты Unisys и IBM были поданы в 1983 году, статья Терри Уэлча с описанием метода вышла в 1984-м, а американский патент Уэлча был выдан в декабре 1985 года. Для проекта свободного программного обеспечения это создавало не абстрактный юридический риск, а прямое ограничение: совместимый компрессор нельзя было спокойно распространять без лицензирования.

Проект GNU прямо называет патенты Unisys и IBM причиной разработки замены. Первую программу gzip написал Жан-Лу Гайи, а Марк Адлер подготовил часть для распаковки. К 1992 году gzip вошёл в инструментарий GNU и создавал собственный формат вместо LZW-совместимого потока, хотя распаковку старых файлов compress сохранили, поскольку патентные формулировки различали кодирование и декодирование.

Слово zip в названии не означает, что gzip является разновидностью ZIP-архива. Формат ZIP появился у PKWARE в 1989 году и умеет собирать несколько файлов вместе с каталогом и метаданными. gzip обычно оборачивает один поток данных, поэтому каталог Unix сначала часто объединяют командой tar, а затем сжимают получившийся поток.

Связь между форматами проходит через DEFLATE. По исторической справке gzip первая версия этого метода появилась в публичном ZIP 0.9 Фила Каца в июле 1991 года, а позднее вошла в линию формата ZIP 2.0. gzip использовал тот же формат сжатого потока в другой оболочке. В мае 1996 года RFC 1951 закрепил DEFLATE, а RFC 1952 описал формат gzip. Это была стандартизация уже работающих форматов: сам RFC 1951 отмечает, что его версия 1.3 лишь перевела существующую спецификацию в стиль RFC, и отдельно называет Фила Каца автором формата DEFLATE.

Как DEFLATE превращает повторы в ссылки

DEFLATE рассматривает вход как последовательность байтов и ищет фрагменты, которые уже встречались в предыдущих 32 КБ. Вместо повторной записи такого фрагмента можно сохранить пару из длины совпадения и расстояния назад. Если строка background-color встречается в CSS несколько раз, очередное вхождение способно превратиться в короткую ссылку на предыдущие байты.

Оставшиеся буквальные байты, длины и расстояния затем кодируются с помощью деревьев Хаффмана. Часто встречающиеся значения получают более короткие битовые коды, а редкие более длинные. Компрессор может тщательнее искать совпадения и получить меньший результат либо завершать поиск раньше ради скорости; формат при этом остаётся тем же, поскольку RFC определяет допустимый поток, а не единственную реализацию кодировщика.

gzip добавляет вокруг DEFLATE заголовок и завершающие данные, включая CRC32 и размер исходного потока по модулю 2³². Поэтому raw DEFLATE, zlib-wrapped DEFLATE и gzip нельзя считать взаимозаменяемыми строками, даже когда внутри используется один метод. У каждого варианта своя оболочка, а распаковщик должен знать, какую именно он получил.

Brotli развивает знакомую идею

Google представила Brotli в конце 2013 года, а его формат был опубликован как RFC 7932 в июле 2016-го. Авторы создавали универсальное сжатие с особым вниманием к плотности интернет-данных и стоимости декодирования, что подробно описано в исследовании команды Brotli.

Brotli тоже заменяет повторяющиеся фрагменты ссылками назад и использует коды Хаффмана, но располагает более гибким окном, контекстным моделированием и встроенным словарём на 122 784 байта. В словаре собраны слова и фрагменты из естественных языков и программного текста, а 121 преобразование позволяет получать варианты с префиксами, суффиксами и изменением регистра. Сжатый поток может сослаться на такую запись даже в начале небольшого документа, когда собственная история повторов ещё почти пуста.

Именно поэтому Brotli часто особенно полезен для HTML, CSS, JavaScript, JSON и другого текста, однако встроенный словарь не гарантирует победу на каждом файле. Длинный документ с большим количеством собственных повторов может хорошо сжаться обоими форматами, короткий случайный набор байтов способен увеличиться из-за служебных данных, а JPEG, WebP, MP4 и архивы обычно уже используют специализированное сжатие. Универсального преимущества на 20 или 30 процентов без указания набора данных, реализации и уровня качества не существует.

В вебе учитывается не только размер

Браузер сообщает серверу поддерживаемые варианты через Accept-Encoding, а сервер помечает выбранное представление заголовком Content-Encoding. В актуальном реестре IANA присутствуют и gzip, и br, поэтому сервер может хранить несколько вариантов одного ресурса и выбрать подходящий для конкретного клиента.

Для статических файлов высокая стоимость кодирования обычно приемлема: CSS или JavaScript можно сжать один раз при сборке и затем многократно отдавать готовый файл. У динамического HTML или JSON кодирование выполняется во время запроса, поэтому дополнительная экономия трафика конкурирует с процессорным временем и задержкой ответа. Более высокий уровень качества заставляет компрессор дольше искать удачное представление; в официальной реализации Brotli диапазон качества идёт от 0 до 11, и больший уровень в общем случае означает более медленное кодирование.

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

Что показывает GZip & Brotli Tool

GZip & Brotli Tool принимает UTF-8 текст и локально сжимает его в gzip, zlib-wrapped DEFLATE, raw DEFLATE или Brotli. Для первых трёх вариантов используется браузерный CompressionStream, а Brotli обрабатывает локально подключённая WebAssembly-сборка. Текущая версия инструмента запускает Brotli с качеством 11 и не предоставляет переключателя уровня, тогда как параметры нативного DEFLATE определяет браузер.

Результат можно представить как Base64 или Hex, но оба варианта являются текстовым кодированием готовых байтов, а не дополнительным сжатием. Показанная статистика сравнивает исходный UTF-8 с сырым сжатым потоком до преобразования в Base64 или Hex, поэтому длина скопированной строки будет больше указанного числа байтов. На коротком вводе сам сжатый поток также может оказаться длиннее исходника, и инструмент честно показывает положительную разницу.

В режиме распаковки можно явно выбрать контейнер и кодирование либо воспользоваться автоматическим определением. У gzip есть узнаваемая сигнатура, у zlib собственный заголовок, а raw DEFLATE и Brotli не имеют универсального magic number, поэтому для них автоопределение перебирает декодеры и остаётся эвристикой. Если данные неоднозначны, формат и Base64 либо Hex лучше указать вручную.

Инструмент подходит для изучения форматов, проверки небольших текстовых payload и сравнения одного ввода, но не заменяет серверный benchmark. Все операции выполняются в памяти браузера, данные никуда не отправляются, а для выбора production-настроек всё равно нужно измерить реальные ресурсы при сопоставимых уровнях качества.

Похожие инструменты

GZip и Brotli СжатиеСжатие текста в GZip и Deflate в формате Base64 и обратная распаковка в читаемый текст в браузере.Криптографический наборОпределяйте неизвестный шифр по алфавиту, индексу совпадений, частотам букв и повторам Касиски; кодируйте сообщение сразу всеми обратимыми шифрами с проверкой обратного преобразования; шифруйте через AES-256-GCM и решайте Цезаря, Виженера, Плейфера, ADFGX, Бифид или «забор» в верстаке — всё в браузере.Генератор хешейСчитайте MD5, SHA-1, SHA-256/384/512, SHA-3 и CRC32 из текста или файлов вживую по мере ввода, с HMAC и сравнением хешей.JSON ToolboxПроверяйте синтаксис, форматируйте или минифицируйте данные и просматривайте вложенные API-ответы и конфиги в виде дерева.