Войти
В вычислении, выкачивает является без потерь сжатия данных формат файла, который использует комбинацию LZSS и кодирования по алгоритму Хаффмана. Он был разработан Филом Кацем для версии 2 его инструмента архивирования PKZIP. Позже Deflate был указан в RFC 1951 (1996).
Кац также разработал оригинальный алгоритм, используемый для создания потоков Deflate. Этот алгоритм был запатентован как патент США 5051745 и переуступлен PKWARE, Inc. Как указано в документе RFC, широко считалось, что алгоритм создания файлов Deflate может быть реализован способом, не охваченным патентами. Это привело к его широкому использованию - например, в файлах, сжатых с помощью gzip, и файлах изображений PNG, в дополнение к формату файлов ZIP, для которого он был первоначально разработан Кацем. Срок действия патента истек.
Поток Deflate состоит из серии блоков. Каждому блоку предшествует 3- битный заголовок:
1: Это последний блок в потоке.0: Есть еще блоки для обработки после этого.00: Сохраненный (также известный как необработанный или буквальный) раздел длиной от 0 до 65 535 байт.01: Статический сжатый блок Хаффмана, использующий предварительно согласованное дерево Хаффмана, определенное в RFC.10: Сжатый блок в комплекте с таблицей Хаффмана.11: Зарезервировано - не использовать.Опция сохраненного блока добавляет минимальные накладные расходы и используется для несжимаемых данных.
Большинство сжимаемых данные будут в конечном итоге кодируются с использованием методы 10, то динамический Хаффман кодирование, которая производит оптимизированный Хаффман дерево настроенное для каждого блока данных в отдельности. Инструкции по созданию необходимого дерева Хаффмана следуют сразу за заголовком блока. Статическая опция Хаффмана используется для коротких сообщений, где фиксированная экономия, полученная за счет исключения дерева, перевешивает процентную потерю сжатия из-за использования неоптимального (таким образом, технически не Хаффмана) кода.
Сжатие достигается в два этапа:
Второй этап сжатия состоит из замены часто используемых символов более короткими представлениями и менее часто используемых символов более длинными представлениями. Используемый метод - это кодирование Хаффмана, которое создает дерево без префикса неперекрывающихся интервалов, где длина каждой последовательности обратно пропорциональна логарифму вероятности того, что этот символ должен быть закодирован. Чем больше вероятность того, что символ должен быть закодирован, тем короче будет его битовая последовательность.
Создается дерево, содержащее место для 288 символов:
За кодом длины совпадения всегда следует код расстояния. На основе считанного кода расстояния могут быть считаны дополнительные «лишние» биты для получения окончательного расстояния. Дерево расстояний содержит место для 32 символов:
Обратите внимание, что для символов расстояния совпадения 2–29 количество дополнительных битов можно рассчитать как.
Два кода (288-символьное / буквальное дерево и 32-символьное дерево расстояний) сами кодируются как канонические коды Хаффмана, задавая битовую длину кода для каждого символа. Сами длины в битах кодируются по длине серий, чтобы получить как можно более компактное представление. В качестве альтернативы включению представления в виде дерева опция «статическое дерево» предоставляет стандартные фиксированные деревья Хаффмана. Сжатый размер с использованием статических деревьев может быть вычислен с использованием той же статистики (количество раз, когда каждый символ появляется), которая используется для генерации динамических деревьев, поэтому для компрессора легко выбрать тот, который меньше.
Внутри сжатых блоков, если обнаруживается повторяющаяся серия байтов (повторяющаяся строка), тогда вставляется обратная ссылка, вместо этого указывается предыдущее расположение этой идентичной строки. Закодированное совпадение с более ранней строкой состоит из 8-битной длины (3–258 байтов) и 15-битного расстояния (1–32 768 байтов) до начала дубликата. Относительные обратные ссылки могут быть сделаны по любому количеству блоков, если расстояние появляется в пределах последних 32 КиБ декодированных несжатых данных (так называемое скользящее окно).
Если расстояние меньше длины, дубликат перекрывает сам себя, указывая на повторение. Например, серия из 10 идентичных байтов может быть закодирована как один байт, за которым следует дубликат длиной 9, начиная с предыдущего байта.
Поиск повторяющихся подстрок в предыдущем тексте является наиболее затратной с точки зрения вычислений частью алгоритма DEFLATE и операцией, на которую влияют настройки уровня сжатия.
На этапе сжатия кодировщик выбирает время, затрачиваемое на поиск совпадающих строк. Эталонная реализация 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. Программы на Аде могут использовать Zip-Ada (чистый) или толстую привязку ZLib-Ada к zlib.
AdvanceCOMP использует версию Deflate с более высокой степенью сжатия, реализованную в 7-Zip (или, возможно, Zopfli в последних версиях), чтобы включить повторное сжатие файлов gzip, PNG, MNG и ZIP с возможностью достижения меньших размеров файлов, чем zlib может максимально настройки.
193f:0001:), способную сжимать потоки с помощью Deflate со скоростью до 3,0 Гбит / с (375 МБ / с) для входящих несжатых данных. К драйверу ядра Linux для AHA361-PCIX прилагается " " специализированная утилита ", способная использовать аппаратное сжатие из Apache. Аппаратное обеспечение основано на ПЛИС Xilinx Virtex и четырех специализированных ASIC AHA3601. Платы AHA361 / AHA362 ограничены обработкой только статических блоков Хаффмана и требуют модификации программного обеспечения для добавления поддержки - карты не могли поддерживать полную спецификацию Deflate, то есть они могли надежно декодировать только свой собственный вывод (поток, который не поддерживался). содержат любые динамические блоки Хаффмана типа 2). ahagzipmod_deflate_aha 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 для распаковки и правильно производит исходные полноразмерные данные или файл.
Обычная цель альтернативной реализации Inflate - это сильно оптимизированная скорость декодирования или чрезвычайно предсказуемое использование ОЗУ для встроенных систем микроконтроллера.
PCDEZIP, Боб Фландерс и Майкл Холмс, опубликовано в журнале PC Magazine 11 января 1994 года.appnote.txt, .ZIP Формат файла спецификации ; Раздел 10, X. Спускание - Метод 8.