Por que o Zip consegue compactar um arquivo único menor que vários arquivos com o mesmo conteúdo?

126

Suponha que eu tenha 10.000 arquivos XML. Agora, suponha que eu queira enviá-los para um amigo. Antes de enviá-los, eu gostaria de compactá-los.

Método 1: Não os comprima

Resultados:

Resulting Size: 62 MB
Percent of initial size: 100%

Método 2: compactar todos os arquivos e enviar a ele 10.000 arquivos xml

Comando:

for x in $(ls -1) ;  do   echo $x ; zip "$x.zip" $x ; done

Resultados:

Resulting Size: 13 MB
Percent of initial size: 20%

Método 3: criar um único zip contendo 10.000 arquivos xml

Comando:

zip all.zip $(ls -1)

Resultados:

Resulting Size: 12 MB
Percent of initial size: 19%

Método 4: concatenar os arquivos em um único arquivo e compactá-lo

Comando:

cat *.xml > oneFile.txt ; zip oneFile.zip oneFile.txt

Resultados:

Resulting Size: 2 MB
Percent of initial size: 3%

Questões:

  • Por que obtenho resultados tão melhores quando estou apenas compactando um único arquivo?
  • Eu esperava obter resultados drasticamente melhores usando o método 3 do que o método 2, mas não o fiz. Por quê?
  • Esse comportamento é específico para zip? Se eu tentasse usar gzip, obteria resultados diferentes?

Informação adicional:

$ zip --version
Copyright (c) 1990-2008 Info-ZIP - Type 'zip "-L"' for software license.
This is Zip 3.0 (July 5th 2008), by Info-ZIP.
Currently maintained by E. Gordon.  Please send bug reports to
the authors using the web page at www.info-zip.org; see README for details.

Latest sources and executables are at ftp://ftp.info-zip.org/pub/infozip,
as of above date; see http://www.info-zip.org/ for other sites.

Compiled with gcc 4.4.4 20100525 (Red Hat 4.4.4-5) for Unix (Linux ELF) on Nov 11 2010.

Zip special compilation options:
    USE_EF_UT_TIME       (store Universal Time)
    SYMLINK_SUPPORT      (symbolic links supported)
    LARGE_FILE_SUPPORT   (can read and write large files on file system)
    ZIP64_SUPPORT        (use Zip64 to store large files in archives)
    UNICODE_SUPPORT      (store and read UTF-8 Unicode paths)
    STORE_UNIX_UIDs_GIDs (store UID/GID sizes/values using new extra field)
    UIDGID_NOT_16BIT     (old Unix 16-bit UID/GID extra field not used)
    [encryption, version 2.91 of 05 Jan 2007] (modified for Zip 3)

Editar: metadados

Uma resposta sugere que a diferença são os metadados do sistema armazenados no zip. Eu não acho que isso possa ser o caso. Para testar, fiz o seguinte:

for x in $(seq 10000) ; do touch $x ; done
zip allZip $(ls -1)

O zip resultante é de 1,4 MB. Isso significa que ainda há ~ 10 MB de espaço inexplicável.

sixtyfootersdude
fonte
34
Se não me engano, é esse fenômeno que faz com que as pessoas façam, .tar.gzem vez de apenas fechar o diretório inteiro.
corsiKa
18
Uma pergunta semelhante já foi feita, usando os arquivos 7zip sólidos.
Dmitry Grigoryev
3
@sixtyfootersdude Como um teste para validar algumas das respostas, você pode tentar compactar o zip produzido no método 3? Eu suspeito que isso irá reduzir o tamanho do arquivo para algo comparável ao método 4.
Travis
7
Em vez de $(ls -1), basta usar *: for x in *; zip all.zip *
Muru
4
Se você deseja fazer uma compactação sólida com o ZIP, aqui está uma solução: primeiro, crie um ZIP não compactado contendo todos os seus arquivos. Em seguida, coloque esse ZIP dentro de outro ZIP compactado.
user20574

Respostas:

129

O Zip trata o conteúdo de cada arquivo separadamente ao compactar. Cada arquivo terá seu próprio fluxo compactado. Há suporte no algoritmo de compactação (normalmente DEFLATE ) para identificar seções repetidas. No entanto, não há suporte no Zip para encontrar redundância entre arquivos.

É por isso que há tanto espaço extra quando o conteúdo está em vários arquivos: está colocando o mesmo fluxo compactado no arquivo várias vezes.

Alan Shutko
fonte
9
É também por isso que algumas ferramentas de compactação oferecem a opção de compactar os arquivos separadamente ou como uma única entidade. (Embora geralmente isso também significa que você tem que descompactar mais do arquivo que você faria de outra forma, se você quiser ver apenas um único arquivo nele.)
JAB
28
@JAB: Ferramentas de compactação como 7z e rar usam o termo "sólido" para empacotar vários arquivos de cabeça a ponta em fluxos de compressão maiores. Com um tamanho de bloco moderado como 64MiB, o acesso aleatório a um único arquivo pode exigir a descompactação de até 64MiB de dados desde o início do bloco de compactação em que ele se encontra. Você pode obter uma troca decente entre acesso aleatório e encontrar redundância entre arquivos. O 7z pode usar o esquema de compactação LZMA mais eficaz (mas mais lento para compactar), que é outra vantagem sobre o zip.
Peter Cordes
Você está dizendo que there is no support in Zip to find redundancy between filesestá na especificação do arquivo zip?
Sixtyfootersdude
6
@sixtyfootersdude Muitos algoritmos de compactação, como DEFLATE, operam como um fluxo. Para recuperar informações suficientes para descompactar uma parte do fluxo, é necessário processar o fluxo inteiro até esse ponto. Se eles tentassem encontrar redundência entre arquivos, seria necessário descompactar todos os 1000 arquivos para chegar ao último. Normalmente, é assim que o tgz funciona. No entanto, o zip foi projetado para permitir que você extraia arquivos individuais. tgz é projetado para ser mais tudo-ou-nada
Cort Ammon
1
@sixtyfootersdude - está correto. Parafraseando Cort: As especificações do pkzip não suportam arquivos cruzados. Se o fizeram, a extração de um arquivo pode exigir a extração de todo o arquivo (e de todos os arquivos).
James Snell
48

A compactação ZIP é baseada em padrões repetitivos nos dados a serem compactados, e a compactação fica melhor quanto maior o arquivo, pois mais e mais padrões podem ser encontrados e usados.

Simplificado, se você compactar um arquivo, o dicionário que mapeia códigos (curtos) para padrões (mais longos) está necessariamente contido em cada arquivo zip resultante; se você compactar um arquivo longo, o dicionário será "reutilizado" e se tornará ainda mais eficaz em todo o conteúdo.

Se seus arquivos forem um pouco parecidos (como o texto sempre é), a reutilização do 'dicionário' se tornará muito eficiente e o resultado será um zip total muito menor.

Aganju
fonte
3
O ZIP faz o arquivamento e a compactação. Isso significa que o ZIP comprime cada arquivo individualmente, mesmo que todos acabem no mesmo arquivo ZIP?
gerrit
2
isso meio que tem que ser - imagine que você remova um único arquivo, não quer que ele gaste mais meia hora recompactando o restante com um novo 'dicionário'. - também, provavelmente assume que arquivos diferentes precisam de 'dicionários' muito diferentes.
Aganju
2
Não vejo por que isso precisa. Com as ferramentas Unix, eu primeiro arquivava um arquivo com tar e depois o compactava com gzip / bz2 / lzma. O algoritmo de compactação não se importa com quantos arquivos são codificados no arquivo morto. Além disso, quão comum é realmente remover um único arquivo de um arquivo compactado? Acho que nunca fiz isso.
Gerrit
4
Eu não discordo, e essa é provavelmente uma boa maneira. Não criei nem escrevi ZIP. Eu apenas disse o que ele faz ...
Aganju
16
@gerrit Ele tem seus próprios problemas. O Zip foi desenvolvido para permitir que você acesse rapidamente qualquer arquivo no arquivo morto - tente descompactar um único arquivo de um arquivo UHA de 100 GiB e você verá por que eles escolheram esse caminho. Ele também foi projetado para anexar - você pode ter o seu zip de backup e continuar adicionando (ou substituindo) arquivos, conforme necessário. Tudo isso é uma grande ajuda ao usar arquivos. A desvantagem é que, se você estiver compactando arquivos muito semelhantes (o que não é tão comum), não poderá explorar as semelhanças para reduzir o tamanho do arquivo morto.
Luaan 15/12/2015
43

No Zip, cada arquivo é compactado separadamente. O oposto é 'compactação sólida', ou seja, os arquivos são compactados juntos. 7-zip e Rar usam compactação sólida por padrão. Gzip e Bzip2 não podem compactar vários arquivos, portanto, o Tar é usado primeiro, tendo o mesmo efeito que a compactação sólida.

Como o arquivo xml possui estrutura semelhante e provavelmente conteúdo semelhante, se os arquivos forem compactados juntos, a compactação será maior.

Por exemplo, se um arquivo contiver a sequência "<content><element name="e o compressor já a encontrar em outro arquivo, ela será substituída por um pequeno ponteiro para a correspondência anterior, se o compressor não usar 'compactação sólida' a primeira ocorrência da sequência na O arquivo será gravado como um literal maior.

ggf31416
fonte
9

O Zip não armazena apenas o conteúdo do arquivo, mas também os metadados do arquivo, como o ID do usuário, permissões, tempos de criação e modificação e assim por diante. Se você possui um arquivo, possui um conjunto de metadados; se você tiver 10.000 arquivos, terá 10.000 conjuntos de metadados.

Mike Scott
fonte
3
Bom ponto, mas os metadados do sistema estão ocupando apenas 1,4 MB de espaço. Veja minha edição.
Sixtyfootersdude
1
Não estou familiarizado com o algoritmo zip, mas os metadados não são apenas as informações do arquivo, mas também coisas como tamanho e um dicionário, possivelmente algumas informações sobre a distribuição de caracteres. Um dicionário em um arquivo de texto não vazio será diferente de zero. Provavelmente é por isso que você vê os metadados maiores nos arquivos xml do que nos vazios.
Ben Richards
Esse foi meu primeiro pensamento. Informações de cabeçalho de arquivo
zip
Isso só explica a diferença entre 2 e 3 - Não 4.
Luaan
@Luaan Não, em 2 e 3, os metadados para todos os 10.000 arquivos estão incluídos no ou nos arquivos zip, portanto, o tamanho total do arquivo é quase do mesmo tamanho. Em 4, existem apenas metadados para um arquivo, e o arquivo zip é muito menor.
Mike Scott
7

Uma opção perdida pelo OP é compactar todos os arquivos com a compactação desativada e compactar o zip resultante com a compactação definida no máximo. Emula aproximadamente o comportamento dos arquivos compactados * nix .tar.Z, .tar.gz, .tar.bz etc., permitindo que a compactação explore redundâncias entre os limites do arquivo (o que o algoritmo ZIP não pode fazer quando executado em um único passar). Isso permite que os arquivos XML individuais sejam extraídos posteriormente, mas maximiza a compactação. A desvantagem é que o processo de extração requer uma etapa extra, usando temporariamente muito mais espaço em disco do que seria necessário para um arquivo zip normal.

Com a onipresença de ferramentas gratuitas, como o 7-Zip, para estender a família tar ao Windows, não há realmente nenhuma razão para não usar um arquivo .tar.gz ou .tar.bz, etc., pois o Linux, OS X e os BSDs possuem ferramentas nativas para manipulá-los.

Monty Harder
fonte
O gzip e o bzip2 podem acabar ainda pior porque foram projetados com fluxos de compressão em mente; portanto, eles terão que começar a produzir dados compactados antes que todos os dados a compactar sejam conhecidos.
rackandboneman
@rackandboneman: Essa é a compensação que você deve fazer ao compactar arquivos maiores que a quantidade de memória que você deseja usar no momento da compactação. (E também, a quantidade de tempo de CPU necessária para encontrar algo ideal em todo o mundo seria enorme.) Um enorme dicionário de compactação também pode aumentar a memória necessária para a descompactação . Esta é uma opção para LZMA ( xz/ 7-zip). De qualquer forma, os dicionários adaptáveis ​​podem captar os padrões quando estiverem visíveis. Não é como se apenas construísse um sistema de codificação estática com base nos primeiros 32k. É por isso que o gzip não é ruim.
22815 Peter Cordes
Eu realmente gosto desse "truque" se você precisar ficar com o formato zip. Discordo do seu "não há razão para não usar o 7-zip" - se estiver enviando um arquivo para um amigo não técnico, quero ter certeza de que ele será capaz de abri-lo facilmente. Se estou enviando para um cliente comercial, ainda mais.
Wowfunhappy 14/03
5

O formato de compactação zip armazena e compacta cada arquivo separadamente. Não tira vantagem da repetição entre arquivos, apenas dentro de um arquivo.

Concatenar o arquivo permite que o zip aproveite as repetições em todos os arquivos, resultando em drasticamente mais compactação.

Por exemplo, digamos que cada arquivo XML tenha um determinado cabeçalho. Esse cabeçalho ocorre apenas uma vez em cada arquivo, mas é repetido quase de forma idêntica em muitos outros arquivos. Nos métodos 2 e 3, o zip não pode compactar para isso, mas no método 4 pode.

BonsaiOak
fonte
3
Qual é a diferença de uma das 3 principais respostas já postadas 5 horas antes?
Xen2050 15/12/2015
1
@ Xen2050 Não há muita diferença, eu apenas pensei em explicar mais claramente.
BonsaiOak
1
@BonsaiOak - adicione um comentário à resposta correta ou edite se você tiver representante suficiente. Caso contrário, mas o seu comentário adiciona clareza, alguém pode pegar isso e editar a postagem de qualquer maneira.
AdamV
@AdamV Entendo o seu ponto. Atualmente, minha resposta não adiciona nenhuma informação útil, embora tenha sido possível quando a escrevi. Já existem comentários apropriados sob a primeira resposta, então também não vejo sentido em adicioná-los. Você está dizendo que eu deveria fechar minha resposta? Que mal há em deixá-lo aberto?
BonsaiOak
4

Ao lado dos metadados que Mike Scott mencionou, também há sobrecarga no algoritmo de compactação.

Ao compactar um monte de arquivos pequenos individuais, você terá que ter muita sorte para poder compactá-los, pois isso só preenche um bloco de compactação. Ao compactar um único bloco monolítico, o sistema pode simplesmente continuar transmitindo dados para seu algoritmo, ignorando os 'limites' (por falta de palavras melhores) dos arquivos individuais.

Também se sabe que o ASCII possui um alto fator de compressão. plus xml geralmente é muito repetitivo, tornando os metadados uma grande parte dos dados que não podem ser tão facilmente compactados quanto o conteúdo xml.

Por fim, se a memória funcionar corretamente, o zip usará algo como codificação de dicionário, que é especialmente eficaz em arquivos ascii e, mais ainda, em XML devido à sua repetibilidade

Compactação de dados explicada: http://mattmahoney.net/dc/dce.html

GapWim
fonte
3

Considere este XML:

<root>
  <element id="1" />
  <element id="2" /> 
  <other id="3" />
  ...
</root>

Um XML tem uma estrutura muito repetitiva, o Zip aproveita essas repetições para criar um dicionário cujo padrão tem mais ocorrências e, ao compactar, usa menos bits para armazenar mais padrões repetidos e mais bits para armazenar menos padrões repetidos .

Quando você concatena esses arquivos, o arquivo de origem (a origem do zip) é grande, mas contém padrões muito mais repetidos, porque a distribuição das estruturas de perfuração de um XML é amortizada no arquivo inteiro grande, dando a chance ao ZIP de armazenar esses padrões. usando menos bits.

Agora, se você combinar XML diferente em um único arquivo, mesmo quando esses arquivos tiverem nomes de tags completamente diferentes, o algoritmo de compactação encontrará a melhor distribuição de padrões entre todos os arquivos, e não arquivo por arquivo.

Por fim, o algoritmo de compactação encontrou a melhor distribuição repetida de padrões.

rnrneverdies
fonte
-1

Além da resposta do 7-Zip, há outra abordagem que não é tão boa, mas vale a pena testar se, por algum motivo, você não quiser usar o 7-Zip:

Comprima o arquivo zip. Agora, normalmente um arquivo zip é incompressível, mas quando contém muitos arquivos idênticos, o compressor pode encontrar essa redundância e compactá-la. Observe que também vi um pequeno ganho ao lidar com um grande número de arquivos sem redundância. Se você realmente se importa com o tamanho, vale a pena tentar se você tiver muitos arquivos no seu zip.

Loren Pechtel
fonte
Isso só funciona se você fizer o primeiro zip com a compactação desativada como mencionei acima.
Monty Mais difícil
@MontyHarder Já vi funcionar com a compactação ativada.
Loren Pechtel