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

Сжатие без потерь — это класс сжатия данных , который позволяет идеально восстановить исходные данные из сжатых данных без потери информации . Сжатие без потерь возможно, поскольку большинство реальных данных демонстрируют статистическую избыточность . ^[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 и т. д. в выборочных значениях) становятся очень частыми, что можно использовать путем их кодирования. в нескольких выходных битах.

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

Методы

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

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

Общее назначение

ANS — энтропийное кодирование, используемое LZFSE и Zstandard.
Арифметическое кодирование – Энтропийное кодирование
Обратимое преобразование Берроуза – Уиллера для повышения сжимаемости текстовых данных, используемое bzip2.
Кодирование Хаффмана — энтропийное кодирование, хорошо сочетается с другими алгоритмами.
Сжатие Лемпеля-Зива (LZ77 и LZ78) - алгоритм на основе словаря, который составляет основу для многих других алгоритмов.
- Алгоритм цепочки Лемпеля-Зива-Маркова (LZMA) - очень высокая степень сжатия, используется 7zip и xz.
- Лемпель-Зив-Сторер-Шимански (LZSS) - используется WinRAR в тандеме с кодированием Хаффмана.
  - Deflate — сочетает в себе сжатие LZ77 с кодированием Хаффмана, используемое ZIP , gzip и PNG . изображениями
- Лемпель-Зив-Велч (LZW) - используется изображениями GIF и Unix. compress полезность
Прогнозирование по частичному совпадению (PPM) — оптимизировано для сжатия обычного текста.
Кодирование длин серий (RLE). Простая схема, обеспечивающая хорошее сжатие данных, содержащих множество серий одного и того же значения.

Аудио

Акустическое кодирование с адаптивным преобразованием (ATRAC)
Apple Lossless (ALAC — аудиокодек Apple Lossless)
Кодирование звука без потерь (также известное как MPEG-4 ALS)
Прямая потоковая передача (DST)
Dolby TrueHD
DTS-HD Мастер Аудио
Бесплатный аудиокодек без потерь (FLAC)
Меридианная упаковка без потерь (MLP)
Аудио Обезьяны (Аудио Обезьяны)
MPEG-4 SLS (также известный как HD-AAC)
ОптимФРОГ
Исходное качество звука (OSQ)
RealPlayer (RealAudio без потерь)
Укоротить (SHN)
ТТА (настоящий звук без потерь)
WavPack (WavPack без потерь)
WMA без потерь (Windows Media без потерь)

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

AVIF – формат файла изображения AV1
FLIF – бесплатный формат изображений без потерь
HEIF — высокоэффективный формат файла изображения (сжатие без потерь или с потерями, с использованием HEVC )
ILBM - (сжатие RLE без потерь изображений Amiga IFF )
JBIG2 – (сжатие черно-белых изображений без потерь или с потерями)
JPEG 2000 - (включая метод сжатия без потерь с помощью Le Gall – Tabatabai 5/3 ^[4]^[5]^[6] обратимое целочисленное вейвлет-преобразование )
JPEG-LS – (стандарт сжатия без потерь/почти без потерь)
JPEG XL – (сжатие без потерь или с потерями)
JPEG XR — ранее WMPhoto и HD Photo , включает метод сжатия без потерь.
LDCT – дискретное косинусное преобразование без потерь ^[7]^[8]
PCX – ОБМЕН ИЗОБРАЖЕНИЯМИ
PDF – формат переносимых документов (сжатие без потерь или с потерями)
QOI – вполне нормальный формат изображения
PNG – переносимая сетевая графика
ТГА – Truevision ТГА
TIFF — формат файла изображения тега (сжатие без потерь или с потерями)
WebP – (сжатие изображений RGB и RGBA без потерь или с потерями)

3D-графика

OpenCTM – сжатие без потерь трехмерных треугольных сеток.

Видео

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

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

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

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

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

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

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

Самораспаковывающиеся исполняемые файлы содержат сжатое приложение и распаковщик. При выполнении декомпрессор прозрачно распаковывает и запускает исходное приложение. Особенно часто это используется при кодировании демо , где проводятся соревнования по демо со строгими ограничениями по размеру, вплоть до 1 КБ .Этот тип сжатия не ограничивается строго двоичными исполняемыми файлами, но также может применяться к сценариям, таким как JavaScript .

Тесты

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

Мэтт Махони в своем бесплатном буклете « Объяснение сжатия данных» за февраль 2010 года дополнительно перечисляет следующее: ^[12]

Корпус Калгари , основанный в 1987 году, больше не используется широко из-за его небольшого размера. Мэтт Махони поддерживал Calgary Compression Challenge, созданный и поддерживаемый с 21 мая 1996 года по 21 мая 2016 года Леонидом А. Брухисом.
Тест сжатия большого текста ^[13] и аналогичный Hutter Prize используют урезанный набор данных Wikipedia XML UTF-8 .
Общий тест сжатия, ^[14] поддерживаемый Мэттом Махони, тестирует сжатие данных, генерируемых случайными машинами Тьюринга .
Сами Рунсас (автор NanoZip) поддерживал рейтинги сжатия — эталонный тест, аналогичный тесту нескольких файлов с максимальным сжатием, но с минимальными требованиями к скорости. Он предлагал калькулятор, который позволял пользователю взвесить важность скорости и степени сжатия. Топовые программы сильно различались из-за требований к скорости. В январе 2010 года лучшей программой была NanoZip, за ней следовали FreeArc , CCM , flashzip и 7-Zip .
Тест Monster of Compression от Nania Francesco Antonio тестировал сжатие 1 ГБ общедоступных данных с ограничением по времени 40 минут. В декабре 2009 года лучшим архиватором был NanoZip 0.07a, а лучшим компрессором отдельных файлов — ccmx 1.30c.

Веб-сайт Compression Ratings опубликовал сводную диаграмму «границы» степени сжатия и времени. ^[15]

Инструмент анализа сжатия ^[16] — это приложение для Windows, которое позволяет конечным пользователям оценивать характеристики производительности потоковых реализаций LZF4, Deflate, ZLIB, GZIP, BZIP2 и LZMA, используя свои собственные данные. Он производит измерения и диаграммы, с помощью которых пользователи могут сравнить скорость сжатия, скорость распаковки и степень сжатия различных методов сжатия, а также изучить, как уровень сжатия, размер буфера и операции очистки влияют на результаты.

Ограничения

Алгоритмы сжатия данных без потерь не могут гарантировать сжатие всех наборов входных данных. Другими словами, для любого алгоритма сжатия данных без потерь будет существовать набор входных данных, который не уменьшается при обработке этим алгоритмом, а для любого алгоритма сжатия данных без потерь, который уменьшает хотя бы один файл, будет хотя бы один файл, который он увеличивает. Это легко доказать с помощью элементарной математики, используя аргумент подсчета, называемый принципом ячейки , следующим образом: ^[17]^[18]

Предположим, что каждый файл представлен как строка бит произвольной длины.
Предположим, что существует алгоритм сжатия, который преобразует каждый файл в выходной файл, длина которого не превышает исходный файл, и что по крайней мере один файл будет сжат в выходной файл, который короче исходного файла.
Пусть M — наименьшее число, такое, что существует файл F длиной M бит, который сжимается во что-то более короткое. Пусть N будет длиной (в битах) сжатой версии F .
Поскольку N < M , каждый файл длиной N сохраняет свой размер во время сжатия. Есть 2 ^Н такие файлы возможны. Вместе с F это составляет 2 ^Н+1 файлы, которые все сжимаются в один из двух ^Н длиной N. файлы
Но 2 ^Н меньше 2 ^Н+1, поэтому по принципу «ячейки» должен существовать некоторый файл длины N , который одновременно является результатом функции сжатия на двух разных входах. Этот файл невозможно надежно распаковать (какой из двух оригиналов это должно дать?), что противоречит предположению, что алгоритм работает без потерь.
Поэтому мы должны заключить, что наша первоначальная гипотеза (о том, что функция сжатия не увеличивает длину файла) обязательно неверна.

Большинство практических алгоритмов сжатия предоставляют возможность «экранирования», которая может отключить обычное кодирование для файлов, которые в результате кодирования станут длиннее. Теоретически требуется только один дополнительный бит, чтобы сообщить декодеру, что нормальное кодирование отключено для всего ввода; однако большинство алгоритмов кодирования используют для этой цели как минимум один полный байт (а обычно более одного). Например, сжатые файлы deflate никогда не должны увеличиваться более чем на 5 байт на каждые 65 535 байт входных данных.

В самом деле, если мы рассматриваем файлы длины N, если бы все файлы были равновероятными, то для любого сжатия без потерь, уменьшающего размер некоторого файла, ожидаемая длина сжатого файла (усредненная по всем возможным файлам длины N) обязательно должна быть больше Н. ^[19] Поэтому, если мы ничего не знаем о свойствах данных, которые сжимаем, мы можем вообще их не сжимать. Алгоритм сжатия без потерь полезен только тогда, когда мы с большей вероятностью сжимаем файлы определенных типов, чем другие; тогда алгоритм можно было бы разработать для лучшего сжатия этих типов данных.

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

«Хитрость», которая позволяет алгоритмам сжатия без потерь, используемым для типа данных, для которых они были разработаны, последовательно сжимать такие файлы до более короткой формы, заключается в том, что все файлы, для обработки которых предназначены алгоритмы, имеют некоторую форму легко моделируемой избыточности, которая алгоритм предназначен для удаления и, таким образом, принадлежит к подмножеству файлов, которые этот алгоритм может сделать короче, тогда как другие файлы не будут сжиматься или даже увеличиваться в размерах. Алгоритмы, как правило, весьма специфически настроены на определенный тип файла: например, программы сжатия звука без потерь плохо работают с текстовыми файлами, и наоборот.

В частности, файлы случайных данных не могут быть последовательно сжаты с помощью любого мыслимого алгоритма сжатия данных без потерь; действительно, этот результат используется для определения понятия случайности в колмогоровской сложности . ^[20]

Доказуемо невозможно создать алгоритм, который сможет сжимать любые данные без потерь. - 1 бит, было много заявлений, Несмотря на то, что за годы существования компаний, добивавшихся «идеального сжатия», когда произвольное число N случайных битов всегда можно сжать до N подобные утверждения можно смело отбросить, даже не рассматривая какие-либо дополнительные подробности относительно предполагаемая схема сжатия. Такой алгоритм противоречит фундаментальным законам математики, поскольку, если бы он существовал, его можно было бы применять неоднократно для уменьшения без потерь любого файла до длины 1. ^[18]

С другой стороны, также доказано ^[21] что не существует алгоритма определения несжимаемости файла в смысле колмогоровской сложности. Следовательно, вполне возможно, что любой конкретный файл, даже если он выглядит случайным, может быть значительно сжат, включая размер декомпрессора. Примером могут служить цифры математической константы «пи» , которые кажутся случайными, но могут быть сгенерированы очень маленькой программой. Однако, хотя невозможно определить, является ли конкретный файл несжимаемым, простая теорема о несжимаемых строках показывает, что более 99% файлов любой заданной длины не могут быть сжаты более чем на один байт (включая размер декомпрессора).

Математическая основа

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

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

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

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

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

См. также

Ссылки

^ «Блок 4, лабораторная работа 4: Представление и сжатие данных, страница 6» . bjc.edc.org . Проверено 9 апреля 2022 г.
^ Прайс, Энди (3 марта 2022 г.). «Потоковая передача без потерь – будущее аудио высокого разрешения» . Аудио Медиа Интернешнл .
^ «Патентная информация LZW» . О Юнисисе . Unisys. Архивировано из оригинала 2 июня 2009 года.
^ Салливан, Гэри (8–12 декабря 2003 г.). «Общие характеристики и соображения по проектированию временного поддиапазонного видеокодирования» . МСЭ-Т . Группа экспертов по видеокодированию . Проверено 13 сентября 2019 г.
^ Унсер, М.; Блу, Т. (2003). «Математические свойства вейвлет-фильтров JPEG2000» (PDF) . Транзакции IEEE при обработке изображений . 12 (9): 1080–1090. Бибкод : 2003ИТИП...12.1080У . дои : 10.1109/TIP.2003.812329 . ПМИД 18237979 . S2CID 2765169 . Архивировано из оригинала (PDF) 13 октября 2019 г.
^ Бовик, Алан С. (2009). Основное руководство по обработке видео . Академическая пресса . п. 355. ИСБН 9780080922508 .
^ Ахмед, Насир ; Мандьям, Гиридхар Д.; Маготра, Нирадж (17 апреля 1995 г.). Родригес, Артуро А.; Сафранек, Роберт Дж.; Дельп, Эдвард Дж. (ред.). «Схема сжатия изображений без потерь на основе DCT». Сжатие цифрового видео: алгоритмы и технологии 1995 . 2419 . Международное общество оптики и фотоники: 474–478. Бибкод : 1995SPIE.2419..474M . дои : 10.1117/12.206386 . S2CID 13894279 .
^ Комацу, К.; Сезаки, Каору (1998). «Обратимое дискретное косинусное преобразование» . Материалы Международной конференции IEEE по акустике, речи и обработке сигналов 1998 г., ICASSP '98 (Кат. № 98CH36181) . Том. 3. С. 1769–1772 т.3. дои : 10.1109/ICASSP.1998.681802 . ISBN 0-7803-4428-6 . S2CID 17045923 .
^ Альфред Дж. Менезес; Пол К. ван Оршот; Скотт А. Ванстон (16 октября 1996 г.). Справочник по прикладной криптографии . ЦРК Пресс. ISBN 978-1-4398-2191-6 .
^ Чанда, П.; Эльхайк, Э.; Бадер, Дж. С. (2012). «HapZipper: делиться популяциями HapMap стало проще» . Нуклеиновые кислоты Рез . 40 (20): 1–7. дои : 10.1093/nar/gks709 . ПМЦ 3488212 . ПМИД 22844100 .
^ Пратас, Д.; Пиньо, Эй Джей; Феррейра, PJSG (2016). «Эффективное сжатие геномных последовательностей». Конференция по сжатию данных (PDF) . Сноуберд, Юта. {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
^ Мэтт Махони (2010). «Описание сжатия данных» (PDF) . стр. 3–5.
^ «Бенчмарк сжатия большого текста» . mattmahoney.net .
^ «Общий тест сжатия» . mattmahoney.net .
^ "Краткое содержание" . 1 сентября 2016 г. Архивировано из оригинала 1 сентября 2016 г.
^ «Инструмент анализа сжатия» . Бесплатные инструменты . Ноэмакс Технологии.
^ Саюд 2002 , с. 41.
^ Перейти обратно: ^а ^б Белл, Тим (28 сентября – 1 октября 2015 г.). «Удивительная информатика». 8-я Международная конференция «Информатика в школе: ситуация, эволюция и перспективы» . Конспекты лекций по информатике. Том. 9378. Спрингер . стр. 1–11. дои : 10.1007/978-3-319-25396-1_1 . ISBN 978-3-319-25396-1 . S2CID 26313283 . См., в частности, стр. 8–9 .
^ «Сжатие без потерь — обзор | Темы ScienceDirect» . www.sciencedirect.com . Проверено 30 октября 2022 г.
^ Саюд 2002 , с. 38.
^ Ли, Мин; Витаньи, Пол (1993). Введение в колмогоровскую сложность и ее приложения . Нью-Йорк: Спрингер. п. 102. ИСБН 0-387-94053-7 . Теорема 2.6. Функция $C(x)$ не является частично рекурсивным.
^ Джоши, Марк С. (18 марта 2015 г.). «Принцип ячейки» . Образцы доказательств . Спрингер . п. 21. дои : 10.1007/978-3-319-16250-8_3 . ISBN 978-3-319-16250-8 . S2CID 116983697 . Проверено 24 августа 2021 г.
^ «Спецификация формата файла .ZIP» . PKWARE, Inc., глава V, раздел J.
^ Нельсон, Марк (20 июня 2006 г.). «Возвращение к задаче на миллион случайных цифр» .
^ Крейг, Патрик. «Вызов сжатия за 5000 долларов» . Проверено 8 июня 2009 г.

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

Саюд, Халид (27 октября 2017 г.). Введение в сжатие данных . Серия Моргана Кауфмана по мультимедийной информации и системам (5-е изд.). Морган Кауфманн . ISBN 978-0-12809474-7 . (790 страниц)
Саюд, Халид, изд. (18 декабря 2002 г.). Справочник по сжатию без потерь (коммуникации, сети и мультимедиа) (1-е изд.). Академическая пресса . ISBN 978-0-12390754-7 . (488 страниц)

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

«Формат сжатия LZF» . гитхаб . Проверено 17 октября 2017 г.
Фамдо, Нам. «Теория сжатия данных» . Сжатие данных . Архивировано из оригинала 8 мая 2016 года . Проверено 17 октября 2017 г.
«Сравнение без потерь» . База знаний Hydrogenaudio . 5 января 2015 г. Проверено 17 октября 2017 г.
«Аудиоформаты музыки без потерь и с потерями» . Бобулус Централ . 6 ноября 2003 года . Проверено 17 октября 2017 г.
«Бенчмарк сжатия изображений» . Архивировано из оригинала 10 февраля 2013 года. Обзор
- Патент США № 7,096,360. Архивировано 2 февраля 2017 года в Wayback Machine . «[a]n «Метод сжатия данных на основе частоты и времени», поддерживающий сжатие, шифрование, декомпрессию и дешифрование, а также сохранение многих двоичных цифр на частотах, где каждая частота представляет собой множество битов».

[1] «Блок 4, лабораторная работа 4: Представление и сжатие данных, страница 6» . bjc.edc.org . Проверено 9 апреля 2022 г.

[2] Прайс, Энди (3 марта 2022 г.). «Потоковая передача без потерь – будущее аудио высокого разрешения» . Аудио Медиа Интернешнл .

[3] «Патентная информация LZW» . О Юнисисе . Unisys. Архивировано из оригинала 2 июня 2009 года.

[4] Салливан, Гэри (8–12 декабря 2003 г.). «Общие характеристики и соображения по проектированию временного поддиапазонного видеокодирования» . МСЭ-Т . Группа экспертов по видеокодированию . Проверено 13 сентября 2019 г.

[Unser-5] Унсер, М.; Блу, Т. (2003). «Математические свойства вейвлет-фильтров JPEG2000» (PDF) . Транзакции IEEE при обработке изображений . 12 (9): 1080–1090. Бибкод : 2003ИТИП...12.1080У . дои : 10.1109/TIP.2003.812329 . ПМИД 18237979 . S2CID 2765169 . Архивировано из оригинала (PDF) 13 октября 2019 г.

[6] Бовик, Алан С. (2009). Основное руководство по обработке видео . Академическая пресса . п. 355. ИСБН 9780080922508 .

[7] Ахмед, Насир ; Мандьям, Гиридхар Д.; Маготра, Нирадж (17 апреля 1995 г.). Родригес, Артуро А.; Сафранек, Роберт Дж.; Дельп, Эдвард Дж. (ред.). «Схема сжатия изображений без потерь на основе DCT». Сжатие цифрового видео: алгоритмы и технологии 1995 . 2419 . Международное общество оптики и фотоники: 474–478. Бибкод : 1995SPIE.2419..474M . дои : 10.1117/12.206386 . S2CID 13894279 .

[8] Комацу, К.; Сезаки, Каору (1998). «Обратимое дискретное косинусное преобразование» . Материалы Международной конференции IEEE по акустике, речи и обработке сигналов 1998 г., ICASSP '98 (Кат. № 98CH36181) . Том. 3. С. 1769–1772 т.3. дои : 10.1109/ICASSP.1998.681802 . ISBN 0-7803-4428-6 . S2CID 17045923 .

[MenezesOV1996-9] Альфред Дж. Менезес; Пол К. ван Оршот; Скотт А. Ванстон (16 октября 1996 г.). Справочник по прикладной криптографии . ЦРК Пресс. ISBN 978-1-4398-2191-6 .

[10] Чанда, П.; Эльхайк, Э.; Бадер, Дж. С. (2012). «HapZipper: делиться популяциями HapMap стало проще» . Нуклеиновые кислоты Рез . 40 (20): 1–7. дои : 10.1093/nar/gks709 . ПМЦ 3488212 . ПМИД 22844100 .

[Pratas-11] Пратас, Д.; Пиньо, Эй Джей; Феррейра, PJSG (2016). «Эффективное сжатие геномных последовательностей». Конференция по сжатию данных (PDF) . Сноуберд, Юта. {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )

[12] Мэтт Махони (2010). «Описание сжатия данных» (PDF) . стр. 3–5.

[13] «Бенчмарк сжатия большого текста» . mattmahoney.net .

[14] «Общий тест сжатия» . mattmahoney.net .

[15] "Краткое содержание" . 1 сентября 2016 г. Архивировано из оригинала 1 сентября 2016 г.

[16] «Инструмент анализа сжатия» . Бесплатные инструменты . Ноэмакс Технологии.

[FOOTNOTESayood200241-17] Саюд 2002 , с. 41.

[ISSEP-2015-18] Перейти обратно: ^а ^б Белл, Тим (28 сентября – 1 октября 2015 г.). «Удивительная информатика». 8-я Международная конференция «Информатика в школе: ситуация, эволюция и перспективы» . Конспекты лекций по информатике. Том. 9378. Спрингер . стр. 1–11. дои : 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 г.

[FOOTNOTESayood200238-20] Саюд 2002 , с. 38.

[21] Ли, Мин; Витаньи, Пол (1993). Введение в колмогоровскую сложность и ее приложения . Нью-Йорк: Спрингер. п. 102. ИСБН 0-387-94053-7 . Теорема 2.6. Функция $C(x)$ не является частично рекурсивным.

[22] Джоши, Марк С. (18 марта 2015 г.). «Принцип ячейки» . Образцы доказательств . Спрингер . п. 21. дои : 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] Крейг, Патрик. «Вызов сжатия за 5000 долларов» . Проверено 8 июня 2009 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]