stringtranslate.com

Сжатие без потерь

Сжатие без потерь — это класс сжатия данных , который позволяет идеально восстановить исходные данные из сжатых данных без потери информации . Сжатие без потерь возможно, поскольку большинство реальных данных демонстрируют статистическую избыточность . [1] Напротив, сжатие с потерями позволяет восстановить только приближение исходных данных , хотя обычно со значительно улучшенными показателями сжатия (и, следовательно, уменьшенными размерами носителей).

Используя принцип «ящика» , ни один алгоритм сжатия без потерь не может уменьшить размер всех возможных данных: некоторые данные станут длиннее как минимум на один символ или бит.

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

Сжатие данных без потерь используется во многих приложениях. Например, оно используется в формате файла ZIP и в инструменте GNU gzip . Оно также часто используется как компонент в технологиях сжатия данных с потерями (например, предварительная обработка стереозвука без потерь mid/side с помощью кодировщиков MP3 и других кодировщиков аудио с потерями). [2]

Сжатие без потерь используется в случаях, когда важно, чтобы исходные и распакованные данные были идентичны, или когда отклонения от исходных данных были бы неблагоприятными. Обычными примерами являются исполняемые программы, текстовые документы и исходный код. Некоторые форматы файлов изображений, такие как PNG или GIF , используют только сжатие без потерь, в то время как другие, такие как TIFF и MNG, могут использовать как методы сжатия без потерь, так и методы сжатия с потерями. Форматы аудио без потерь чаще всего используются для архивирования или производства, в то время как меньшие аудиофайлы с потерями обычно используются на портативных плеерах и в других случаях, когда дисковое пространство ограничено или точная репликация аудио не нужна.

Методы

Большинство программ сжатия без потерь выполняют две операции последовательно: на первом этапе создается статистическая модель для входных данных, а на втором этапе эта модель используется для сопоставления входных данных с последовательностями битов таким образом, что «вероятные» (т. е. часто встречающиеся) данные будут давать более короткие выходные данные, чем «маловероятные» данные.

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

Существует два основных способа построения статистических моделей: в статической модели данные анализируются и строится модель, затем эта модель сохраняется вместе со сжатыми данными. Этот подход прост и модульен, но имеет тот недостаток, что сама модель может быть дорогой для хранения, а также то, что он заставляет использовать одну модель для всех сжимаемых данных и поэтому плохо работает с файлами, содержащими неоднородные данные. Адаптивные модели динамически обновляют модель по мере сжатия данных. И кодер, и декодер начинают с тривиальной модели, что приводит к плохому сжатию исходных данных, но по мере того, как они узнают больше о данных, производительность улучшается. Большинство популярных типов сжатия, используемых на практике, теперь используют адаптивные кодеры.

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

Мультимедиа

Эти методы используют преимущества специфических характеристик изображений, таких как распространенное явление смежных 2-D областей схожих тонов. Каждый пиксель, кроме первого, заменяется разницей с его левым соседом. Это приводит к тому, что малые значения имеют гораздо большую вероятность, чем большие значения. Это часто применяется также к звуковым файлам и может сжимать файлы, содержащие в основном низкие частоты и низкую громкость. Для изображений этот шаг можно повторить, взяв разницу с верхним пикселем, а затем в видео можно взять разницу с пикселем в следующем кадре.

Иерархическая версия этой техники берет соседние пары точек данных, сохраняет их разность и сумму, и на более высоком уровне с более низким разрешением продолжает с суммами. Это называется дискретным вейвлет-преобразованием . JPEG2000 дополнительно использует точки данных из других пар и коэффициенты умножения, чтобы смешать их с разностью. Эти коэффициенты должны быть целыми числами, так что результат будет целым числом при любых обстоятельствах. Таким образом, значения увеличиваются, увеличивая размер файла, но распределение значений может быть более пиковым. [ необходима цитата ]

Адаптивное кодирование использует вероятности из предыдущего образца при кодировании звука, из левого и верхнего пикселя при кодировании изображения и дополнительно из предыдущего кадра при кодировании видео. В вейвлет-преобразовании вероятности также передаются через иерархию. [3]

Историко-правовые вопросы

Многие из этих методов реализованы в открытых и фирменных инструментах, в частности LZW и его вариантах. Некоторые алгоритмы запатентованы в Соединенных Штатах и ​​других странах, и их законное использование требует лицензирования держателем патента. Из-за патентов на определенные виды сжатия LZW и, в частности, практики лицензирования держателем патента Unisys, которую многие разработчики считали злоупотребляющей, некоторые сторонники открытого исходного кода призывали людей избегать использования формата Graphics Interchange Format (GIF) для сжатия неподвижных файлов изображений в пользу Portable Network Graphics (PNG), который объединяет алгоритм deflate на основе LZ77 с выбором фильтров прогнозирования, специфичных для домена. Однако патенты на LZW истекли 20 июня 2003 года. [4]

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

Как упоминалось ранее, сжатие звука без потерь — это несколько специализированная область. Алгоритмы сжатия звука без потерь могут использовать повторяющиеся шаблоны, показанные волнообразной природой данных ‍ — ‍ по сути, используя авторегрессионные модели для прогнозирования «следующего» значения и кодирования (возможно, небольшой) разницы между ожидаемым значением и фактическими данными. Если разница между прогнозируемыми и фактическими данными (называемая ошибкой ) имеет тенденцию быть небольшой, то определенные значения разницы (например, 0, +1, −1 и т. д. в значениях выборки) становятся очень частыми, что можно использовать, кодируя их в нескольких выходных битах.

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

Методы

Ни один алгоритм сжатия без потерь не может эффективно сжать все возможные данные (см. § Ограничения для получения дополнительной информации) . По этой причине существует множество различных алгоритмов, которые разработаны либо с учетом определенного типа входных данных, либо с определенными предположениями о том, какие виды избыточности, вероятно, будут содержаться в несжатых данных.

Ниже перечислены некоторые из наиболее распространенных алгоритмов сжатия без потерь.

Общего назначения

Аудио

Растровая графика

3D-графика

Видео

Посмотреть список кодеков видео без потерь

Криптография

Криптосистемы часто сжимают данные («открытый текст») перед шифрованием для дополнительной безопасности. При правильной реализации сжатие значительно увеличивает расстояние уникальности , удаляя шаблоны, которые могут облегчить криптоанализ . [9] Однако многие обычные алгоритмы сжатия без потерь создают заголовки, оболочки, таблицы или другие предсказуемые выходные данные, которые вместо этого могут облегчить криптоанализ. Таким образом, криптосистемы должны использовать алгоритмы сжатия, выходные данные которых не содержат этих предсказуемых шаблонов.

Генетика и геномика

Алгоритмы генетического сжатия (не путать с генетическими алгоритмами ) — это последнее поколение алгоритмов без потерь, которые сжимают данные (обычно последовательности нуклеотидов) с использованием как обычных алгоритмов сжатия, так и специальных алгоритмов, адаптированных к генетическим данным. В 2012 году группа ученых из Университета Джонса Хопкинса опубликовала первый алгоритм генетического сжатия, который не полагается на внешние генетические базы данных для сжатия. HAPZIPPER был адаптирован для данных HapMap и достигает более чем 20-кратного сжатия (уменьшение размера файла на 95%), обеспечивая сжатие в 2–4 раза лучше, чем ведущие универсальные утилиты сжатия. [10]

Алгоритмы сжатия геномной последовательности, также известные как компрессоры последовательностей ДНК, исследуют тот факт, что последовательности ДНК имеют характерные свойства, такие как инвертированные повторы. Наиболее успешными компрессорами являются XM и GeCo. [11] Для эукариот XM немного лучше по коэффициенту сжатия, хотя для последовательностей размером более 100 МБ его вычислительные требования непрактичны.

Исполняемые файлы

Самораспаковывающиеся исполняемые файлы содержат сжатое приложение и декомпрессор. При запуске декомпрессор прозрачно распаковывает и запускает исходное приложение. Это особенно часто используется в демо -кодировании, где проводятся соревнования для демонстраций со строгими ограничениями по размеру, вплоть до 1k . Этот тип сжатия не ограничивается строго бинарными исполняемыми файлами, но может также применяться к скриптам, таким как 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] , что не существует алгоритма для определения того, является ли файл несжимаемым в смысле сложности Колмогорова. Следовательно, возможно, что любой конкретный файл, даже если он кажется случайным, может быть значительно сжат, даже включая размер декомпрессора. Примером являются цифры математической константы pi , которые кажутся случайными, но могут быть сгенерированы очень маленькой программой. Однако, даже если невозможно определить, является ли конкретный файл несжимаемым, простая теорема о несжимаемых строках показывает, что более 99% файлов любой заданной длины не могут быть сжаты более чем на один байт (включая размер декомпрессора).

Математическое образование

Абстрактно, алгоритм сжатия можно рассматривать как функцию последовательностей (обычно октетов). Сжатие успешно, если полученная последовательность короче исходной последовательности (и инструкций для карты распаковки). Чтобы алгоритм сжатия был без потерь , карта сжатия должна формировать инъекцию из «простых» в «сжатые» битовые последовательности. Принцип ящика запрещает биекцию между набором последовательностей длины N и любым подмножеством набора последовательностей длины N −1. Следовательно, невозможно создать алгоритм без потерь, который уменьшает размер каждой возможной входной последовательности. [22]

Точки приложения в реальной теории сжатия

Разработчики реальных алгоритмов сжатия признают, что потоки с высокой информационной энтропией не могут быть сжаты, и соответственно включают средства для обнаружения и обработки этого состояния. Очевидный способ обнаружения — применение алгоритма необработанного сжатия и проверка того, меньше ли его вывод, чем ввод. Иногда обнаружение выполняется эвристикой ; например, приложение сжатия может считать файлы, имена которых заканчиваются на «.zip», «.arj» или «.lha», несжимаемыми без какого-либо более сложного обнаружения. Обычный способ обработки этой ситуации — цитирование ввода или несжимаемых частей ввода в выводе, что минимизирует накладные расходы на сжатие. Например, формат данных zip определяет «метод сжатия» «Stored» для входных файлов, которые были скопированы в архив дословно. [23]

Задача «Миллион случайных цифр»

Марк Нельсон, в ответ на заявления о «магических» алгоритмах сжатия, появляющихся в comp.compression, создал двоичный файл размером 415 241 байт с высокоэнтропийным содержимым и объявил публичный вызов в 100 долларов любому, кто напишет программу, которая вместе со своими входными данными будет меньше предоставленных им двоичных данных, но сможет восстановить их без ошибок. [24] Похожий вызов с вознаграждением в 5000 долларов был объявлен Майком Голдманом. [25]

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

Ссылки

  1. ^ "Unit 4 Lab 4: Data Representation and Compression, Page 6". bjc.edc.org . Получено 9 апреля 2022 г. .
  2. ↑ Прайс, Энди (3 марта 2022 г.). «Потоковая передача без потерь — будущее аудио высокого разрешения». Audio Media International .
  3. ^ ab Unser, M.; Blu, T. (2003). "Математические свойства вейвлет-фильтров JPEG2000" (PDF) . IEEE Transactions on Image Processing . 12 (9): 1080–1090. Bibcode :2003ITIP...12.1080U. doi :10.1109/TIP.2003.812329. PMID  18237979. S2CID  2765169. Архивировано из оригинала (PDF) 13 октября 2019 г.
  4. ^ "LZW Patent Information". О Unisys . Unisys. Архивировано из оригинала 2 июня 2009 г.
  5. ^ Салливан, Гэри (8–12 декабря 2003 г.). «Общие характеристики и соображения по проектированию для временного поддиапазонного видеокодирования». ITU-T . Группа экспертов по видеокодированию . Получено 13 сентября 2019 г. .
  6. ^ Бовик, Алан С. (2009). Основное руководство по обработке видео. Academic Press . стр. 355. ISBN 9780080922508.
  7. ^ Ахмед, Насир ; Мандьям, Гиридхар Д.; Маготра, Нирадж (17 апреля 1995 г.). Родригес, Артуро А.; Сафранек, Роберт Дж.; Делп, Эдвард Дж. (ред.). «Схема на основе DCT для сжатия изображений без потерь». Цифровое видеосжатие: алгоритмы и технологии 1995 г. 2419 г. Международное общество оптики и фотоники: 474–478. Bibcode : 1995SPIE.2419..474M. doi : 10.1117/12.206386. S2CID  13894279.
  8. ^ Комацу, К.; Сезаки, Каору (1998). «Обратимое дискретное косинусное преобразование». Труды Международной конференции IEEE 1998 года по акустике, речи и обработке сигналов, ICASSP '98 (Cat. No.98CH36181) . Том 3. С. 1769–1772, том 3. doi :10.1109/ICASSP.1998.681802. ISBN 0-7803-4428-6. S2CID  17045923.
  9. ^ Альфред Дж. Менезес; Пол К. ван Ооршот; Скотт А. Ванстоун (16 октября 1996 г.). Справочник по прикладной криптографии. CRC Press. ISBN 978-1-4398-2191-6.
  10. ^ Чанда, П.; Элхайк, Э.; Бадер, Дж. С. (2012). «HapZipper: совместное использование популяций HapMap стало проще». Nucleic Acids Res . 40 (20): 1–7. doi :10.1093/nar/gks709. PMC 3488212. PMID  22844100 . 
  11. ^ Пратас, Д.; Пинхо, А.Дж.; Феррейра, П.Дж.С.Г. (2016). «Эффективное сжатие геномных последовательностей». Конференция по сжатию данных (PDF) . Сноуберд, Юта.{{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
  12. ^ Мэтт Махони (2010). «Объяснение сжатия данных» (PDF) . стр. 3–5.
  13. ^ "Тест сжатия больших текстов". mattmahoney.net .
  14. ^ "Универсальный тест сжатия". mattmahoney.net .
  15. ^ "Summary". 1 сентября 2016 г. Архивировано из оригинала 1 сентября 2016 г.
  16. ^ "Инструмент анализа сжатия". Бесплатные инструменты . Noemax Technologies.
  17. ^ Саюд 2002, стр. 41.
  18. ^ ab Bell, Tim (28 сентября – 1 октября 2015 г.). «Удивительная компьютерная наука». 8-я международная конференция по информатике в школах: ситуация, эволюция и перспективы . Lecture Notes in Computer Science. Vol. 9378. Springer . pp. 1–11. doi :10.1007/978-3-319-25396-1_1. ISBN 978-3-319-25396-1. S2CID  26313283.См. в частности стр. 8–9.
  19. ^ "Сжатие без потерь - обзор | Темы ScienceDirect". www.sciencedirect.com . Получено 30 октября 2022 г. .
  20. ^ Саюд 2002, стр. 38.
  21. ^ Ли, Мин; Витаньи, Пол (1993). Введение в колмогоровскую сложность и ее приложения. Нью-Йорк: Спрингер. п. 102. ИСБН 0-387-94053-7Теорема 2.6 Функция не является частично рекурсивной.
  22. ^ Джоши, Марк С. (18 марта 2015 г.). «Принцип Пигеонхола». Proof Patterns . Springer . стр. 21. doi :10.1007/978-3-319-16250-8_3. ISBN 978-3-319-16250-8. S2CID  116983697 . Получено 24 августа 2021 г. .
  23. ^ "Спецификация формата файла .ZIP". PKWARE, Inc. глава V, раздел J.
  24. ↑ Нельсон, Марк (20 июня 2006 г.). «Повторный взгляд на задачу миллиона случайных цифр».
  25. ^ Крейг, Патрик. "The $5000 Compression Challenge" . Получено 8 июня 2009 г.

Дальнейшее чтение

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