Почему данные могут быть сжаты только один раз?

Question

Таким образом, процесс сжатия берет кусок двоичных данных A и выводит меньший кусок двоичных данных B. Какие характеристики B делают невозможным повторение этого процесса?

Answer 1

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

Answer 2

Это неправда, что данные, которые уже сжаты, не могут быть сжаты снова.Если вы возьмете файл, состоящий из 1 миллиона нулей, и сожмете его, используя gzip , результирующий сжатый файл будет иметь размер 1010 байт.Если вы снова сжимаете сжатый файл, он дополнительно уменьшается до 75 байт.

$ python
>>> f = open('0.txt', 'w')
>>> f.write('0'*1000000)
>>> f.close()
>>>
$ wc -c 0.txt
<b>1000000</b> 0.txt

$ gzip 0.txt
$ wc -c 0.txt.gz
<b>1010</b> 0.txt.gz

$ mv 0.txt.gz 0.txt
$ gzip 0.txt
$ wc -c 0.txt.gz
<b>75</b> 0.txt.gz

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

Answer 3

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

Более простой ответ: предположим, что вы можете сжимать снова и снова, скажем, с коэффициентом 10 каждый раз. Вы можете сжать Википедию до гигабайта, затем до 100 МБ, затем до 10 МБ ... сделайте это 9 раз, и вы получите один байт. Если бы вся информация в Википедии могла быть сжата до одного байта, людям не нужно было бы ее писать, они могли бы просто расширить один из 256 возможных байтов, одним из них было бы содержимое Википедии:)

Немного более разумный ответ: текст избыточен : в этих байтах есть информация, которая может быть выражена немного более плотно. В статье в Википедии упоминается тот факт, что, например, за «q» почти всегда следует «u». «Е» встречается чаще, чем «Т». И так далее. Точно так же в программе часто 0 встречается чаще, чем любое другое число. Эту последовательность можно использовать и «выдавливать». Но как только вы сделали это один раз, первоначальная избыточность в основном исчезла. В сжатом файле почти нет «потерянных битов».

Answer 4

Во-первых, это относится только к сжатию без потерь.Сжатие с потерями (например, JPG), теоретически может применяться снова и снова.Конечно, качество сжатого материала каждый раз падает.

Для сжатия без потерь мы можем думать о сжатии как о процедуре, которая берет некоторые данные и преобразовывает их в другую форму (A-> B).Поскольку он без потерь, мы должны быть в состоянии взять B и перейти A <-B.Если мы проследим это, то это означает, что если мы возьмем каждую последовательность из 4 битов (16 шаблонов) и сжимаем их, мы должны получить 16 различных результатов.Это означает, что в среднем сжатие не выполнялось! </p>

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

Если сделать еще один шаг вперед, если мы неоднократно повторно сжимаем одно и то же сообщение, оно в среднем не изменит размер (опять же, это best кейс).

Answer 5

Возьмите лист бумаги и сложите его - вы сжали его на 50%. Теперь сделай это снова - и продолжай пытаться. Заметьте, как все сложнее и сложнее, и в какой-то момент вы должны остановиться?

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

Answer 6

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

Чтобы понять минимальный размер, не читая слишком много теории, придумайте вопрос с двумя возможными ответами: «Да» и «Нет». Наименьший, который вы можете получить, это один бит, где 0 = Нет и 1 = Да (или наоборот) , Даже это сделало кучу предположений (например, человек, получающий данные, понимает эту кодировку).

На более сложном уровне то же самое верно для всех других данных. В ситуации, когда у вас есть восемь возможных ответов, все одинаково вероятны (это важно), минимальный размер составляет три бита - наименьшее количество бит, чтобы предоставить вам восемь вариантов (000, 001, 010, 011, 100, 101, 110 , 111).

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

Answer 7

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

Большинство шаблоновпопасть в первое сжатие.Вы можете добиться дальнейшего сжатия после его сжатия, но ... осталось не так много шаблонов.

Answer 8

Для любого числа N существует 2 ^ (N + 1) -1 различных возможных входных файла длиной N бит или меньше. Если для каждого отдельного входного файла будет свой выходной файл, то для каждого возможного входного файла длиной k, который может быть уменьшен до некоторой более короткой длины, должен быть как минимум один более короткий файл, который становится длиннее.

Answer 9

Проблема сжатия без потерь в основном, как эта информация может быть выражена более кратко?Например, вы могли заметить, что в предыдущем тексте символ «e» чаще всего сопровождается необычным символом spacEand substitutEan для этого шаблона.Точно так же пробел, за которым следует буква «t», может быть заменен другой, необычной последовательностью, и поэтому «s» может также аналогичным образом сокращаться.Когда UrunOutOf последовательностей COMMN заменяет, Ucan не может продолжать какую-либо дальнейшую (или может иметь стратегию замены шаблона switchToAdifferent).

Answer 10

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

Подумайте об этом, вот ваши данные:

1001 0011 1110 0100 0011 1001

Я использую готовый компрессор, чтобы разбить данные на четыре части как nybble:

если 1001, сожмите как 101, поскольку ниббл не начинается с 101, а 1001 встречается дважды если 0011, сожмите как 110, поскольку ниббл не начинается с 110, а 0011 встречается дважды

После сжатия:

101 110 1110 0100 110 101 или же 1011 1011 1001 0011 0101

На самом деле это не сработает в реальном мире, но, как вы можете себе представить, вы можете сжать это снова, поскольку это все еще двоичные данные.

Следующее сжатие делает это:

если 1011, сжимать как 111

после сжатия: 111 111 1001 0011 0101 или же 1111 1110 0100 1101 01

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

Опять же, это не настоящий компрессор, а простой способ понять концепцию.