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

Ответ 1

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

Ответ 2

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

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

$ gzip 0.txt
$ wc -c 0.txt.gz
1010 0.txt.gz

$ mv 0.txt.gz 0.txt
$ gzip 0.txt
$ wc -c 0.txt.gz
75 0.txt.gz

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

Ответ 3

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

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

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

Ответ 4

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

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

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

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

Ответ 5

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

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

Ответ 6

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

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

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

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

Ответ 7

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

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

Ответ 8

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

Ответ 9

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

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

1001 0011 1110 0100 0011 1001

Я использую созданный компрессор для tokenize посредством nybble (4 бит) данных как таковых:

если 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

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

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

Ответ 10

Проблема сжатия без потерь в основном, как эта информация может быть выражена более лаконично? Например, вы могли заметить, что в предыдущем тексте символ "e" чаще всего сопровождается символом spacE и substitutEan для этого шаблона. Точно так же пробел, за которым следует "t", мог бы быть заменен другой, необычной последовательностью иThEsequencEofTwo "s: es мог бы аналогичным образом bEshortened. Когда UrunOutOf commN sequenceTo замените, Ucannot продолжите любую работу (или Umay haveTo switchToAdifferent стратегия замещения шаблонов).