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, Е. В. Михальчик
 Методысжатия | |||||||
|---|---|---|---|---|---|---|---|
| Теория |
| ||||||
| Без потерь |
| ||||||
| Аудио |
| ||||||
| Изображения |
| ||||||
| Видео |
| ||||||