Какое лучшее сжатие файлов случайных двоичных данных, которые вы можете достичь?

Ответ 1

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

В качестве простого примера предположим, что вы хотите сохранить без потерь файл, в котором бит является случайным и независимым, но вместо 50% установленных битов всего 33%. Можно сжать такой файл, взяв каждую пару бит и записать "0", если оба бита были четкими, "10", если первый бит был установлен, а второй - "110", если второй был установлен, а первый не был, или "111", если оба бита установлены. Эффект будет заключаться в том, что каждая пара бит будет составлять один бит 44% времени, два бита 22% времени и три бита 33% времени. Хотя некоторые строки данных будут расти, другие сократятся; пары, которые сократились бы - если бы распределение вероятности было таким, как ожидалось, - больше, чем те, которые растут (4/9 файлов сократятся немного, 2/9 останутся неизменными, а 3/9 будут расти, поэтому пары будут средняя усадка на 1/9 бит, а файлы будут в среднем уменьшаться на 1/18 [так как 1/9 фигура была битами на пару]).

Обратите внимание, что если на битах фактически было 50% -ное распределение, тогда только 25% пар стали бы одним битом, 25% оставались бы двумя битами, а 50% стали бы тремя битами. Следовательно, 25% бит сократятся, а 50% вырастут, поэтому пары в среднем вырастут на 25%, а файлы вырастут на 12,5%. Точка безубыточности будет составлять около 38,2% бит (два минус золотое среднее), что приведет к сокращению 38,2% бит-пар и росту того же процента.

Ответ 2

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

Например, сжатие JPEG позволяет вам сжимать изображения довольно много, потому что это не имеет большого значения, если красный на вашем изображении равен 0xFF или 0xFE (обычно). Однако, если вы попытались сжать текстовый документ, такие изменения будут катастрофическими.

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

Пример: иногда использование tar файла gzip меньше, а иногда использование tar файла bzip меньше.

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

Ответ 3

Файловый архиватор 7z использует LZMA (Lempel Ziv Markow Algorithm), который представляет собой молодой алгоритм сжатия, который в настоящее время является одним из лучших коэффициентов сжатия (см. Страницу Сравнение сжатия Linux).

Другие преимущества наряду с высокой степенью сжатия:

• быстрая декомпрессия, примерно в 10-20 раз быстрее, чем сжатие
• малый объем памяти при распаковке файла