Сжатие Deflate

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

История

Алгоритм Deflate был создан Филом Кацем в 1993 году для программы PKZIP, которая стала стандартом де-факто для сжатия данных на платформе MS-DOS и ранних версиях Windows. Кац разработал Deflate как улучшенную замену более ранним алгоритмам сжатия, таким как LZW (используемый в GIF) и LZSS (используемый в ARJ). Основной целью было достижение высокой степени сжатия при относительно низких требованиях к памяти и вычислительным ресурсам.

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

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

Алгоритм Deflate работает в два этапа, которые могут быть реализованы как последовательно, так и в комбинированном виде.

Этап 1: LZ77 (сжатие с использованием скользящего окна)

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

• Расстояние (distance) — сколько байт назад от текущей позиции находится начало найденной строки.
• Длина (length) — количество байт, которые повторяются.

Если повторение не найдено, байт кодируется как литерал (непосредственное значение). Максимальная длина повторения в Deflate ограничена 258 байтами, а максимальное расстояние — 32 768 байтами (32 КБ).

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

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

1. Дерево для литералов и длин — кодирует все литералы (0–255), а также коды длин (257–285) и специальный код конца блока (256).
2. Дерево для расстояний — кодирует значения расстояний (0–29).

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

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

Deflate оперирует блоками данных. Каждый блок может быть сжат одним из трёх способов:

• Несжатый блок (тип 0) — данные передаются без сжатия, используется для несжимаемых данных.
• Сжатый блок с фиксированными кодами Хаффмана (тип 1) — используется предопределённое дерево Хаффмана, которое не требует передачи в потоке.
• Сжатый блок с динамическими кодами Хаффмана (тип 2) — дерево Хаффмана строится на основе данных блока и передаётся вместе с ним.

Блоки могут быть объединены в один поток данных. Каждый блок завершается специальным маркером конца блока.

Применение

Deflate является одним из самых широко используемых алгоритмов сжатия в мире. Основные области применения:

• Архиваторы: ZIP, gzip, 7z (в режиме Deflate).
• Форматы изображений: PNG (Portable Network Graphics) использует Deflate для сжатия данных изображения.
• Сетевые протоколы: HTTP (сжатие содержимого с помощью gzip или deflate), WebSocket (расширение permessage-deflate).
• Форматы документов: PDF (частично), OpenDocument, Office Open XML (внутри ZIP-архивов).
• Программное обеспечение: многие утилиты сжатия, такие как zlib (библиотека, реализующая Deflate), используются в операционных системах, играх и приложениях.

Производительность

Степень сжатия Deflate зависит от размера скользящего окна и стратегии поиска повторений. В типичных условиях (окно 32 КБ) Deflate сжимает текстовые данные в 2–4 раза, а бинарные данные (например, исполняемые файлы) — в 1,5–2 раза. Скорость сжатия и распаковки варьируется в зависимости от реализации: программные реализации могут достигать скорости десятков мегабайт в секунду на современных процессорах, а аппаратные ускорители — сотен мегабайт в секунду.

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

• LZW (используемый в GIF): Deflate обычно обеспечивает более высокую степень сжатия, особенно на текстовых данных, и не имеет патентных ограничений.
• Bzip2 (алгоритм Барроуза — Уиллера): Bzip2 сжимает лучше, чем Deflate, но значительно медленнее при сжатии и распаковке.
• LZMA (используемый в 7z): LZMA обеспечивает более высокую степень сжатия, чем Deflate, но требует больше памяти и вычислительных ресурсов.
• LZ4 (алгоритм быстрого сжатия): LZ4 ориентирован на скорость, а не на степень сжатия, и значительно быстрее Deflate, но сжимает хуже.

Критика и ограничения

Основным недостатком Deflate является относительно низкая степень сжатия по сравнению с более современными алгоритмами, такими как LZMA или Brotli. Кроме того, алгоритм не поддерживает сжатие с использованием контекстного моделирования или предсказания, что ограничивает его эффективность на некоторых типах данных (например, на высокоэнтропийных данных). Также Deflate не поддерживает многопоточность на уровне алгоритма, хотя современные реализации могут обрабатывать несколько блоков параллельно.

Реализации

Существует множество реализаций Deflate, как программных, так и аппаратных. Наиболее известные:

• zlib — библиотека, написанная Жаном-Лу Гайи и Марком Адлером, является эталонной реализацией Deflate.
• libdeflate — библиотека с высокой производительностью, оптимизированная для современных процессоров.
• Intel IPP — библиотека Intel Integrated Performance Primitives, содержащая аппаратно-ускоренную реализацию Deflate.
• zlib-ng — форк zlib с улучшенной производительностью.

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

• Алгоритм Deflate был разработан Филом Кацем в возрасте 30 лет, и его реализация в PKZIP стала коммерчески успешной, принеся Кацу миллионы долларов.
• Формат PNG был создан в 1995 году как свободная альтернатива GIF, и Deflate был выбран для сжатия данных из-за отсутствия патентных ограничений.
• В 2013 году была опубликована спецификация Deflate64, которая увеличивает размер скользящего окна до 64 КБ, но этот формат не получил широкого распространения.
• Алгоритм Deflate используется в сжатии HTTP-трафика, что позволяет значительно ускорить загрузку веб-страниц.

Источники

• RFC 1951 — DEFLATE Compressed Data Format Specification version 1.3
• Deutsch, P. (1996). DEFLATE Compressed Data Format Specification. IETF.
• Кац, Ф. (1993). PKZIP 2.0 Technical Documentation.
• Гайи, Ж.-Л., Адлер, М. (1995). zlib: A Massively Spiffy Yet Delicately Unobtrusive Compression Library.
• Salomon, D. (2007). Data Compression: The Complete Reference. Springer.