Основываясь на идее, что заархивированный файл является новым двоичным файлом, почему я не могу уменьшить размер Zip, снова и снова упаковывая его - до очень маленького результирующего файла?
4 ответа
7
Основываясь на идее, что заархивированный файл является новым бинарным файлом, почему я не могу уменьшить его размер, снова и снова упаковывая его в очень маленький файл?
Потому что сжатие работает на основе поиска шаблонов и сокращения данных, которые похожи.
Например, RLE (кодирование длин серий) - это простой метод сжатия, при котором данные проверяются, а серии похожих данных сжимаются следующим образом:
AAABCEEEJFFYYYYYYYYYYOOAAAAGGGGGAAA
becomes
3ABC3EJ2F10YOO4A5G3A
Как вы можете видеть, заменив повторяющиеся данные только данными и счетчиком того, сколько раз это происходит, вы можете уменьшить этот конкретный пример с 35 байтов до 20 байтов. Это не огромное снижение, но это по - прежнему 42% меньше. Более того, это небольшой надуманный пример; большие, реальные примеры могут иметь еще лучшее сжатие. OO был оставлен в покое , потому что заменив его 2O ничего не спасло бы.)
Текстовые файлы часто сжимаются очень хорошо, потому что они имеют много шаблонов, которые можно сжать. Например, слово the очень распространено в английском языке, поэтому вы можете отбросить каждый экземпляр слова с идентификатором, который составляет всего один байт (или даже меньше). Вы также можете сжать больше с частями слов, которые похожи, как cAKE , bAKE , shAKE , undertAKE и так далее.
Так почему же вы не можете сжать файл, который уже сжат? Потому что, когда вы сделали первоначальное сжатие, вы удалили шаблоны.
Посмотрите на сжатый пример RLE. Как вы можете сжать это дальше? Не существует прогонов идентичных данных для сжатия. На самом деле, часто, когда вы пытаетесь сжать файл, который уже сжат, вы можете получить файл большего размера . Например, если вы принудительно перекодировали приведенный выше пример, вы можете получить что-то вроде этого:
131A1B1C131E1J121F11101Y2O141A151G131A
Теперь данные сжатия (количество прогонов) сами по себе обрабатываются как данные, так что в результате вы получите файл большего размера, чем начали.
Вы можете попробовать использовать другой алгоритм сжатия, потому что возможно, что выходные данные одного алгоритма сжатия могут быть простыми для другого алгоритма, однако это обычно довольно маловероятно.
Конечно, это все о сжатии без потерь, когда распакованные данные должны быть точно идентичны исходным данным. При сжатии с потерями вы обычно можете удалить больше данных, но качество снижается. Кроме того, сжатие с потерями обычно использует какую-то схему, основанную на шаблонах (она не только отбрасывает данные), так что вы все равно в конечном итоге достигнете точки, где просто не будет шаблонов для поиска.
2
Если все сжатые файлы после сжатия снова уменьшают свои размеры (или имеют размеры не больше, чем их родительские файлы), то в какой-то момент размер станет равным 0, что не может быть истинным. Если это правда, нам почти не нужны файловые хранилища вообще.
Алгоритмы сжатия данных без потерь не могут гарантировать сжатие для всех наборов входных данных. Другими словами, для любого алгоритма сжатия данных без потерь будет входной набор данных, который не становится меньше при обработке алгоритмом, а для любого алгоритма сжатия данных без потерь, который уменьшает по меньшей мере один файл, будет по меньшей мере один файл, который он делает больше. Это легко доказать с помощью элементарной математики с использованием счетного аргумента:
- Предположим, что каждый файл представлен в виде строки битов произвольной длины.
- Предположим, что существует алгоритм сжатия, который преобразует каждый файл в выходной файл, который не длиннее исходного файла, и что по крайней мере один файл будет сжат в выходной файл, который короче исходного файла.
- Пусть M наименьшее число, такое, что существует файл F с длиной M бит, который сжимается во что-то более короткое. Пусть N будет длиной (в битах) сжатой версии F.
- Поскольку N <M, каждый файл длины N сохраняет свой размер во время сжатия. Есть 2 N таких файлов. Вместе с F это создает 2 N+1 файла, которые все сжимаются в один из 2 N файлов длиной N.
- Но 2 N меньше, чем 2 N+1, поэтому по принципу голубиных отверстий должен быть некоторый файл длины N, который одновременно является выходом функции сжатия на двух разных входах. Этот файл не может быть надежно распакован (какой из двух оригиналов должен быть получен?), Что противоречит предположению, что алгоритм был без потерь.
- Поэтому мы должны сделать вывод, что наша первоначальная гипотеза (что функция сжатия больше не создает файл) обязательно неверна.
https://en.wikipedia.org/wiki/Lossless_compression#Limitations
1
Я бы сказал, вы не можете сжимать произвольные двоичные файлы в значительной степени - подумайте об изображениях JPEG, видео x264 и так далее. Тем более, что вы хотите точно восстановить исходный файл (то есть побитово), вам нужно сжатие без потерь. 1
Причина такого ограниченного сжатия указана в статье в Википедии об энтропии, которая количественно оценивает ожидаемую ценность информации, содержащейся в сообщении:
Энтропия эффективно ограничивает производительность самого сильного сжатия без потерь (или почти без потерь), которое может быть реализовано теоретически с использованием типового набора или на практике с использованием кодирования Хаффмана, Лемпеля-Зива или арифметического кодирования. (...)
1 Очень сильное "сжатие" изображений JPEG возможно только потому, что некоторая информация отбрасывается (таким образом, что человеческий глаз не может распознать ее на первый взгляд; сжатие с потерями).
1
Файл, который был оптимально сжат, не будет иметь шаблонов или чего-либо, что можно уменьшить.
Давайте представим простой файл, который содержит это.
AAAAAAAAAAAAAAAAAAAA
BBBBBBBBBBBBBBBBBBBB
CCCCCCCCCCCCCCCCCCCC
Если мы сжимаем его, мы можем сказать, что это 20 A, перевод строки, затем 20 B, перевод строки, а затем 20 C. Или что-то вроде 20xA\n20xB\n20xC\n . После того, как мы выполнили первое сжатие, нет новых шаблонов для сжатия. Каждый бит, если информация уникальна.