RFC 1951

RFC 1951 — это спецификация, определяющая алгоритм сжатия данных Deflate, опубликованная в мае 1996 года Инженерным советом Интернета (IETF) в виде запроса комментариев (Request for Comments). Она описывает формат сжатого потока данных, который использует комбинацию алгоритма LZ77 (Lempel-Ziv 1977) и кодирования Хаффмана. RFC 1951 является основой для многих широко распространённых форматов сжатия, включая gzip, PNG и ZIP.

История и контекст создания

Спецификация RFC 1951 была разработана в середине 1990-х годов как ответ на потребность в универсальном, свободном от патентных ограничений алгоритме сжатия данных. До этого широко использовались алгоритмы, такие как LZW (Lempel-Ziv-Welch), который был запатентован корпорацией Unisys, что создавало юридические риски для разработчиков свободного программного обеспечения.

Автором RFC 1951 является Питер Дойч (Peter Deutsch), который в то время работал в компании Aladdin Enterprises. Он также участвовал в разработке формата gzip (RFC 1952) и формата архивов ZIP. Основной целью было создание алгоритма, который обеспечивал бы высокую степень сжатия при относительно низких требованиях к вычислительным ресурсам, а также был бы полностью свободным для реализации.

Основные принципы работы: LZ77

Алгоритм Deflate, описанный в RFC 1951, состоит из двух последовательных этапов. Первый этап основан на алгоритме LZ77, который выполняет поиск повторяющихся последовательностей байтов в уже обработанных данных.

Механизм словаря и скользящего окна

LZ77 использует скользящее окно фиксированного размера (до 32 768 байт, или 32 КБ). В этом окне хранятся последние обработанные данные. Алгоритм анализирует текущий фрагмент данных и пытается найти его копию в пределах этого окна. Если такая копия найдена, она заменяется ссылкой на неё, которая состоит из двух чисел:

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

Если повторяющаяся последовательность не найдена, байт кодируется как литерал (literal), то есть передаётся в неизменном виде. Максимальная длина совпадения, которую может закодировать LZ77 в Deflate, составляет 258 байт.

Основные принципы работы: кодирование Хаффмана

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

Деревья Хаффмана

RFC 1951 определяет два типа кодов Хаффмана:

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

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

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

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

Применение и распространение

RFC 1951 является одним из самых распространённых алгоритмов сжатия данных в мире. Его использование охватывает множество областей:

Формат gzip (RFC 1952): наиболее распространённый способ сжатия файлов в Unix-подобных операционных системах. Используется для сжатия веб-страниц, программного обеспечения и архивов.
Формат PNG (Portable Network Graphics): графический формат, использующий Deflate для сжатия растровых изображений без потерь.
Формат ZIP: популярный формат архивов, который использует Deflate как основной метод сжатия.
Протокол HTTP: многие веб-серверы и браузеры поддерживают сжатие передаваемых данных с помощью gzip, что значительно ускоряет загрузку страниц.
Протокол WebSocket: используется для сжатия сообщений в реальном времени.
Файловые системы: некоторые файловые системы, такие как ZFS, используют Deflate для сжатия данных на диске.

Преимущества и недостатки

Преимущества

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

Недостатки

Ограниченный размер окна LZ77: окно в 32 КБ может быть недостаточным для эффективного сжатия очень больших файлов с длинными повторяющимися структурами.
Неоптимальная степень сжатия: более современные алгоритмы, такие как LZMA (используемый в 7z) или Brotli, могут достигать значительно более высокой степени сжатия за счёт более сложных методов и большего размера словаря.
Чувствительность к шуму: в данных с высоким уровнем шума (например, в зашумлённых изображениях) эффективность сжатия резко падает.

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

Несмотря на широкое распространение, RFC 1951 подвергался критике за недостаточную эффективность сжатия по сравнению с более современными алгоритмами. В ответ на это были разработаны альтернативы, такие как:

Brotli: алгоритм сжатия, разработанный Google, который использует более крупный словарь (до 4 МБ) и более сложные методы кодирования. Он широко используется в веб-сжатии.
Zstandard (zstd): алгоритм сжатия, разработанный Facebook (компания Meta признана экстремистской и запрещена в РФ), который предлагает высокую скорость и степень сжатия, настраиваемую под конкретные задачи.
LZMA: алгоритм, используемый в архиваторе 7-Zip, обеспечивающий очень высокую степень сжатия за счёт большого размера словаря и сложного кодирования.

Тем не менее, RFC 1951 остаётся стандартом де-факто для многих приложений благодаря своей простоте, скорости и отсутствию патентных ограничений.

Источники

RFC 1951 — DEFLATE Compressed Data Format Specification version 1.3 (P. Deutsch, 1996).
RFC 1952 — GZIP file format specification version 4.3 (P. Deutsch, 1996).
RFC 2083 — PNG (Portable Network Graphics) Specification (T. Boutell, 1997).
Сэлмон, Д. «Сжатие данных: методы и практика». — М.: Вильямс, 2004.
Официальная документация по формату ZIP (PKWARE Inc.).

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →