Сжатие данных Deflate

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

История

Предпосылки создания

До появления Deflate доминирующими алгоритмами сжатия были LZW (использовался в GIF и Unix-утилите compress) и арифметическое кодирование. LZW был запатентован компанией Unisys, что создавало юридические ограничения для свободного использования. Кроме того, существовали проблемы с производительностью и степенью сжатия для определённых типов данных.

Разработка Филом Кацем

Фил Кац, американский программист, в 1989 году разработал алгоритм Deflate для своей программы PKZIP. Кац стремился создать алгоритм, который:

• Не нарушал существующих патентов (в частности, на LZW).
• Обеспечивал высокую степень сжатия для текстовых и бинарных файлов.
• Был достаточно быстрым для работы на персональных компьютерах того времени.

Алгоритм был опубликован в 1993 году в спецификации формата ZIP (PKWARE) и вскоре стал открытым стандартом (RFC 1951, 1996 год). Открытость спецификации позволила Deflate стать основой для многих свободных и коммерческих программ.

Стандартизация

В 1996 году спецификация Deflate была опубликована как RFC 1951 Инженерным советом Интернета (IETF). Этот документ формально описал алгоритм, что позволило создавать совместимые реализации для любых платформ. С тех пор Deflate является одним из наиболее распространённых алгоритмов сжатия в мире.

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

Deflate состоит из двух последовательных этапов:

Этап 1: LZ77 (словарное сжатие)

На этом этапе алгоритм ищет повторяющиеся последовательности байтов (строки) во входном потоке. Он использует скользящее окно (обычно размером до 32 КБ) и буфер предварительного просмотра (look-ahead buffer, до 258 байт).

• Принцип: Если текущая последовательность байтов уже встречалась в окне, она заменяется парой чисел (distance, length): расстояние от текущей позиции до места первого вхождения (distance) и длина совпадающей строки (length).
• Пример: Для строки «abcabcabc» алгоритм может закодировать второе и третье вхождения «abc» ссылками на первое. Если в окне совпадение не найдено, байт кодируется как литерал (сам байт).

Этап 2: Кодирование Хаффмана (энтропийное сжатие)

После этапа LZ77 поток данных состоит из двух типов символов: литералов (исходные байты) и пар (distance, length). Deflate использует два отдельных дерева Хаффмана:

1. Дерево для литералов и длин (length): Кодирует все 256 возможных байтов (литералы) и значения длины (от 3 до 258). Для длин используется дополнительная кодировка, где некоторые значения кодируются фиксированными кодами, а для других добавляются дополнительные биты (extrabits).
2. Дерево для расстояний (distance): Кодирует значения расстояний (от 1 до 32768). Аналогично, для некоторых расстояний используются дополнительные биты.

Алгоритм Хаффмана строит оптимальные префиксные коды на основе частоты встречаемости каждого символа в потоке. Часто встречающиеся символы получают короткие коды (например, 2-3 бита), а редкие — длинные (до 15 бит). Deflate поддерживает два режима кодирования Хаффмана:

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

Формат сжатого потока

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

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

Блоки могут быть любого размера (до 65535 байт в несжатом виде). После заголовка следуют сжатые данные, а затем — контрольная сумма (CRC-32) и длина исходных данных (для несжатых блоков).

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

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

Deflate обеспечивает степень сжатия от 2:1 до 5:1 для типичных текстовых файлов и от 1.5:1 до 3:1 для бинарных файлов. Для уже сжатых данных (например, JPEG, MP3) степень сжатия близка к 1:1 или даже увеличивает размер из-за служебной информации.

Скорость

Скорость сжатия и распаковки сильно зависит от реализации. Алгоритм является достаточно быстрым для распаковки (обычно несколько сотен мегабайт в секунду на современном процессоре). Сжатие может быть медленнее, особенно на максимальном уровне (level 9), из-за более тщательного поиска совпадений в LZ77.

Память

Для распаковки требуется буфер размером до 32 КБ (скользящее окно) и память для хранения деревьев Хаффмана (несколько сотен байт). Для сжатия требуется дополнительная память для построения словаря (обычно до 64 КБ).

Применение

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

Форматы файлов

• ZIP: Основной метод сжатия (метод 8). Используется в архиваторах (WinZip, 7-Zip, Info-ZIP).
• gzip: Формат сжатия отдельных файлов (RFC 1952). Широко используется в Unix-подобных системах для сжатия логов, пакетов программ (tar.gz).
• PNG: Формат растровой графики. Deflate используется для сжатия пиксельных данных (после фильтрации).
• PDF: Документы PDF могут содержать сжатые потоки Deflate (фильтр /FlateDecode).
• Zlib: Библиотека сжатия, реализующая Deflate. Используется в многих программах и протоколах.

Протоколы

• HTTP: Протокол передачи гипертекста поддерживает сжатие содержимого (Content-Encoding: deflate). Сервер может сжимать HTML, CSS, JavaScript перед отправкой клиенту.
• TLS/SSL: Протокол защиты транспортного уровня может использовать Deflate для сжатия данных (хотя в современных версиях это отключено из-за уязвимости CRIME).
• SSH: Протокол Secure Shell поддерживает сжатие Deflate (алгоритм zlib).

Программное обеспечение

• Библиотеки: zlib (наиболее известная реализация, автор — Жан-Луп Гайи), miniz, libdeflate.
• Утилиты: gzip, gunzip, zcat, zip, unzip.
• Операционные системы: Ядро Linux использует Deflate для сжатия initramfs и некоторых других данных.

Критика и альтернативы

Несмотря на широкое распространение, Deflate имеет ограничения:

• Степень сжатия: Уступает более современным алгоритмам, таким как LZMA (7-Zip), bzip2 (BWT) и Brotli (Google). Для текстовых данных Brotli может обеспечить на 20-30% лучшее сжатие.
• Скорость сжатия: На высоких уровнях (9) может быть медленнее, чем некоторые современные алгоритмы (например, LZ4, Zstandard).
• Размер окна: Фиксированный размер скользящего окна (32 КБ) ограничивает эффективность на больших объёмах данных.

Современные альтернативы включают:

• Zstandard (zstd): Алгоритм от Facebook (Meta — организация признана экстремистской и запрещена в РФ), обеспечивающий более высокую степень сжатия и скорость при настройке параметров.
• Brotli: Алгоритм от Google, оптимизированный для сжатия веб-контента (HTML, CSS). Использует более сложные методы (контекстное моделирование) и больший словарь.
• LZ4: Алгоритм, ориентированный на максимальную скорость распаковки, но с меньшей степенью сжатия.

Источники

1. RFC 1951 — DEFLATE Compressed Data Format Specification version 1.3
2. RFC 1952 — GZIP file format specification version 4.3
3. RFC 1950 — ZLIB Compressed Data Format Specification version 3.3
4. P. Deutsch, J.-L. Gailly. «Zlib Compressed Data Format Specification» (1996)
5. D. Salomon. «Data Compression: The Complete Reference» (4th edition, 2007)
6. M. Nelson, J.-L. Gailly. «The Data Compression Book» (2nd edition, 1995)