Как победить gzip (или другое сжатие без потерь)

Question

По принципу голубя, каждый алгоритм сжатия без потерь может быть «побежден», т. Е. Для некоторых входов он производит выходные данные, которые длиннее входных. Можно ли явно создать файл, который при подаче, например, gzip или другая программа сжатия без потерь, приведет к (намного) большему выходу? (или, что еще лучше, файл, который раздувается до бесконечности при последующих сжатиях?)

Answer 1

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

touch file
gzip file -c > file.1
...
gzip file.9 -c > file.10

И получил:

  0 bytes: file
 25 bytes: file.1
 45 bytes: file.2
 73 bytes: file.3
103 bytes: file.4
122 bytes: file.5
152 bytes: file.6
175 bytes: file.7
205 bytes: file.8
232 bytes: file.9
262 bytes: file.10

Вот24 380 файлов графически (это действительно на самом деле удивляет меня):

альтернативный текст http://research.engineering.wustl.edu/~schultzm/images/filesize.png

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

Если вы хотите воспроизвести, вот сценарий bash для генерации файлов:

#!/bin/bash

touch file.0

for ((i=0; i < 20000; i++)); do
    gzip file.$i -c > file.$(($i+1))
done

wc -c file.* | awk '{print $2 "\t" $1}' | sed 's/file.//' | sort -n > filesizes.txt

Полученный файл filesizes.txt представляет собой отсортированный по табуляции файл для вашей любимой графической утилиты.(Вам придется вручную удалить поле «итого» или удалить его из сценария.)

Answer 2

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

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

Для упаковщиков, которые включают имя файла (например, rar, zip, tar), вы, конечно, можете просто сделать имя файла действительно long: -)

Answer 3

Все эти алгоритмы сжатия ищут избыточные данные.Если в вашем файле нет или очень мало избыточности (например, последовательность abac…az, bcbd…bz, cdce…cz и т. Д.), Очень вероятно, что «дефлированный» вывод - это скорее инфляция.

Answer 4

Текстовый файл с 1 байтом в нем (например, один символ, такой как 'A') хранится в 1 байте на диске, но winrar сокращает его до 94 байтов и zip до 141 байта.

Я знаюЭто своего рода обманчивый ответ, но он работает.Я думаю, что это будет наибольшая разница в процентах между исходным размером и «сжатым» размером, который вы увидите.

Взгляните на формулу для архивирования, они достаточно просты, и чтобы сделать «сжатым»файл больше исходного, самый простой способ - избежать повторяющихся данных.

Answer 5

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

echo a > file.txt

Сжатие файла размером 2 байта, полученного из сжатого файла размером 31 байт!