Deflate

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

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

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

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

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

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

Компрессия выполняется в два этапа:

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

Ссылки

  • RFC 1951 — DEFLATE Compressed Data Format Specification version 1.3 (англ.)
  • Deflate decoding — Описание формата сжатия данных Deflate, Е. В. Михальчик
ПО
Это заготовка статьи о программном обеспечении. Помогите Википедии, дополнив её.
В другом языковом разделе есть более полная статья DEFLATE (англ.).
Вы можете помочь проекту, расширив текущую статью с помощью перевода

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.