Как утилиты сжатия добавляют файлы последовательно в сжатый архив? - PullRequest
1 голос
/ 24 апреля 2011

Например, когда вы tar -zcvf каталог, вы можете увидеть список файлов, добавляемых последовательно в окончательный файл gzip.

Но как это происходит?

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

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

Я что-то упустил?Если нет, значит ли это, что все эти алгоритмы сжатия выбирают неоптимальное представление данных?

Ответы [ 3 ]

3 голосов
/ 24 апреля 2011

В gzip избыточность ограничена конкретным размером окна (по умолчанию 32k, если я правильно помню).Это означает, что после обработки несжатых данных за пределами этого окна вы можете начать запись сжатых выходных данных.

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

2 голосов
/ 24 апреля 2011

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

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

Существуют методы сжатия (например, двухпроходное сжатие Хаффмана), при котором вы сканируете данные, чтобы найти идеальный «словарь» для этих конкретных данных, а затем используете его для сжатия данных. Однако, когда вы делаете это, вам, как правило, приходится передавать словарь вместе с данными, чтобы иметь возможность распаковать его на принимающей стороне.

То, что может быть разумным компромиссом - если у вас достаточно высокий уровень уверенности в том, что вы будете сжимать достаточно данных одним и тем же словарем, вы можете получить больше от улучшенного сжатия, чем потерять передавая словарь. Однако есть одна проблема: «символ» данных в файле часто изменяется внутри одного и того же файла, поэтому словарь, который лучше всего работает в одной части файла, может быть не совсем хорошим для другой части файла. Это особенно актуально для сжатия файла tar, который содержит несколько составных файлов, каждый из которых может (и, вероятно, будет) иметь различную избыточность.

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

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

1 голос
/ 24 апреля 2011

Когда вы говорите tar -zcvf X, это эквивалентно высказыванию:

tar -cvf X | gzip 

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

...