Беспотерьное сжатие данных и методы восстановления исходной информации.

Введение

Подход сжатия данных, позволяющий идеальную реконструкцию исходных данных.

Сжатие без потерь – это класс сжатия данных, позволяющий полностью восстановить исходные данные из сжатых без какой-либо потери информации. Сжатие без потерь возможно, поскольку большинство реальных данных демонстрируют статистическую избыточность. В отличие от него, сжатие с потерями позволяет восстановить лишь приближение исходных данных, хотя обычно с существенно более высокой степенью сжатия (и, следовательно, меньшим размером файлов). В силу принципа Дирихле, ни один алгоритм сжатия без потерь не может уменьшить размер всех возможных данных: некоторые данные увеличатся как минимум на один символ или байт. Алгоритмы сжатия обычно эффективны для документов, читаемых человеком и машиной, и не могут уменьшить размер случайных данных, не содержащих избыточности. Существуют различные алгоритмы, разработанные с учетом конкретного типа входных данных или определенных предположений о том, какие виды избыточности могут содержаться в несжатых данных. Сжатие без потерь используется во многих приложениях. Например, оно применяется в формате ZIP-файлов и в утилите GNU gzip. Оно также часто используется как компонент в технологиях сжатия с потерями (например, предварительная обработка стереоканалов "mid/side" без потерь в кодировщиках MP3 и других аудиокодировщиках с потерями). Сжатие без потерь используется в тех случаях, когда важно, чтобы исходные и распакованные данные были идентичны, или когда отклонения от исходных данных недопустимы. Типичные примеры – исполняемые программы, текстовые документы и исходный код. Некоторые форматы файлов изображений, такие как PNG или GIF, используют только сжатие без потерь, в то время как другие, такие как TIFF и MNG, могут использовать методы с потерями или без потерь. Аудиоформаты без потерь чаще всего используются для архивирования или производства, в то время как более компактные аудиофайлы с потерями обычно применяются на портативных устройствах и в других случаях, когда объем памяти ограничен или точное воспроизведение аудио не требуется.

Техника

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

Мультимедиа

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

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

Многие из этих методов реализованы в открытых и проприетарных инструментах, особенно LZW и его вариантах. Некоторые алгоритмы запатентованы в Соединенных Штатах и других странах, и их законное использование требует лицензирования у патентообладателя. Из-за патентов на определенные виды сжатия LZW, и в частности лицензионной политики компании Unisys, которую многие разработчики считали злоупотреблением, некоторые сторонники открытого исходного кода призывали избегать использования формата обмена графическими файлами (GIF) для сжатия статических изображений в пользу портативной сетевой графики (PNG), которая сочетает алгоритм дефляции на основе LZ77 с набором фильтров предсказания, специфичных для области применения. Однако патенты на LZW истекли 20 июня 2003 года. Многие методы сжатия без потерь, используемые для текста, также достаточно хорошо работают с индексированными изображениями, но существуют и другие методы, которые не подходят для обычного текста, но полезны для некоторых изображений (особенно простых растровых изображений), а также методы, использующие специфические характеристики изображений (например, часто встречающееся явление смежных 2D областей с близкими тонами и тот факт, что в цветных изображениях обычно преобладает ограниченный диапазон цветов из тех, которые можно представить в цветовом пространстве). Как упоминалось ранее, сжатие звука без потерь – это довольно специализированная область. Алгоритмы сжатия звука без потерь могут использовать повторяющиеся закономерности, обусловленные волнообразной природой звука, по сути, применяя авторегрессионные модели для предсказания "следующего" значения и кодирования (желательно небольшой) разницы между ожидаемым и фактическим значением. Если разница между предсказанным и фактическим значением (так называемая ошибка) имеет тенденцию быть небольшой, то определенные значения разницы (например, 0, +1, −1 и т. д.) становятся очень частыми, что можно использовать, кодируя их небольшим количеством выходных битов. Иногда полезно сжимать только разницу между двумя версиями файла (или, в случае сжатия видео, между последовательными кадрами в последовательности). Это называется дельта-кодированием (от греческой буквы Δ, обозначающей разницу в математике), но этот термин обычно используется только тогда, когда обе версии имеют смысл вне процессов сжатия и декомпрессии. Например, процесс сжатия ошибки в вышеупомянутой схеме сжатия звука без потерь можно описать как дельта-кодирование от аппроксимированной звуковой волны к исходной звуковой волне, однако аппроксимированная версия звуковой волны не имеет смысла в каком-либо другом контексте.

Many of these methods are implemented in open source and proprietary tools, particularly LZW and its variants. Some algorithms are patented in the United States and other countries and their legal usage requires licensing by the patent holder. Because of patents on certain kinds of LZW compression, and in particular licensing practices by patent holder Unisys that many developers considered abusive, some open source proponents encouraged people to avoid using the Graphics Interchange Format (GIF) for compressing still image files in favor of Portable Network Graphics (PNG), which combines the LZ77 based deflate algorithm with a selection of domain specific prediction filters. However, the patents on LZW expired on June 20, 2003. Many of the lossless compression techniques used for text also work reasonably well for indexed images, but there are other techniques that do not work for typical text that are useful for some images (particularly simple bitmaps), and other techniques that take advantage of the specific characteristics of images (such as the common phenomenon of contiguous 2 D areas of similar tones, and the fact that color images usually have a preponderance of a limited range of colors out of those representable in the color space). As mentioned previously, lossless sound compression is a somewhat specialized area. Lossless sound compression algorithms can take advantage of the repeating patterns shown by the wave like nature of the essentially using autoregressive models to predict the "next" value and encoding the (hopefully small) difference between the expected value and the actual data. If the difference between the predicted and the actual data (called the error) tends to be small, then certain difference values (like 0, +1, −1 etc. on sample values) become very frequent, which can be exploited by encoding them in few output bits. It is sometimes beneficial to compress only the differences between two versions of a file (or, in video compression, of successive images within a sequence). This is called delta encoding (from the Greek letter Δ, which in mathematics, denotes a difference), but the term is typically only used if both versions are meaningful outside compression and decompression. For example, while the process of compressing the error in the above mentioned lossless audio compression scheme could be described as delta encoding from the approximated sound wave to the original sound wave, the approximated version of the sound wave is not meaningful in any other context.

Методы

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

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

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

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

Генетические алгоритмы сжатия (не путать с генетическими алгоритмами) – это новейшее поколение алгоритмов сжатия без потерь, которые сжимают данные (обычно последовательности нуклеотидов), используя как традиционные алгоритмы сжатия, так и специализированные алгоритмы, адаптированные к генетическим данным. В 2012 году группа ученых из Университета Джона Хопкинса опубликовала первый алгоритм генетического сжатия, не требующий для работы внешних генетических баз данных. HAPZIPPER был разработан для данных HapMap и обеспечивает сжатие более чем в 20 раз (сокращение размера файла на 95%), что на 2–4 раза эффективнее и быстрее, чем ведущие универсальные программы сжатия. Алгоритмы сжатия геномных последовательностей, также известные как компрессоры последовательностей ДНК, используют особенности последовательностей ДНК, такие как инвертированные повторы. Наиболее эффективными компрессорами являются XM и GeCo. Для эукариот XM обеспечивает немного лучшее соотношение сжатия, однако для последовательностей размером более 100 МБ его вычислительные требования становятся непрактичными.

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

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

Ограничения

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

Предположим, что каждый файл представлен как строка битов произвольной длины. Предположим, что существует алгоритм сжатия, который преобразует каждый файл в выходной файл, не превышающий по длине исходный файл, и что хотя бы один файл будет сжат в выходной файл, который короче исходного. Пусть M – наименьшее число, такое что существует файл F длиной M битов, который сжимается до чего-то меньшего. Пусть N – длина (в битах) сжатой версии F.
Поскольку N < M, каждый файл длиной N сохраняет свой размер при сжатии. Существует 2N таких файлов. Вместе с F это составляет 2N+1 файлов, которые все сжимаются в один из 2N файлов длиной N.
Но 2N меньше, чем 2N+1, поэтому, согласно принципу Дирихле, должен существовать файл длиной N, который одновременно является результатом сжатия двух разных входных файлов. Этот файл нельзя будет надежно распаковать (какой из двух исходных файлов следует восстановить?), что противоречит предположению о том, что алгоритм был без потерь. Следовательно, мы должны заключить, что наша первоначальная гипотеза (о том, что функция сжатия не увеличивает размер файла) обязательно неверна. Большинство практических алгоритмов сжатия предоставляют механизм "отмены", который может отключить обычное кодирование для файлов, которые станут длиннее при кодировании. Теоретически, для информирования декодера об отключении обычного кодирования для всего входного потока требуется всего один дополнительный бит; однако большинство алгоритмов кодирования используют для этой цели как минимум один полный байт (и обычно больше одного). Например, сжатые файлы Deflate никогда не должны увеличиваться более чем на 5 байт на каждые 65 535 байт входных данных. Фактически, если рассматривать файлы длиной N, и все файлы равновероятны, то для любого сжатия без потерь, уменьшающего размер какого-либо файла, ожидаемая длина сжатого файла (в среднем по всем возможным файлам длиной N) должна быть больше N. Таким образом, если мы ничего не знаем о свойствах сжимаемых данных, то лучше вообще не сжимать их. Алгоритм сжатия без потерь полезен только тогда, когда определенные типы файлов сжимаются с большей вероятностью, чем другие; тогда алгоритм можно разработать для лучшего сжатия этих типов данных. Таким образом, главный вывод из этого рассуждения заключается не в том, что можно понести большие потери, а лишь в том, что нельзя всегда выиграть. Выбор алгоритма всегда подразумевает неявный выбор подмножества всех файлов, которые станут полезно короче. Это теоретическое обоснование необходимости различных алгоритмов сжатия для разных типов файлов: не существует алгоритма, который был бы хорош для всех типов данных. "Секрет", позволяющий алгоритмам сжатия без потерь, используемым для данных, для которых они были разработаны, последовательно сжимать такие файлы в более короткую форму, заключается в том, что файлы, для которых предназначены алгоритмы, имеют некоторую форму легко моделируемой избыточности, которую алгоритм предназначен для удаления, и, следовательно, принадлежат к подмножеству файлов, которые этот алгоритм может сделать короче, в то время как другие файлы не будут сжаты или даже увеличатся в размере. Алгоритмы обычно тщательно настроены на определенный тип файла: например, программы сжатия аудио без потерь плохо работают с текстовыми файлами и наоборот. В частности, файлы случайных данных не могут быть последовательно сжаты каким-либо возможным алгоритмом сжатия данных без потерь; этот результат, на самом деле, используется для определения понятия случайности в сложности Колмогорова. Доказать невозможность создания алгоритма, который может сжимать любые данные без потерь. Хотя на протяжении многих лет поступало много заявлений о том, что компании достигли "идеального сжатия", когда произвольное число N случайных битов всегда можно сжать до N-1 битов, от таких заявлений можно безопасно отказаться, даже не вдаваясь в подробности предполагаемой схемы сжатия. Такой алгоритм противоречит фундаментальным законам математики, поскольку, если бы он существовал, его можно было бы многократно применять для без потерь уменьшения любого файла до длины 1. Не существует алгоритма для определения, является ли файл несжимаемым в смысле сложности Колмогорова. Следовательно, возможно, что любой конкретный файл, даже если он кажется случайным, может быть значительно сжат, включая размер декомпрессора. Примером являются цифры математической константы пи, которые кажутся случайными, но могут быть сгенерированы очень короткой программой. Однако, хотя нельзя определить, является ли конкретный файл несжимаемым, простое утверждение о несжимаемых строках показывает, что более 99% файлов любой заданной длины не могут быть сжаты более чем на один байт (включая размер декомпрессора).

Assume that each file is represented as a string of bits of some arbitrary length. Suppose that there is a compression algorithm that transforms every file into an output file that is no longer than the original file, and that at least one file will be compressed into an output file that is shorter than the original file. Let M be the least number such that there is a file F with length M bits that compresses to something shorter. Let N be the length (in bits) of the compressed version of F.
Because N<M, every file of length N keeps its size during compression. There are 2N such files possible. Together with F, this makes 2N+1 files that all compress into one of the 2N files of length N.
But 2N is smaller than 2N+1, so by the pigeonhole principle there must be some file of length N that is simultaneously the output of the compression function on two different inputs. That file cannot be decompressed reliably (which of the two originals should that yield? ), which contradicts the assumption that the algorithm was lossless. We must therefore conclude that our original hypothesis (that the compression function makes no file longer) is necessarily untrue. Most practical compression algorithms provide an "escape" facility that can turn off the normal coding for files that would become longer by being encoded. In theory, only a single additional bit is required to tell the decoder that the normal coding has been turned off for the entire input; however, most encoding algorithms use at least one full byte (and typically more than one) for this purpose. For example, deflate compressed files never need to grow by more than 5 bytes per 65,535 bytes of input. In fact, if we consider files of length N, if all files were equally probable, then for any lossless compression that reduces the size of some file, the expected length of a compressed file (averaged over all possible files of length N) must necessarily be greater than N. So if we know nothing about the properties of the data we are compressing, we might as well not compress it at all. A lossless compression algorithm is useful only when we are more likely to compress certain types of files than others; then the algorithm could be designed to compress those types of data better. Thus, the main lesson from the argument is not that one risks big losses, but merely that one cannot always win. To choose an algorithm always means implicitly to select a subset of all files that will become usefully shorter. This is the theoretical reason why we need to have different compression algorithms for different kinds of files: there cannot be any algorithm that is good for all kinds of data. The "trick" that allows lossless compression algorithms, used on the type of data they were designed for, to consistently compress such files to a shorter form is that the files the algorithms are designed to act on all have some form of easily modeled redundancy that the algorithm is designed to remove, and thus belong to the subset of files that that algorithm can make shorter, whereas other files would not get compressed or even get bigger. Algorithms are generally quite specifically tuned to a particular type of file: for example, lossless audio compression programs do not work well on text files, and vice versa. In particular, files of random data cannot be consistently compressed by any conceivable lossless data compression algorithm; indeed, this result is used to define the concept of randomness in Kolmogorov complexity. It is provably impossible to create an algorithm that can losslessly compress any data. While there have been many claims through the years of companies achieving "perfect compression" where an arbitrary number N of random bits can always be compressed to N − 1 bits, these kinds of claims can be safely discarded without even looking at any further details regarding the purported compression scheme. Such an algorithm contradicts fundamental laws of mathematics because, if it existed, it could be applied repeatedly to losslessly reduce any file to length 1. that there is no algorithm to determine whether a file is incompressible in the sense of Kolmogorov complexity. Hence it is possible that any particular file, even if it appears random, may be significantly compressed, even including the size of the decompressor. An example is the digits of the mathematical constant pi, which appear random but can be generated by a very small program. However, even though it cannot be determined whether a particular file is incompressible, a simple theorem about incompressible strings shows that over 99% of files of any given length cannot be compressed by more than one byte (including the size of the decompressor).

Математическая подготовка

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

Применение в теории реального сжатия

Разработчики реальных алгоритмов сжатия признают, что потоки с высокой информационной энтропией не поддаются сжатию и, соответственно, включают средства для обнаружения и обработки этой ситуации. Очевидный способ обнаружения – применение "сырого" алгоритма сжатия и проверка, меньше ли его выходной поток, чем входной. Иногда обнаружение выполняется с помощью эвристик; например, приложение для сжатия может считать файлы с именами, заканчивающимися на ".zip", ".arj" или ".lha", несжимаемыми без более сложного анализа. Распространенный способ обработки такой ситуации – дословное копирование входных данных или несжимаемых их частей в выходной поток, минимизируя накладные расходы на сжатие. Например, формат данных zip определяет "метод сжатия" "Stored" (хранение) для входных файлов, которые были скопированы в архив без изменений.

"Проблема миллиона случайных цифр"

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