Deflate

Deflate — это алгоритм сжатия без потерь, который использует комбинацию алгоритма LZ77 и алгоритма Хаффмана. Изначально он был описан Филом Кацом для 2-й версии своей утилиты для создания архивов PKZIP, который впоследствии был определён в RFC 1951.

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

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

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

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

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

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

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

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

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

• Замена повторяющихся строк указателями.
• Перемещение символов в словаре, основываясь на частоте их использования.

Ссылки

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