Deflate — это RFC 1951.

Deflate считается свободным от всех существующих патентов, и пока патент на LZW (который используется в формате GIF) оставался в силе, это привело к использованию deflate в файлах, сжимаемых gzip, и изображениях в формате PNG вдобавок к формату ZIP, для которого Кац изначально его спроектировал.

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

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

• 1 бит: флаг последнего блока.

• 1: блок последний.
• 0: не последний блок.

• 2 бита: метод, с помощью которого были закодированы данные.

• 00: данные не были закодированы. (В блоке находятся непосредственно выходные данные.)
• 01: данные, закодированные с помощью метода статического Хаффмана.
• 10: данные, закодированные с помощью метода динамического Хаффмана.
• 11: зарезервированное значение. (ошибка)

Большая часть блоков кодируется с помощью метода 10 (динамический Хаффман), который предоставляет оптимизированное дерево кодов Хаффмана для каждого нового блока. Инструкции для создания дерева кодов Хаффмана следуют непосредственно за заголовком блока.

Компрессия происходит в два шага:

• Замена повторяющихся строк указателями (LZ77).
• Замена символов новыми символами, основываясь на частоте их использования (алгоритм Хаффмана).

Ссылки

• RFC 1951 — DEFLATE Compressed Data Format Specification version 1.3
• Deflate decoding - Описание формата сжатия данных Deflate Е.В. Михальчик