Сжатие без потерь — это класс сжатия данных , который позволяет идеально восстановить исходные данные из сжатых данных без потери информации . Сжатие без потерь возможно, поскольку большинство реальных данных демонстрируют статистическую избыточность . [1] Напротив, сжатие с потерями позволяет восстановить только аппроксимацию исходных данных , хотя обычно со значительно улучшенной степенью сжатия (и, следовательно, меньшими размерами носителя).
Благодаря принципу «ячейки» ни один алгоритм сжатия без потерь не может уменьшить размер всех возможных данных: некоторые данные станут длиннее как минимум на один символ или байт.
Алгоритмы сжатия обычно эффективны для документов, читаемых человеком и компьютером, и не могут уменьшить размер случайных данных, не содержащих избыточности . Существуют различные алгоритмы, которые разработаны либо с учетом определенного типа входных данных, либо с учетом конкретных предположений о том, какие виды избыточности могут содержать несжатые данные.
Сжатие данных без потерь используется во многих приложениях. Например, он используется в формате файла ZIP и в инструменте GNU gzip . Он также часто используется в качестве компонента в технологиях сжатия данных с потерями (например, совместная предварительная обработка среднего и бокового стереосигнала без потерь с помощью кодеров MP3 и других аудиокодеров с потерями). [2]
Сжатие без потерь используется в тех случаях, когда важно, чтобы исходные и распакованные данные были идентичны, или когда отклонения от исходных данных были бы нежелательны. Типичными примерами являются исполняемые программы, текстовые документы и исходный код. Некоторые форматы файлов изображений, такие как PNG или GIF , используют только сжатие без потерь, тогда как другие, такие как TIFF и MNG , могут использовать методы либо без потерь, либо с потерями. Аудиоформаты без потерь чаще всего используются для архивирования или производства, тогда как аудиофайлы меньшего размера с потерями обычно используются на портативных плеерах и в других случаях, когда пространство для хранения ограничено или точное копирование звука не требуется.
Большинство программ сжатия без потерь последовательно выполняют две вещи: на первом этапе создается статистическая модель входных данных, а на втором этапе эта модель используется для сопоставления входных данных с битовыми последовательностями таким образом, чтобы «вероятные» (т. е. часто встречающиеся) данные даст более короткий результат, чем «невероятные» данные.
Основными алгоритмами кодирования, используемыми для создания битовых последовательностей, являются кодирование Хаффмана (также используемое алгоритмом дефлятирования ) и арифметическое кодирование . Арифметическое кодирование обеспечивает степень сжатия, близкую к наилучшей возможной для конкретной статистической модели, которая определяется информационной энтропией , тогда как сжатие Хаффмана проще и быстрее, но дает плохие результаты для моделей, которые имеют дело с вероятностями символов, близкими к 1.
Существует два основных способа построения статистических моделей: в статической модели данные анализируются и строится модель, затем эта модель сохраняется со сжатыми данными. Этот подход прост и модульен, но имеет тот недостаток, что хранить саму модель может быть дорого, а также то, что он вынуждает использовать одну модель для всех сжимаемых данных и поэтому плохо работает с файлами, содержащими разнородные данные. Адаптивные модели динамически обновляют модель по мере сжатия данных. И кодер, и декодер начинают с тривиальной модели, обеспечивающей плохое сжатие исходных данных, но по мере того, как они узнают больше о данных, производительность улучшается. Наиболее популярные виды сжатия, используемые сейчас на практике, используют адаптивные кодеры.
Методы сжатия без потерь можно разделить на категории в зависимости от типа данных, для сжатия которых они предназначены. Хотя, в принципе, любой алгоритм сжатия без потерь общего назначения (универсальный означает , что он может принимать любую битовую строку) может использоваться для любого типа данных, многие из них не могут достичь значительного сжатия данных, которые не имеют той формы, для которой они были предназначены для сжатия. Многие из методов сжатия без потерь, используемых для текста, также достаточно хорошо работают для индексированных изображений .
Эти методы используют преимущества специфических характеристик изображений, таких как распространенное явление смежных двумерных областей схожих тонов. Каждый пиксель, кроме первого, заменяется разницей с его левым соседом. Это приводит к тому, что малые значения имеют гораздо более высокую вероятность, чем большие значения. Это часто также применяется к звуковым файлам и позволяет сжимать файлы, содержащие в основном низкие частоты и небольшую громкость. Для изображений этот шаг можно повторить, приняв разницу к верхнему пикселю, а затем в видео можно измерить разницу до пикселя в следующем кадре.
Иерархическая версия этого метода берет соседние пары точек данных, сохраняет их разницу и сумму и на более высоком уровне с более низким разрешением продолжает суммировать. Это называется дискретным вейвлет-преобразованием . JPEG2000 дополнительно использует точки данных из других пар и коэффициенты умножения, чтобы смешать их с разницей. Эти коэффициенты должны быть целыми числами, чтобы результат был целым числом при любых обстоятельствах. Таким образом, значения увеличиваются, увеличивая размер файла, но, будем надеяться, распределение значений будет более пиковым. [ нужна цитата ]
Адаптивное кодирование использует вероятности из предыдущего образца при кодировании звука, из левого и верхнего пикселя при кодировании изображения и дополнительно из предыдущего кадра при кодировании видео. При вейвлет-преобразовании вероятности также проходят через иерархию.
Многие из этих методов реализованы в инструментах с открытым исходным кодом и в собственных инструментах, особенно в LZW и его вариантах. Некоторые алгоритмы запатентованы в США и других странах, и их законное использование требует лицензии патентообладателя. Из-за патентов на определенные виды сжатия LZW и, в частности, практики лицензирования патентообладателя Unisys, которую многие разработчики считали злоупотребительной, некоторые сторонники открытого исходного кода призывали людей избегать использования формата обмена графикой (GIF) для сжатия файлов неподвижных изображений в пользу портативного формата . Сетевая графика (PNG), которая сочетает в себе алгоритм дефляции на основе LZ77 с набором фильтров прогнозирования для конкретной области. Однако срок действия патентов на LZW истек 20 июня 2003 г. [3]
Многие из методов сжатия без потерь, используемых для текста, также достаточно хорошо работают для индексированных изображений , но есть и другие методы, которые не работают для обычного текста, но полезны для некоторых изображений (особенно простых растровых изображений), а также другие методы, которые используют преимущества конкретных характеристики изображений (такие как обычное явление смежных двумерных областей схожих тонов и тот факт, что цветные изображения обычно имеют преобладание ограниченного диапазона цветов из тех, которые можно представить в цветовом пространстве).
Как упоминалось ранее, сжатие звука без потерь — это несколько специализированная область. Алгоритмы сжатия звука без потерь могут использовать преимущества повторяющихся шаблонов, демонстрируемых волнообразной природой данных — по используя авторегрессионные модели для прогнозирования «следующего» значения и кодирования (надеюсь, небольшой) разницы между ожидаемым значением и фактическим. данные. Если разница между прогнозируемыми и фактическими данными (называемая ошибкой ) имеет тенденцию быть небольшой, то определенные значения разницы (например, 0, +1, -1 и т. д. в выборочных значениях) становятся очень частыми, что можно использовать путем их кодирования. в нескольких выходных битах.
Иногда бывает полезно сжать только различия между двумя версиями файла (или, при сжатии видео , последовательными изображениями в последовательности). Это называется дельта-кодированием (от греческой буквы Δ , которая в математике обозначает разницу), но этот термин обычно используется только в том случае, если обе версии имеют смысл вне сжатия и распаковки. Например, хотя процесс сжатия ошибки в вышеупомянутой схеме сжатия звука без потерь можно описать как дельта-кодирование аппроксимированной звуковой волны в исходную звуковую волну, аппроксимированная версия звуковой волны не имеет смысла ни в каком другом контексте. .
Ни один алгоритм сжатия без потерь не может эффективно сжимать все возможные данные . По этой причине существует множество различных алгоритмов, которые разработаны либо с учетом определенного типа входных данных, либо с конкретными предположениями о том, какие виды избыточности могут содержать несжатые данные.
Ниже перечислены некоторые из наиболее распространенных алгоритмов сжатия без потерь.
compress и утилитами Unix.См. список видеокодеков без потерь.
Криптосистемы часто сжимают данные («открытый текст») перед шифрованием для дополнительной безопасности. При правильной реализации сжатие значительно увеличивает расстояние уникальности за счет удаления шаблонов, которые могут облегчить криптоанализ . [9] Однако многие обычные алгоритмы сжатия без потерь создают заголовки, оболочки, таблицы или другие предсказуемые выходные данные, которые вместо этого могут упростить криптоанализ. Таким образом, криптосистемы должны использовать алгоритмы сжатия, выходные данные которых не содержат этих предсказуемых шаблонов.
Алгоритмы генетического сжатия (не путать с генетическими алгоритмами ) — это последнее поколение алгоритмов без потерь, которые сжимают данные (обычно последовательности нуклеотидов) с использованием как обычных алгоритмов сжатия, так и специальных алгоритмов, адаптированных к генетическим данным. В 2012 году группа ученых из Университета Джонса Хопкинса опубликовала первый алгоритм генетического сжатия, который не использует для сжатия внешние генетические базы данных. HAPZIPPER был специально разработан для данных HapMap и обеспечивает более чем 20-кратное сжатие (уменьшение размера файла на 95%), обеспечивая в 2–4 раза лучшее сжатие, намного быстрее, чем ведущие утилиты сжатия общего назначения. [10]
Алгоритмы сжатия геномных последовательностей, также известные как компрессоры последовательностей ДНК, исследуют тот факт, что последовательности ДНК обладают характерными свойствами, такими как инвертированные повторы. Наиболее успешными компрессорами являются XM и GeCo. [11] Для эукариот XM немного лучше по степени сжатия, хотя для последовательностей размером более 100 МБ его вычислительные требования непрактичны.
Самораспаковывающиеся исполняемые файлы содержат сжатое приложение и распаковщик. При выполнении декомпрессор прозрачно распаковывает и запускает исходное приложение. Особенно часто это используется при кодировании демо , где проводятся соревнования по демо со строгими ограничениями по размеру, вплоть до 1 КБ . Этот тип сжатия не ограничивается строго двоичными исполняемыми файлами, но также может применяться к сценариям, таким как JavaScript .
Алгоритмы сжатия без потерь и их реализации регулярно тестируются в параллельных тестах . Существует ряд более известных тестов сжатия. Некоторые тесты охватывают только степень сжатия данных , поэтому победители этих тестов могут оказаться непригодными для повседневного использования из-за низкой скорости лучших производительностей. Еще одним недостатком некоторых тестов является то, что их файлы данных известны, поэтому некоторые разработчики программ могут оптимизировать свои программы для достижения наилучшей производительности на определенном наборе данных. Победителями в этих тестах часто являются представители класса программного обеспечения для сжатия контекстного микширования .
Мэтт Махони в своем бесплатном буклете «Объяснение сжатия данных» за февраль 2010 года дополнительно перечисляет следующее: [12]
Веб-сайт Compression Ratings опубликовал сводную диаграмму «границы» степени сжатия и времени. [15]
Инструмент анализа сжатия [16] — это приложение для Windows, которое позволяет конечным пользователям оценивать характеристики производительности потоковых реализаций LZF4, Deflate, ZLIB, GZIP, BZIP2 и LZMA, используя свои собственные данные. Он производит измерения и диаграммы, с помощью которых пользователи могут сравнивать скорость сжатия, скорость распаковки и степень сжатия различных методов сжатия, а также исследовать, как уровень сжатия, размер буфера и операции очистки влияют на результаты.
Алгоритмы сжатия данных без потерь не могут гарантировать сжатие всех наборов входных данных. Другими словами, для любого алгоритма сжатия данных без потерь будет существовать набор входных данных, который не уменьшается при обработке этим алгоритмом, а для любого алгоритма сжатия данных без потерь, который уменьшает хотя бы один файл, будет хотя бы один файл, который он увеличивает. Это легко доказать с помощью элементарной математики, используя счетный аргумент, называемый принципом ячейки , следующим образом: [17] [18]
Большинство практических алгоритмов сжатия предоставляют возможность «экранирования», которая может отключить обычное кодирование для файлов, которые в результате кодирования станут длиннее. Теоретически требуется только один дополнительный бит, чтобы сообщить декодеру, что нормальное кодирование отключено для всего ввода; однако большинство алгоритмов кодирования используют для этой цели как минимум один полный байт (а обычно более одного). Например, сжатые файлы deflate никогда не должны увеличиваться более чем на 5 байт на каждые 65 535 байт входных данных.
В самом деле, если мы рассматриваем файлы длины N, если бы все файлы были равновероятными, то для любого сжатия без потерь, уменьшающего размер некоторого файла, ожидаемая длина сжатого файла (усредненная по всем возможным файлам длины N) обязательно должна быть больше N. [19] Поэтому, если мы ничего не знаем о свойствах данных, которые мы сжимаем, мы могли бы вообще не сжимать их. Алгоритм сжатия без потерь полезен только тогда, когда мы с большей вероятностью сжимаем файлы определенных типов, чем другие; тогда алгоритм можно было бы разработать для лучшего сжатия этих типов данных.
Таким образом, главный урок из этого аргумента заключается не в том, что человек рискует большими потерями, а просто в том, что он не может всегда выигрывать. Выбор алгоритма всегда означает неявный выбор подмножества всех файлов, которые станут короче. Это теоретическая причина, по которой нам нужны разные алгоритмы сжатия для разных типов файлов: не может быть алгоритма, подходящего для всех типов данных.
«Хитрость», которая позволяет алгоритмам сжатия без потерь, используемым для типа данных, для которых они были разработаны, последовательно сжимать такие файлы до более короткой формы, заключается в том, что все файлы, для обработки которых предназначены алгоритмы, имеют некоторую форму легко моделируемой избыточности , которая алгоритм предназначен для удаления и, таким образом, принадлежит к подмножеству файлов, которые этот алгоритм может сделать короче, тогда как другие файлы не будут сжиматься или даже увеличиваться в размерах. Алгоритмы, как правило, весьма специфически настроены на определенный тип файла: например, программы сжатия звука без потерь плохо работают с текстовыми файлами, и наоборот.
В частности, файлы случайных данных не могут быть последовательно сжаты с помощью любого мыслимого алгоритма сжатия данных без потерь; действительно, этот результат используется для определения понятия случайности в колмогоровской сложности . [20]
Доказуемо невозможно создать алгоритм, который сможет сжимать любые данные без потерь. Несмотря на то, что за годы существования компаний, добивавшихся «идеального сжатия», когда произвольное число N случайных битов всегда можно сжать до N - 1 бит, было много заявлений, подобные утверждения можно смело отбросить, даже не рассматривая какие-либо дополнительные подробности относительно предполагаемая схема сжатия. Такой алгоритм противоречит фундаментальным законам математики, поскольку, если бы он существовал, его можно было бы применять неоднократно для уменьшения без потерь любого файла до длины 1. [18]
С другой стороны, также было доказано [21] , что не существует алгоритма определения несжимаемости файла в смысле колмогоровской сложности. Следовательно, вполне возможно, что любой конкретный файл, даже если он выглядит случайным, может быть значительно сжат, включая размер декомпрессора. Примером могут служить цифры математической константы «пи» , которые кажутся случайными, но могут быть сгенерированы очень маленькой программой. Однако, хотя невозможно определить, является ли конкретный файл несжимаемым, простая теорема о несжимаемых строках показывает, что более 99% файлов любой заданной длины не могут быть сжаты более чем на один байт (включая размер декомпрессора).
Абстрактно алгоритм сжатия можно рассматривать как функцию последовательностей (обычно октетов). Сжатие считается успешным, если полученная последовательность короче исходной последовательности (и инструкций для карты декомпрессии). Чтобы алгоритм сжатия был без потерь , карта сжатия должна формировать инъекцию от «простых» к «сжатым» битовым последовательностям. Принцип «ячейки» запрещает биекцию между набором последовательностей длины N и любым подмножеством набора последовательностей длины N -1. Следовательно, невозможно создать алгоритм без потерь, который уменьшал бы размер каждой возможной входной последовательности. [22]
Разработчики реальных алгоритмов сжатия признают, что потоки с высокой информационной энтропией не могут быть сжаты, и, соответственно, включают средства для обнаружения и обработки этого условия. Очевидный способ обнаружения — применить алгоритм необработанного сжатия и проверить, меньше ли его выходные данные, чем входные. Иногда обнаружение осуществляется с помощью эвристики ; например, приложение сжатия может считать файлы, имена которых заканчиваются на «.zip», «.arj» или «.lha», несжимаемыми без какого-либо более сложного обнаружения. Распространенным способом решения этой ситуации является цитирование входных данных или несжимаемых частей входных данных в выходных данных, что минимизирует затраты на сжатие. Например, формат данных zip определяет «метод сжатия» «Сохранено» для входных файлов, которые были дословно скопированы в архив. [23]
Марк Нельсон, в ответ на заявления о «магических» алгоритмах сжатия, появившихся в comp.compression, создал двоичный файл размером 415 241 байт с высокоэнтропийным содержанием и объявил публичный вызов в размере 100 долларов каждому, кто напишет программу, которая вместе со своими входными данными , будет меньше, чем предоставленные им двоичные данные, но сможет восстановить их без ошибок. [24] Аналогичный вызов с наградой в 5000 долларов предложил Майк Голдман. [25]
{{cite book}}: CS1 maint: location missing publisher (link){{cite book}}: |journal=игнорируется ( помощь )Теорема 2.6. Функция не является частично рекурсивной.
