stringtranslate.com

Сдувать

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

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

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

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

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

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

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

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

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

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

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

Сокращение бита

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

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

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

Обратите внимание, что для символов расстояния соответствия 2–29 количество дополнительных бит можно рассчитать как .

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

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

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

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

Deflate64/Улучшенный Deflate

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

Ссылки

  1. ^ Авторы Go. "flate package - compress/flate - Go Packages". Язык программирования Go . Google . Получено 5 сентября 2023 г. Пакет flate реализует формат сжатых данных DEFLATE, описанный в выпуске RFC 1951.
  2. ^ Adobe Systems Incorporated . "PDF 32000-1:2008: Управление документами — Формат переносимых документов — Часть 1: PDF 1.7" (PDF) . Adobe Open Source . Adobe. стр. 23 . Получено 5 сентября 2023 г. . FlateDecode [...] Распаковывает данные, закодированные с использованием метода сжатия zlib/deflate
  3. ^ ab Deutsch, L. Peter (май 1996 г.). Спецификация формата сжатых данных DEFLATE версии 1.3. IETF . стр. 1. раздел. Аннотация. doi : 10.17487/RFC1951 . RFC 1951. Получено 23.04.2014 .
  4. ↑ Патент США 5051745, Katz, Phillip W. , «String Searcher, and Compressor Using Same», опубликован 24 сентября 1991 г., выдан 24 сентября 1991 г., передан PKWare Inc. 
  5. ^ Дэвид, Саломон (2007). Сжатие данных: Полный справочник (4-е изд.). Springer. стр. 241. ISBN 978-1-84628-602-5.
  6. ^ "Binary Essence – Deflate64". Архивировано из оригинала 21 июня 2017 года . Получено 22 мая 2011 года .{{cite web}}: CS1 maint: бот: исходный статус URL неизвестен ( ссылка )
  7. ^ "Binary Essence – "Calgary Corpus" compression comparisons". Архивировано из оригинала 27 декабря 2017 года . Получено 22 мая 2011 года .{{cite web}}: CS1 maint: бот: исходный статус URL неизвестен ( ссылка )
  8. ^ "-m (Установить метод сжатия) переключатель". sevenzip.osdn.jp . Архивировано из оригинала 2022-04-09 . Получено 2023-01-21 .
  9. ^ История алгоритмов сжатия данных без потерь – Deflate64
  10. ^ Часто задаваемые вопросы по zlib – Поддерживает ли zlib новый формат «Deflate64», представленный PKWare?
  11. ^ "Plan 9 из Bell Labs's /n/sources/plan9/sys/src/libflate". plan9.bell-labs.com . Lucent Technologies. Архивировано из оригинала 2006-03-15.
  12. ^ "Высокопроизводительное сжатие DEFLATE с оптимизацией для наборов геномных данных". Intel Software . 1 октября 2019 г. Получено 18 января 2020 г.
  13. ^ "libdeflate". Сильно оптимизированная библиотека для сжатия и распаковки DEFLATE/zlib/gzip .
  14. ↑ Маццолени, Андреа (21 февраля 2023 г.). «амадванс/адванцемп». Гитхаб .
  15. ^ "Процессоры Intel® Xeon® серий E5-2600 и E5-2400 с набором микросхем Intel® Communications серии 89xx" . Получено 18.05.2016 .
  16. ^ ab "Представляем IBM z15 — корпоративную платформу для критически важных гибридных мультиоблаков". IBM . 12 сентября 2019 г. Получено 01.11.2021 г.
  17. ^ ab Lascu, Octavian (28 апреля 2021 г.). Техническое руководство IBM z15 (8562), стр. 97. IBM Redbooks. ISBN 9780738458991. Получено 01.11.2021 .
  18. ^ ab "Сжатие данных с использованием библиотеки zlibNX - Документация IBM". IBM . Получено 2021-11-01 .
  19. ^ ab "Эксплуатация внутриядерного ускорения процессоров POWER для AIX" . Получено 01.11.2021 .

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