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

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

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

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

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

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

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

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

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

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

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

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

1001 0011 1110 0100 0011 1001

Я буду использовать выдуманный компрессор для токенизации по ниблам (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

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

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

Неверно, что уже сжатые данные нельзя снова сжать. Если взять файл, состоящий из 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

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

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

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

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

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

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

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

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

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