Войти
В вычислениях, Deflate - это без потерь сжатие данных формат файла, в котором используется комбинация LZSS и кодирования Хаффмана. Он был разработан Филом Кацем для версии 2 его инструмента архивирования PKZIP. Позже Deflate был описан в RFC 1951 (1996).
Кац также разработал оригинальный алгоритм, используемый для создания потоков Deflate. Этот алгоритм был запатентован как U.S. Патент 5051745, переуступленный PKWARE, Inc. Как указано в документе RFC, широко считалось, что алгоритм создания файлов Deflate может быть реализован способом, не охваченным патентами. Это привело к его широкому использованию, например, в сжатых файлах gzip и файлах изображений PNG в дополнение к формату файлов ZIP, для которого он был первоначально разработан Кацем. Срок действия патента истек.
Поток Deflate состоит из серии блоков. Каждому блоку предшествует 3- бит заголовок:
1: это последний блок в потоке.0: Там - это еще блоки, которые нужно обработать после этого.00: Сохраненный (также известный как необработанный или буквальный) раздел длиной от 0 до 65 535 байтов01: Статический сжатый блок Хаффмана с использованием предварительно согласованного дерева Хаффмана, определенного в RFC10: Сжатый блок с предоставленной таблицей Хаффмана11: Зарезервировано - не использовать.Параметр сохраненного блока добавляет минимум накладные расходы и используется для несжимаемых данных.
Наиболее сжимаемые данные будут закодированы с использованием метода 10, динамического кодирования Хаффмана, который создает оптимизированное дерево Хаффмана, настроенное для каждого блока данных индивидуально. Инструкции по созданию необходимого дерева Хаффмана следуют сразу за заголовком блока. Статическая опция Хаффмана используется для коротких сообщений, где фиксированная экономия, полученная за счет исключения дерева, перевешивает процентную потерю сжатия из-за использования неоптимального (таким образом, технически не Хаффмана) кода.
Сжатие достигается в два этапа:
Внутри сжатых блоков, если обнаруживается повторяющаяся серия байтов (повторяющаяся строка), тогда вставляется обратная ссылка , вместо этого добавляется ссылка на предыдущее местоположение этой идентичной строки. Закодированное совпадение с более ранней строкой состоит из 8-битной длины (3–258 байтов) и 15-битного расстояния (1–32 768 байтов) до начала дубликата. Относительные обратные ссылки могут быть сделаны по любому количеству блоков, если расстояние появляется в пределах последних 32 KiB декодированных несжатых данных (так называемое скользящее окно).
Если расстояние меньше длины, дубликат перекрывает сам себя, указывая на повторение. Например, серия из 10 идентичных байтов может быть закодирована как один байт, за которым следует дубликат длиной 9, начиная с предыдущего байта.
Поиск в предыдущем тексте повторяющихся подстрок - это наиболее затратная часть алгоритма DEFLATE и операция, на которую влияют настройки уровня сжатия.
Второй этап сжатия состоит из замены обычно используемых символов более короткими представлениями и менее часто используемых символов более длинными представлениями. Используемый метод - это кодирование Хаффмана, которое создает дерево без префикса неперекрывающихся интервалов, где длина каждой последовательности обратно пропорциональна логарифму вероятности того, что этот символ должен быть закодирован. Чем больше вероятность того, что символ должен быть закодирован, тем короче будет его битовая последовательность.
Создается дерево, содержащее пространство для 288 символов:
За кодом длины совпадения всегда следует код расстояния. На основе считанного кода расстояния могут быть считаны дополнительные "лишние" биты для получения окончательного расстояния. Дерево расстояний содержит пространство для 32 символов:
Обратите внимание, что для соответствия символы расстояния 2–29, количество дополнительных битов можно рассчитать как 
Два кода (288-символьное / литеральное дерево и 32-символьное дерево расстояний) сами кодируются как канонические коды Хаффмана, задавая битовую длину кода для каждого символа. Сами длины в битах закодированы по длине серий для получения как можно более компактного представления. В качестве альтернативы включению представления в виде дерева опция «статическое дерево» предоставляет стандартные фиксированные деревья Хаффмана. Сжатый размер с использованием статических деревьев может быть вычислен с использованием той же статистики (количество раз, когда каждый символ появляется), которая используется для генерации динамических деревьев, поэтому для компрессора легко выбрать тот, который меньше.
На этапе сжатия именно кодировщик выбирает время, затрачиваемое на поиск совпадающих строк. Эталонная реализация zlib / gzip позволяет пользователю выбирать из скользящей шкалы вероятного результирующего уровня сжатия в зависимости от скорости кодирования. Варианты варьируются от 0(не пытаться сжать, просто сохранять в несжатом виде) до 9, представляя максимальные возможности эталонной реализации в zlib / gzip.
Были созданы другие кодеры Deflate, все из которых также будут создавать совместимый битовый поток, который может быть распакован любым существующим декодером Deflate. Разные реализации, вероятно, будут давать вариации в конечном созданном закодированном битовом потоке. В версиях кодировщика, отличных от zlib, основное внимание уделялось созданию более эффективно сжатого и закодированного потока меньшего размера.
Deflate64, указанный PKWARE, является частным вариантом Deflate. Принципиально тот же алгоритм. Что изменилось, так это увеличение размера словаря с 32 КБ до 64 КБ, расширение кодов расстояния до 16 бит, чтобы они могли адресовать диапазон в 64 КБ, и код длины, который увеличен до 16 бит, чтобы он может определять длину от трех до 65 538 байтов. Это приводит к тому, что Deflate64 имеет более длительное время сжатия и потенциально немного более высокую степень сжатия, чем Deflate. Некоторые бесплатные проекты и / или проекты с открытым исходным кодом поддерживают Deflate64, например 7-Zip, в то время как другие, такие как zlib, не поддерживают его из-за проприетарного характера процедуры и очень скромное увеличение производительности по сравнению с Deflate.
Реализации Deflate бесплатно доступны на многих языках. Программы на C обычно используют библиотеку zlib (под лицензией zlib License, которая позволяет использовать как бесплатное, так и проприетарное программное обеспечение). Программы, написанные с использованием диалектов Паскаля Borland, могут использовать paszlib; библиотека C ++ включена как часть 7-Zip / AdvanceCOMP. Java включает поддержку как часть стандартной библиотеки (в java.util.zip). Библиотека базовых классов Microsoft.NET Framework 2.0 поддерживает его в пространстве имен System.IO.Compression. Программы на Ada могут использовать Zip-Ada (чистый) или ZLib-Ada с толстой привязкой к zlib.
AdvanceCOMP использует версию Deflate с более высокой степенью сжатия, реализованную в 7-Zip (или, возможно, Zopfli в последних версиях), чтобы включить повторное сжатие gzip, Файлы PNG, MNG и ZIP с возможностью достижения меньшего размера файла, чем zlib при максимальных настройках.
193f: 0001), способную сжимать потоки с помощью Deflate со скоростью до 3,0 Гбит / с (375 МБ / с) для входящих несжатых данных. Вместе с ядром Linux драйвером для AHA361-PCIX есть утилита «ahagzip» и настроенный «mod_deflate_aha», способный использовать оборудование сжатие из Apache. Аппаратное обеспечение основано на Xilinx Virtex FPGA и четырех специализированных AHA3601 ASIC. Платы AHA361 / AHA362 ограничены обработкой только статических блоков Хаффмана и требуют модификации программного обеспечения для добавления поддержки - карты не могли поддерживать полную спецификацию Deflate, то есть они могли надежно декодировать только свой собственный вывод (поток, который не содержат любые динамические блоки Хаффмана типа 2).17b4: 0011) или PCI-X с от одного до шести модулей сжатия с заявленной скоростью обработки до 3,6 Гбит / с. (450 МБ / с). Доступны версии карт под отдельным брендом WebEnhance, специально разработанные для использования в Интернете, а не для SAN или резервного копирования; версии PCIe, также производится MX4E.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 полностью совместимы с дефляцией. ПроцессорыInflate - это процесс декодирования, который использует битовый поток Deflate для распаковки. и правильно производит исходные полноразмерные данные или файл.
Обычная цель альтернативной реализации с расширением - это сильно оптимизированная скорость декодирования или чрезвычайно предсказуемое использование ОЗУ для встроенных микроконтроллерных систем.
PCDEZIP, Боб Фландерс и Майкл Холмс, опубликовано в журнале PC Magazine 11 января 1994 г.appnote.txt, Спецификация формата файла.ZIP ; Раздел 10, X. Deflating - Method 8.