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 (динамический Хаффман), который предоставляет оптимизированное дерево кодов Хаффмана для каждого нового блока. Инструкции для создания дерева кодов Хаффмана следуют непосредственно за заголовком блока.

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

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

Ссылки[править | править исходный текст]

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