Алгоритм Deflate

Алгоритм Deflate — это алгоритм сжатия данных без потерь, основанный на комбинации алгоритма LZ77 и кодирования Хаффмана. Он был разработан Филом Кацем в 1993 году для программы PKZIP и впоследствии стал широко распространённым стандартом сжатия, используемым в форматах ZIP, gzip, PNG, HTTP (сжатие содержимого) и многих других. Deflate обеспечивает высокую степень сжатия при относительно низких требованиях к памяти и вычислительным ресурсам, что делает его эффективным для общего назначения.

История

Алгоритм Deflate был создан Филом Кацем в рамках работы над архиватором PKZIP 2.0. До этого основным стандартом сжатия в PKZIP был алгоритм Implode, который также использовал LZ77, но с более простым энтропийным кодированием. Кац разработал Deflate как более совершенный метод, способный конкурировать с алгоритмами LZW и LHA, которые доминировали на рынке в начале 1990-х годов.

В 1996 году спецификация Deflate была опубликована в виде RFC 1951 (DEFLATE Compressed Data Format Specification version 1.3). Это сделало алгоритм открытым и свободным для использования, что способствовало его быстрому распространению. В отличие от LZW, который был запатентован компанией Unisys, Deflate не имел патентных ограничений, что стало ключевым фактором его популярности в открытых форматах, таких как PNG и gzip.

Принцип работы

Deflate состоит из двух последовательных этапов: сначала данные обрабатываются алгоритмом LZ77, а затем результат кодируется с помощью кода Хаффмана.

Этап 1: LZ77 (скользящее окно)

Алгоритм LZ77 заменяет повторяющиеся последовательности байтов ссылками на предыдущие вхождения. Для этого используется «скользящее окно» — буфер фиксированного размера (обычно 32 КБ), в котором хранятся последние обработанные данные.

• Если алгоритм находит последовательность байтов, которая уже встречалась в окне, он заменяет её на пару (расстояние, длина). Расстояние — это количество байтов назад от текущей позиции до начала совпадения, а длина — количество совпадающих байтов.
• Если совпадение не найдено или его длина меньше минимальной (обычно 3 байта), байт кодируется как литерал (непосредственное значение).

Максимальная длина совпадения составляет 258 байтов, а максимальное расстояние — 32 768 байтов (2^15). Эти ограничения заданы спецификацией RFC 1951.

Этап 2: Кодирование Хаффмана

После этапа LZ77 данные представляют собой последовательность символов двух типов: литералы (0–255) и коды длины (257–285), а также специальный символ конца блока (256). Коды длины всегда сопровождаются дополнительными битами, уточняющими точную длину совпадения, и кодами расстояния (0–29), которые также имеют дополнительные биты.

Для сжатия этой последовательности используется кодирование Хаффмана — метод построения префиксных кодов переменной длины на основе частоты встречаемости символов. Более частые символы получают более короткие коды.

Deflate поддерживает два режима:

• Фиксированные коды Хаффмана — предопределённая таблица кодов, не зависящая от данных. Используется для простоты и скорости, но даёт меньшую степень сжатия.
• Динамические коды Хаффмана — таблица строится на основе статистики конкретного блока данных. Требует передачи самой таблицы в заголовке блока, что увеличивает накладные расходы, но позволяет лучше сжимать данные.

Формат данных

Сжатый поток Deflate состоит из последовательности блоков. Каждый блок начинается с 3-битного заголовка:

• 1 бит — флаг BFINAL (1, если это последний блок).
• 2 бита — тип сжатия BTYPE:
• 00 — не сжато (копируется как есть).
• 01 — сжато фиксированными кодами Хаффмана.
• 10 — сжато динамическими кодами Хаффмана.
• 11 — зарезервировано (ошибка).

Для несжатых блоков (BTYPE=00) данные выравниваются по границе байта и содержат длину блока (16 бит) и её побитовое дополнение для проверки целостности.

Для сжатых блоков данные кодируются в виде последовательности кодов Хаффмана, за которыми следуют дополнительные биты (для длин и расстояний), и заканчиваются кодом конца блока (256).

Применение

Форматы архивов

• ZIP — основной алгоритм сжатия. Используется в большинстве ZIP-архивов, созданных PKZIP, WinZip, 7-Zip и другими программами.
• gzip — формат, использующий Deflate с обёрткой (заголовок, CRC-32, размер). Широко применяется в Unix-подобных системах для сжатия файлов и потоков данных.
• zlib — библиотека, реализующая Deflate с дополнительной обёрткой для обнаружения ошибок. Используется во многих протоколах, включая HTTP, SSH и TLS.

Графические форматы

• PNG — формат растровой графики использует Deflate для сжатия данных изображения (после фильтрации строк). Это обеспечивает сжатие без потерь, что критично для изображений с текстом, диаграммами или логотипами.
• TIFF — может использовать Deflate в качестве одного из методов сжатия (обычно обозначается как «Deflate» или «ZIP»).

Сетевые протоколы

• HTTP — сжатие содержимого (Content-Encoding: deflate) позволяет уменьшить объём передаваемых данных между сервером и клиентом. Однако на практике чаще используется gzip, который также основан на Deflate.
• WebSocket — расширение permessage-deflate позволяет сжимать сообщения в реальном времени.

Прочие применения

• PDF — может использовать Deflate для сжатия потоков данных внутри документа.
• Java — классы java.util.zip.Deflater и Inflater реализуют Deflate.
• .NET — классы System.IO.Compression.DeflateStream и GZipStream.

Реализации

Наиболее известной и широко используемой реализацией Deflate является библиотека zlib, написанная Жаном-Лу Гайи и Марком Адлером. Она предоставляет функции для сжатия и распаковки данных в форматах Deflate, gzip и zlib. zlib является эталонной реализацией и используется в большинстве операционных систем, веб-браузеров и серверного ПО.

Другие реализации включают:

• miniz — компактная реализация на C, часто используется во встраиваемых системах.
• libdeflate — высокопроизводительная реализация, оптимизированная для скорости.
• zlib-ng — форк zlib с улучшенной производительностью и поддержкой современных процессоров.

Сравнение с другими алгоритмами

Deflate занимает промежуточное положение: он быстрее LZMA и bzip2, но уступает им в степени сжатия. Однако его низкие требования к памяти и отсутствие патентных ограничений делают его идеальным для встраиваемых систем, сетевых протоколов и форматов, где важна совместимость.

Ограничения и недостатки

• Не поддерживает контекстное моделирование — Deflate не использует предсказание на основе контекста, что ограничивает степень сжатия для некоторых типов данных (например, текстов).
• Фиксированный размер окна — 32 КБ может быть недостаточно для эффективного сжатия больших повторяющихся структур (например, в базах данных).
• Отсутствие адаптации — алгоритм не подстраивается под статистику данных в процессе сжатия; все блоки обрабатываются независимо.
• Чувствительность к шуму — случайные данные или зашумлённые изображения могут сжиматься хуже, чем несжатые (иногда размер увеличивается).

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

• Алгоритм Deflate был назван в честь термина «дефляция» (сдувание), в противоположность «инфляции» (раздувание) — намёк на уменьшение размера данных.
• В спецификации RFC 1951 намеренно не определён конкретный алгоритм поиска совпадений в LZ77 — это позволяет реализациям использовать различные эвристики (например, хэш-таблицы, деревья или бинарный поиск) для оптимизации скорости и степени сжатия.
• Формат PNG был создан в 1995 году как замена GIF, который использовал запатентованный LZW. Deflate стал ключевым элементом, обеспечившим свободное распространение PNG.
• В 2013 году была обнаружена уязвимость CRIME, которая использовала сжатие Deflate в HTTPS для восстановления содержимого куки-файлов. Это привело к отключению сжатия в некоторых протоколах.

Источники

• RFC 1951 — DEFLATE Compressed Data Format Specification version 1.3
• RFC 1950 — ZLIB Compressed Data Format Specification version 3.3
• RFC 1952 — GZIP file format specification version 4.3
• Deutsch, P. (1996). «DEFLATE Compressed Data Format Specification». IETF.
• Gailly, J.-L., Adler, M. (1995). «zlib 1.0.0 Release Notes».
• Salomon, D. (2007). «Data Compression: The Complete Reference». Springer.