Deflate

Deflate — это алгоритм сжатия данных без потерь, основанный на комбинации алгоритма LZ77 (Lempel-Ziv 1977) и кодирования Хаффмана. Разработан Филом Кацем (Phil Katz) в 1990 году для архиватора PKZIP и впоследствии ставший одним из наиболее распространённых методов сжатия в вычислительной технике. Deflate используется в форматах файлов ZIP, gzip, PNG, HTTP (сжатие данных веб-серверами) и многих других.

История

Алгоритм Deflate был создан Филом Кацем, основателем компании PKWare, как ответ на ограничения существовавших на тот момент методов сжатия. В 1980-х годах доминирующим архиватором был ARC, использующий алгоритм сжатия, основанный на LZW (Lempel-Ziv-Welch). Кац стремился создать более эффективный и быстрый алгоритм, который не нарушал бы патентов на LZW, принадлежавших корпорации Unisys.

В 1989 году Кац выпустил архиватор PKZIP 0.9, в котором впервые применил Deflate. Алгоритм был описан в спецификации формата ZIP (APPNOTE.TXT), что позволило другим разработчикам реализовывать его независимо. Благодаря открытости спецификации и высокой степени сжатия, Deflate быстро вытеснил ARC и стал стандартом де-факто для сжатия данных на платформе IBM PC.

В 1996 году алгоритм был стандартизирован как RFC 1951 (DEFLATE Compressed Data Format Specification). Позднее был разработан улучшенный вариант — Deflate64 (Enhanced Deflate), используемый в некоторых реализациях ZIP, однако он не получил столь широкого распространения, как оригинальный Deflate.

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

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

Этап LZ77

На этом этапе алгоритм скользящим окном просматривает входные данные. Для каждой позиции он ищет самую длинную последовательность байтов, которая уже встречалась ранее в пределах окна (обычно размером от 32 КБ до 64 КБ). Если такая последовательность найдена, она заменяется парой (длина, расстояние), где длина — количество совпадающих байтов (от 3 до 258), а расстояние — отступ назад от текущей позиции (от 1 до 32768). Если совпадение не найдено, байт кодируется как литерал (исходное значение).

Этап кодирования Хаффмана

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

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

Коды Хаффмана строятся динамически для каждого блока данных на основе частоты встречаемости элементов. Deflate поддерживает три режима кодирования:

• Несжатый (stored) — данные передаются без сжатия, используется для несжимаемых данных.
• Фиксированный Хаффман (fixed) — используются предопределённые коды Хаффмана, что ускоряет сжатие за счёт меньшей степени сжатия.
• Динамический Хаффман (dynamic) — коды Хаффмана вычисляются на основе статистики блока, что даёт лучшую степень сжатия, но требует передачи описания деревьев.

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

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

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

Для динамического Хаффмана после заголовка следует описание деревьев кодирования, которое включает коды длин для литералов/длин и расстояний, сжатые с помощью кодирования длин серий (run-length encoding). Затем идут сами сжатые данные, закодированные кодами Хаффмана.

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

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

• Степень сжатия: в среднем от 2:1 до 5:1 для текстовых данных, для бинарных файлов может быть ниже. Максимальная степень сжатия достигается на данных с высокой избыточностью.
• Скорость: алгоритм имеет умеренную скорость сжатия и высокую скорость распаковки. Реализации могут варьироваться: например, библиотека zlib (наиболее распространённая реализация Deflate) поддерживает уровни сжатия от 0 (без сжатия) до 9 (максимальное сжатие).
• Память: для сжатия требуется память под скользящее окно (обычно 32 КБ) и буферы; для распаковки — только окно.
• Патентная чистота: алгоритм не защищён патентами, что способствовало его широкому распространению.

Применение

Deflate используется в огромном количестве программных продуктов и форматов:

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

• ZIP — основной алгоритм сжатия (PKZIP, WinZip, 7-Zip и др.).
• gzip — утилита сжатия в Unix-подобных системах, использует Deflate с обёрткой gzip.
• PNG — формат растровых изображений, использует Deflate для сжатия данных изображения (после фильтрации строк).
• HTTP — протокол передачи гипертекста поддерживает сжатие тела ответа с помощью Deflate (Content-Encoding: deflate).
• PDF — документы PDF могут содержать сжатые потоки Deflate.
• TIFF — некоторые реализации используют Deflate для сжатия.
• WebSocket — расширение для сжатия сообщений.

Библиотеки

• zlib — эталонная реализация Deflate, написанная на C Жаном-Лу Гайи (Jean-loup Gailly) и Марком Адлером (Mark Adler). Используется в большинстве операционных систем и приложений.
• miniz — компактная реализация на C.
• libdeflate — оптимизированная реализация с высокой производительностью.

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

Deflate уступает по степени сжатия более современным алгоритмам, таким как LZMA (используется в 7-Zip) или BZIP2, но превосходит их по скорости распаковки и простоте реализации. Для текстовых данных Deflate часто обеспечивает достаточную степень сжатия при низких вычислительных затратах. Алгоритмы семейства LZ4 и Snappy, ориентированные на максимальную скорость, сжимают хуже Deflate, но работают быстрее.

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

• Алгоритм Deflate был назван в честь термина «дефляция» (сжатие), в отличие от «инфляции» (расширение).
• Фил Кац, создатель Deflate, умер в 2000 году, а его компания PKWare была продана.
• Спецификация RFC 1951 является одной из наиболее цитируемых в области сжатия данных.
• В 2010-х годах были разработаны аппаратные ускорители Deflate (например, в процессорах Intel QuickAssist), позволяющие обрабатывать сжатие на скорости до десятков гигабит в секунду.

Источники

• RFC 1951 — DEFLATE Compressed Data Format Specification (1996)
• Deutsch, P., Gailly, J.-L. — ZLIB Compressed Data Format Specification (RFC 1950, 1996)
• Gailly, J.-L., Adler, M. — zlib library documentation
• PKWare — APPNOTE.TXT — .ZIP File Format Specification (версии 6.3.x и выше)
• Salomon, D. — Data Compression: The Complete Reference (4th edition, 2007)
• Sayood, K. — Introduction to Data Compression (5th edition, 2017)