Сдуть

Эта статья об алгоритме сжатия данных. Чтобы узнать о других значениях, см. Дефляция (значения) .

В вычислительной технике Deflate ( стилизованный под DEFLATE , также называемый Flate ) — это без потерь со сжатием данных формат файлов , в котором используется комбинация кодирования LZ77 и Хаффмана . Он был разработан Филом Кацем для второй версии его инструмента архивирования PKZIP . Позднее Deflate был указан в RFC 1951 (1996).

Кац также разработал оригинальный алгоритм, используемый для создания потоков Deflate. Этот алгоритм был запатентован как патент США № 5 051 745 и передан компании PKWARE, Inc. Как указано в документе RFC, многие считали, что алгоритм создания файлов Deflate можно реализовать способом, не защищенным патентами. Это привело к его широкому использованию — например, в gzip файлах, сжатых , и файлах изображений PNG , в дополнение к формату файлов ZIP , для которого Кац изначально разработал его. Срок действия патента истек.

Формат потока

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

• Первый бит: Маркер последнего блока в потоке:
  • 1: Это последний блок в потоке.
  • 0: После этого нужно обработать еще несколько блоков.
• Второй и третий биты: метод кодирования, используемый для этого типа блока:
  • 00: Сохраненный (он же необработанный или буквальный) раздел длиной от 0 до 65 535 байт.
  • 01: статический сжатый блок Хаффмана , использующий предварительно согласованное дерево Хаффмана, определенное в RFC.
  • 10: Динамический сжатый блок Хаффмана в комплекте с поставляемой таблицей Хаффмана.
  • 11: Зарезервировано — не использовать.

Опция хранимого блока добавляет минимальные накладные расходы и используется для несжимаемых данных.

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

Сжатие достигается в два этапа:

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

Удаление повторяющихся строк

Основные статьи: LZ77, LZ78 и LZSS.

Если внутри сжатых блоков обнаруживается повторяющаяся серия байтов (повторяющаяся строка), то обратная ссылка вставляется , ссылающаяся вместо этого на предыдущее местоположение этой идентичной строки. Закодированное совпадение с более ранней строкой состоит из 8-битной длины (3–258 байт) и 15-битного расстояния (1–32 768 байт) до начала дубликата. Относительные обратные ссылки могут быть сделаны для любого количества блоков, при условии, что расстояние находится в пределах последних 32 КиБ декодированных несжатых данных (так называемое скользящее окно ).

Если расстояние меньше длины, дубликат перекрывается, указывая на повторение. Например, серия из 10 одинаковых байтов может быть закодирована как один байт, за которым следует дубликат длиной 9, начиная с предыдущего байта.

Поиск повторяющихся подстрок в предыдущем тексте — самая затратная в вычислительном отношении часть алгоритма DEFLATE и операция, на которую влияют настройки уровня сжатия.

Битовое уменьшение

Основная статья: Кодирование Хаффмана

Второй этап сжатия состоит из замены часто используемых символов более короткими представлениями и менее часто используемых символов более длинными представлениями. Используемый метод — это кодирование Хаффмана , которое создает дерево непересекающихся интервалов без префиксов, где длина каждой последовательности обратно пропорциональна логарифму вероятности того, что этот символ необходимо закодировать. Чем более вероятно, что символ необходимо закодировать, тем короче будет его битовая последовательность.

Создается дерево, содержащее место для 288 символов:

• 0–255: представляют буквальные байты/символы 0–255.
• 256: конец блока – остановить обработку, если блок последний, иначе начать обработку следующего блока.
• 257–285: в сочетании с дополнительными битами длина совпадения составляет 3–258 байт.
• 286, 287: не используются, зарезервированы и незаконны, но все же являются частью дерева.

За кодом длины совпадения всегда следует код расстояния. На основе считанного кода расстояния могут быть считаны дополнительные «дополнительные» биты, чтобы получить окончательное расстояние. Дерево расстояний содержит место для 32 символов:

• 0–3: расстояния 1–4
• 4–5: расстояния 5–8, 1 дополнительный бит
• 6–7: расстояния 9–16, 2 дополнительных бита.
• 8–9: расстояния 17–32, 3 дополнительных бита.
• ...
• 26–27: расстояния 8 193–16 384, 12 дополнительных битов.
• 28–29: расстояния 16 385–32 768, 13 дополнительных битов.
• 30–31: не используются, зарезервированы и незаконны, но все же являются частью дерева.

Обратите внимание, что для символов расстояния совпадения 2–29 количество дополнительных битов можно рассчитать как $\left\lfloor {\frac {n}{2}}\right\rfloor -1$.

Два кода (дерево длины/литерала длиной 288 символов и дерево расстояний из 32 символов) сами по себе кодируются как канонические коды Хаффмана, указывая длину кода в битах для каждого символа. Длины битов сами по себе кодируются по длинам серий, чтобы обеспечить максимально компактное представление. В качестве альтернативы представлению дерева опция «статическое дерево» предоставляет стандартные фиксированные деревья Хаффмана. Размер сжатого изображения с использованием статических деревьев можно вычислить с использованием той же статистики (количество повторов появления каждого символа), которая используется для создания динамических деревьев, поэтому компрессору легко выбрать тот, который меньше.

Кодер/компрессор

На этапе сжатия именно кодер выбирает количество времени, затрачиваемое на поиск совпадающих строк. zlib/gzip Эталонная реализация позволяет пользователю выбирать по скользящей шкале вероятный уровень сжатия в зависимости от скорости кодирования. Варианты варьируются от 0 (не пытайтесь сжать, просто сохраните в несжатом виде), чтобы 9 представляющий максимальные возможности эталонной реализации в zlib/gzip.

Были созданы и другие кодеры Deflate, все из которых также создают совместимый битовый поток , который можно распаковать любым существующим декодером Deflate. Различные реализации, скорее всего, приведут к вариациям конечного закодированного потока битов. В версиях кодировщика, отличных от Zlib, обычно основное внимание уделяется созданию более эффективно сжатого и меньшего по размеру закодированного потока.

Deflate64/Enhanced Deflate

Deflate64, указанный PKWARE, является собственным вариантом Deflate. По сути, это тот же алгоритм. Что изменилось, так это увеличение размера словаря с 32 КБ до 64 КБ, расширение кодов расстояния до 16 бит, чтобы они могли адресовать диапазон в 64 КБ, и код длины, который расширен до 16 бит, чтобы он может определять длину от трех до 65 538 байт. Это приводит к тому, что Deflate64 имеет более длительное время сжатия и, возможно, немного более высокую степень сжатия, чем Deflate. Некоторые бесплатные проекты и/или проекты с открытым исходным кодом поддерживают Deflate64, например 7-Zip . в то время как другие, такие как zlib , этого не делают из-за запатентованного характера процедуры. и очень скромное увеличение производительности по сравнению с Deflate.

Использование Deflate в новом программном обеспечении

Реализации Deflate свободно доступны на многих языках. Приложения, написанные на C, обычно используют библиотеку zlib (под разрешительной лицензией zlib ). Приложения на Borland Pascal (и совместимых языках) могут использовать paszlib. Приложения на C++ могут использовать улучшенную библиотеку Deflate в 7-Zip . И Java , и .NET Framework предлагают готовую поддержку Deflate в своих библиотеках (соответственно, java.util.zip и System.IO.Compression ). Приложения на Ada могут использовать Zip-Ada (чистую) или ZLib-Ada .

Реализации кодировщика

• PKZIP : первая реализация, первоначально сделанная Филом Кацем как часть PKZip.
• zlib : стандартная эталонная реализация, принятая во многих приложениях из-за разрешительной лицензии с открытым исходным кодом. См. Zlib § Forks для более высокопроизводительных вилок.
• Crypto++ : содержит общедоступную реализацию на C++, направленную на снижение потенциальных уязвимостей безопасности . Автор, Вэй Дай, утверждает: « Этот код менее умен, но, надеюсь, более понятен и удобен в сопровождении [чем zlib] ».
• 7-Zip : написанная Игорем Павловым на C++ , эта версия лицензируется свободно и обеспечивает более высокое сжатие, чем zlib, за счет использования процессора. Имеет возможность использовать формат хранения DEFLATE64.
• PuTTY 'sshzlib.c': автономная реализация под лицензией MIT от Саймона Тэтэма, она имеет полную возможность декодирования, но поддерживает только создание статического дерева.
• либфлат: часть Plan 9 от Bell Labs , реализует сжатие deflate.
• Hyperbac : использует собственную библиотеку сжатия (на C++ и ассемблере) с возможностью реализации формата хранения DEFLATE64.
• Zopfli : реализация C под лицензией Apache от Google ; обеспечивает более высокое сжатие за счет использования процессора. ZopfliPNG — это вариант Zopfli для использования с файлами PNG .
• igzip: кодировщик, написанный на языке ассемблера x86 , выпущенный Intel по лицензии MIT . В 3 раза быстрее, чем zlib -1. Полезно для сжатия геномных данных.
• libdeflate: библиотека для быстрого сжатия и распаковки всего буфера на основе DEFLATE. Libdeflate сильно оптимизирован, особенно на процессорах x86.

AdvanceCOMP использует версии Deflate с более высокой степенью сжатия в 7-Zip, libdeflate и Zopfli, чтобы обеспечить повторное сжатие файлов gzip , PNG , MNG и ZIP с возможностью получения файлов меньшего размера, чем zlib при максимальных настройках.

Аппаратные кодеры

• AHA361-PCIX/AHA362-PCIX от Comtech AHA. Архивировано 8 декабря 2006 г. в Wayback Machine . Comtech выпустила карту PCI-X (PCI-ID: 193f:0001), способный сжимать потоки с помощью Deflate со скоростью до 3,0 Гбит/с (375 МБ/с) для входящих несжатых данных. В комплект поставки ядра Linux драйвера для AHA361-PCIX входит " ahagzip«Полезность и индивидуальность» mod_deflate_aha» способны использовать аппаратное сжатие от Apache . Аппаратное обеспечение основано на Xilinx Virtex FPGA и четырех специализированных ASIC AHA3601 . Платы AHA361/AHA362 ограничены только обработкой статических блоков Хаффмана и требуют модификации программного обеспечения для добавления поддержки — карты не могли поддерживать полную спецификацию Deflate, то есть могли надежно декодировать только свой собственный вывод (поток, который не содержал никаких динамических блоков Хаффмана типа 2).
• StorCompress 300 / MX3 от Indra Networks . Это диапазон PCI (PCI-ID: 17b4:0011) или карты PCI-X, оснащенные от одного до шести механизмами сжатия с заявленной скоростью обработки до 3,6 Гбит/с (450 МБ/с). Доступны версии карт под отдельным брендом WebEnhance, специально разработанные для использования в веб-сервисах, а не для SAN или резервного копирования; версия PCIe , MX4E . также производится
• AHA363-PCIe / AHA364-PCIe / AHA367-PCIe . В 2008 году Comtech начала производство двух карт PCIe ( PCI-ID: 193f:0363/ 193f:0364) с новым аппаратным чипом кодера AHA3610. Новый чип был разработан с расчетом на устойчивую скорость передачи данных 2,5 Гбит/с. Используя два таких чипа, плата AHA363-PCIe может обрабатывать Deflate со скоростью до 5,0 Гбит/с (625 МБ/с), используя два канала (два сжатия и два декомпрессии). Вариант AHA364-PCIe — это версия карты, предназначенная только для кодирования, предназначенная для балансировщиков исходящей нагрузки , и вместо этого имеет несколько наборов регистров, позволяющих использовать 32 независимых виртуальных канала сжатия, питающих два физических механизма сжатия. Драйверы устройств ядра Linux, Microsoft Windows и OpenSolaris доступны для обеих новых карт, а также модифицированная системная библиотека zlib, так что динамически подключаемые приложения могут автоматически использовать аппаратную поддержку без внутренних модификаций. Плата AHA367-PCIe ( PCI-ID: 193f:0367) аналогичен AHA363-PCIe, но использует четыре чипа AHA3610 для постоянной скорости сжатия 10 Гбит/с (1250 МБ/с). В отличие от AHA362-PCIX, механизмы декомпрессии на платах AHA363-PCIe и AHA367-PCIe полностью совместимы с дефляцией.
• Найтрокс и Октеон Процессоры от Cavium, Inc. содержат высокоскоростные аппаратные механизмы выкачивания и раздувания, совместимые как с ZLIB, так и с GZIP, при этом некоторые устройства способны обрабатывать несколько одновременных потоков данных.
• Реализация HDL-Deflate GPL FPGA.
• ZipAccel-C от CAST Inc. Это Silicon IP-ядро, поддерживающее сжатие Deflate, Zlib и Gzip . ZipAccel-C может быть реализован в ASIC или FPGA , поддерживает как динамические, так и статические таблицы Хаффмана и может обеспечивать пропускную способность более 100 Гбит/с. Компания предлагает эталонные конструкции плат ускорителя сжатия/распаковки для FPGA Intel ( ZipAccel-RD-INT ) и FPGA Xilinx ( ZipAccel-RD-XIL ).
• Набор коммуникационных микросхем Intel серии 89xx (Cave Creek) для процессоров Intel Xeon E5-2600 и E5-2400 (Sandy Bridge-EP/EN) поддерживает аппаратное сжатие и распаковку с использованием технологии QuickAssist. В зависимости от набора микросхем доступны скорости сжатия и распаковки 5 Гбит/с, 10 Гбит/с или 20 Гбит/с.
• Процессоры IBM z15 включают улучшенную версию аппаратного ускорения Nest Accelerator Unit (NXU) от карт расширения ввода-вывода zEDC Express, используемых в системах z14 для аппаратного сжатия и распаковки Deflate, как указано в RFC1951.
• Начиная с архитектуры POWER9 , IBM добавила аппаратную поддержку сжатия и распаковки Deflate (как указано в RFC 1951) в ранее криптоцентричное ядро ​​ускорителя Nest (NX), представленное в POWER7+ . Эта поддержка доступна для программ, работающих с пакетом расширения AIX 7.2 Technology Level 4 или пакетом обновления 2 для AIX 7.2 Technology Level 5, через библиотеку zlibNX.

Декодер/декомпрессор

Инфляция — это процесс декодирования, который использует битовый поток Deflate для распаковки и правильно создает исходные полноразмерные данные или файл.

Реализации только для инфляции

Обычной целью альтернативной реализации Inflate является высокооптимизированная скорость декодирования или чрезвычайно предсказуемое использование оперативной памяти для встроенных систем с микроконтроллерами.

• Сборка
  • 6502 inflate , написанный Петром Фусиком на языке ассемблера 6502 .
  • SAMflate , написанный Эндрю Кольером на Z80 ассемблере с дополнительной поддержкой подкачки памяти для SAM Coupé , и доступный по лицензиям BSD / GPL / LGPL / DFSG .
  • Gunzip , написанный Лоренсом Холстом на Z80 ассемблере для MSX , под лицензией BSD .
  • inflate.asm — быстрая и эффективная реализация на машинном языке M68000 , написанная Кейром Фрейзером и выпущенная в общественное достояние .

• С / С++
  • kunzip от Майкла Кона и не имеет отношения к «KZIP». Поставляется с C исходным кодом по лицензии GNU LGPL . Используется в установщике GIMP .
  • puff.c ( zlib ), небольшая, свободная, однофайловая эталонная реализация, включенная в каталог /contrib/puff дистрибутива zlib.
  • tinf написан Йоргеном Ибсеном на языке ANSI C и поставляется с лицензией zlib. Добавляет около 2к кода.
  • tinfl.c ( miniz ), общедоступная реализация Inflate, полностью содержащаяся в одной функции C.
• PCDEZIP, Боб Фландерс и Майкл Холмс, опубликовано в журнале PC Magazine 11 января 1994 г.
• inflate.cl Джона Фодераро. Автономный декодер Common Lisp , распространяемый по лицензии GNU LGPL .
• inflate.s7i / gzip.s7i — чистая основе Seed7 реализация декомпрессии Deflate и gzip на , созданная Томасом Мертесом. Доступно по лицензии GNU LGPL .
• pyflate на чистом Python, — автономный декодер Deflate ( gzip ) и bzip2 созданный Полом Слэйденом. Написано для исследований/прототипирования и доступно по лицензиям BSD / GPL / LGPL / DFSG .
• deflatelua на чистом Lua — реализация Deflate и декомпрессии gzip /zlib, автор — Дэвид Манура.
• inflate — реализация Inflate на чистом Javascript от Криса Дикинсона.
• pako : оптимизированный по скорости порт zlib для JavaScript. Содержит отдельную сборку только с функцией инфляции.

Аппаратные декодеры

• Графический процессор Serial Inflate от BitSim. Аппаратная реализация Inflate. BitSim BADGE (Bitsim Accelerated Display Graphics Engine) для встроенных систем. Часть контроллера
• Реализация HDL-Deflate GPL FPGA.
• ZipAccel-D от CAST Inc. Это ядро ​​Silicon IP, поддерживающее распаковку файлов Deflate, Zlib и Gzip . IP-ядро ZipAccel-D, которое можно реализовать в ASIC или FPGA. Компания предлагает эталонные конструкции плат ускорителя сжатия/декомпрессии для FPGA Intel ( ZipAccel-RD-INT ) и FPGA Xilinx ( ZipAccel-RD-XIL ).
• Процессоры IBM z15 включают улучшенную версию аппаратного ускорения Nest Accelerator Unit (NXU) от карт расширения ввода-вывода zEDC Express, используемых в системах z14 для аппаратного сжатия и распаковки Deflate, как указано в RFC1951.
• Начиная с архитектуры POWER9 , IBM добавила аппаратную поддержку сжатия и распаковки Deflate (как указано в RFC 1951) в ранее криптоцентричное ядро ​​ускорителя Nest (NX), представленное в POWER7+ . Эта поддержка доступна для программ, работающих с пакетом расширения AIX 7.2 Technology Level 4 или пакетом обновления 2 для AIX 7.2 Technology Level 5, через библиотеку zlibNX.

См. также

• Список форматов архивов
• Список файловых архиваторов
• Сравнение файловых архиваторов

Внешние ссылки

• PKWARE, Inc. appnote.txt, Спецификация формата файла .ZIP. Архивировано 5 декабря 2014 г. на Wayback Machine ; Раздел 10, X. Дефляция – Метод 8 .
• RFC 1951 – Спецификация формата сжатых данных Deflate, версия 1.3
• Домашняя страница zlib
• Объяснение алгоритма выкачивания - Антеус Фельдспар
• Расширенное применение суффиксных деревьев для сжатия данных. Архивировано 23 сентября 2016 г. на Wayback Machine — отличный алгоритм для реализации Deflate, автор Джеспер Ларссон.
• Zip-файлы: история, объяснение и реализация — пошаговое руководство по реализации Deflate.