Эффективно ли многократно применять различные алгоритмы сжатия к одному файлу?

Question

Я знаю, что невозможно сжимать файл бесконечно, повторно применяя один алгоритм.

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

Answer 1

Номер
Устройство, которое мы используем для «веса» файла, это байт.
Байт всего несколько экземпляров более фундаментального блока бит.

Хотя слово «бит» происходит от «двоичной цифры», на самом деле это единица измерения, так же, как метров, джоулех, секунд и так далее.
Битовая оценка минимальное количество информации, измеряемой, точно так же как e - наименьший плата.
Когда мы говорим, что файл имеет размер 2 MiB, мы говорим, что есть 2 ^{20 + 3} = 8.388.608 бит информации.

Теперь, если вы хотите идти в гору высотой 20 м и вы вес 50 кг вам нужно по крайней мереE = MGH = 50 · 9,81 · 20 = 9810 Дж
Независимо от того, что ты сделайте, вам нужно не менее, что энергия или вы туда не доберетесь .
Также вы можете иметь больше энергия, 9810 J - это минимум.

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

Таким образом, мы можем интуитивно удалить избыточность файла, уменьшив его размер до тех пор, пока мы не достигнем минимума X.
Сохранение удаления битов после достижения минимума означало удаление полезной информации, предотвращающей восстановление исходного файла (читай: разархивировано).
Это фактически сделано с помощью алгоритмов lossy, например MP3, JPEG и т. Д.

Эта интуиция, что струны не могут быть бесконечно сжаты, легко доказать.
Мы следуем подходу главы 6.4 от Введение в теорию вычислений by Sipser.

Мы присваиваем вес в строку ы таким образом: мы рассмотрим все алгоритмы , что при обработке, новый, строка Ма выход s.
Мы кодировать каждые и Ма в виде строки, и мы устанавливаем K (ы) как длина кратчайшего такой строки.
К (ы) называется минимальный дескриптор из ами и представляют собой наименьшую информацию, необходимую для генерации с.

Если К (ы) меньше, чем длина ы, чем с Говорят сжимаемый.
Теперь мы покажем, что есть несжимаемые строки.

Предполагается, что s имеет длину n. Есть 2 ⁿ возможно такие строки.
Если s сжимаемо, то он имеет минимальный дескриптор длины не более n-1.
Есть 1 + 2 + 4 + 8 + ... + 2 ^n-1 = 2 ⁿ - 1 таких дескрипторов.
Поскольку каждый дескриптор определяет строку однозначно и существует меньше дескрипторов, чем строки длиной n, некоторая строка длины n несжимаема.
По произвольно n несжимаемых нитей любой длины существует.

Итак, если мы продолжаем сжимать, мы в конечном итоге достигаем несжимаемого файла. На практике хороший алгоритм сжатия должен удалить большую часть избыточности на первом этапе без добавления значительного объема информации.
Вот почему zping jpeg, уже сжатый формат, не дает того же результата, что и zipping текстового файла. Также объясните, почему зашифрованные файлы, которые кажутся случайными, поэтому без какой-либо избыточности не могут быть сжаты очень хорошо.

---

Мы имеем дело только с простой ньютоновской физикой здесь.

Answer 2

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

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

Проверьте, пожалуйста, here.

Answer 3

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

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

Алгоритм compress00:

Если первые два бита в файле, 00 заменить те, два бита с одним битом 0 - в этом случае файл 1 немного короче. В противном случае добавьте 1 к файлу - в этом случае файл будет 1 бит дольше.

Этот алгоритм легко обратим (т. Е. Выход может быть однозначно декомпрессирован), и он либо сокращает, либо удлиняет файл на 1 бит. Представьте себе семейство из 4-х компрессоров: compress00, compress01, compress10, compress11, которые имеют одинаковое поведение, за исключением того, что, например, compress01 сокращает файл, если он начинается с 01 и удлиняет его в противном случае и т. Д. Для других компрессоров.

Заметим теперь, что каждый файл, по крайней мере, два бита либо начинается с 00, 01, 10, или 11 - так на каждый этап в вашем процессе повторного сжатия вы можете выбрать алгоритм, который сжимает файл, 1 бит. Повторное применение этого процесса уменьшит файл до одного бита (и вы можете определить некоторое дополнительное поведение для 1-битных файлов, чтобы получить до 0 бит).

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