Questão Por que o Zip é capaz de compactar um único arquivo menor que vários arquivos com o mesmo conteúdo?


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

Método 1: não compactá-los

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 arquivos de 10.000 xml

Comando:

zip all.zip $(ls -1)

Resultados:

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

Método 4: Concatene os arquivos em um único arquivo e zip-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 fechando um único arquivo?
  • Eu estava esperando obter resultados drasticamente melhores usando o método 3 do que o método 2, mas não o faça. Por quê?
  • Este comportamento é específico para zip? Se eu tentei usar gzip Eu teria 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 é o metadado do sistema que é armazenado 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 inexplicado.


119


origem


Se não me engano, é este fenómeno que faz com que as pessoas façam .tar.gz ao contrário de apenas fechar o diretório inteiro. - corsiKa
UMA pergunta semelhante já foi solicitado, tl; dr use arquivos sólidos de 7zip. - Dmitry Grigoryev
@sixtyfootersdude Como um teste para validar algumas das respostas, você pode tentar fechar 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
Ao invés de $(ls -1), Apenas use *: for x in *; zip all.zip * - muru
Se você quiser fazer uma compactação sólida com ZIP, veja uma solução: primeiro, crie uma descompactado ZIP contendo todos os seus arquivos. Em seguida, coloque esse CEP dentro de outro ZIP compactado. - user20574


Respostas:


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

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


124



É também por isso que algumas ferramentas de compactação oferecem a opção de compactar os arquivos separadamente ou como uma entidade única. (Embora geralmente isso também significa que você tem que descompactar mais do arquivo do que você faria caso você queira ver apenas um único arquivo.) - JAB
@JAB: Ferramentas de compactação como 7z e rar usam o termo "sólido" para compactar vários arquivos da cabeça aos pés em fluxos de compactaçã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. Você pode obter uma troca razoável entre o acesso aleatório e a redundância de arquivos cruzados. O 7z pode usar o esquema de compactação LZMA mais efetivo (mas mais lento para compactar), que é outra vantagem sobre o zip. - Peter Cordes
Você está dizendo isso? there is no support in Zip to find redundancy between files está na especificação do arquivo zip? - sixtyfootersdude
@sixtyfootersdude Muitos algoritmos de compactação, como DEFLATE, operam como um fluxo. Para recuperar informações suficientes para descompactar uma parte do fluxo, você precisa processar todo o fluxo até esse ponto. Se eles tentassem encontrar redundância entre os arquivos, você teria que descompactar todos os 1000 arquivos para chegar ao último. Isso é tipicamente como o tgz funciona, na verdade. No entanto, o zip foi projetado para permitir que você extraia arquivos individuais. tgz é projetado para ser mais tudo ou nada - Cort Ammon
@sixtyfootersdude - está correto. Parafraseando Cort: As especificações do pkzip não suportam o trabalho de arquivo cruzado. Se o fizerem, extrair um arquivo pode requerer que todo o arquivo (e todo arquivo) seja extraído. - James Snell


A compactação ZIP é baseada em padrões repetitivos nos dados a serem compactados, e a compactação fica melhor quanto mais tempo o arquivo estiver, à medida que mais e mais padrões possam ser encontrados e usados.

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

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


46



O ZIP faz o arquivamento e a compactação. Isso significa que o ZIP compacta cada arquivo individualmente, mesmo que todos eles acabem no mesmo arquivo ZIP? - gerrit
isso meio que tem que - imagine você remover um único arquivo, você não quer que ele gaste mais meia hora comprimindo novamente o restante com um novo 'dicionário'. - também, provavelmente assume que arquivos diferentes precisam de 'dicionários' muito diferentes. - Aganju
Eu não vejo por que isso tem que acontecer. Com as ferramentas do Unix, eu primeiro arquivaria um arquivo com o tar e depois o compactaria com gzip / bz2 / lzma. O algoritmo de compactação não se importa com quantos arquivos estão codificados no arquivo. Além disso, quão comum é realmente remover um único arquivo de um arquivo compactado? Eu não acho que já fiz isso. - gerrit
Eu não discordo, e isso é provavelmente um bom caminho. Eu não criei nem escrevi ZIP. Eu acabei de dizer o que isso faz ... - Aganju
@gerrit Tem seus próprios problemas. O Zip foi projetado para permitir que você acesse rapidamente qualquer arquivo no arquivo morto - tente descompactar um único arquivo de um arquivo de 100 GiB UHA e você verá por que eles escolheram esse caminho. Ele também é projetado para anexar - você pode ter 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 tudo isso comum), ele não pode explorar as semelhanças para reduzir o tamanho do arquivo. - Luaan


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. O Gzip e o Bzip2 não podem compactar vários arquivos para que o Tar seja usado primeiro, com o mesmo efeito da compactação sólida.

Como o arquivo xml tem 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 string "<content><element name=" e o compressor já achou essa string em outro arquivo ele irá substituí-lo com um pequeno ponteiro para a correspondência anterior, se o compressor não usar 'compressão sólida' a primeira ocorrência da string no arquivo será gravada como um literal que é maior.


42





O Zip não armazena apenas o conteúdo do arquivo, ele também armazena 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ê tiver um arquivo, você tem um conjunto de metadados; Se você tiver 10.000 arquivos, terá 10.000 conjuntos de metadados.


9



Bom ponto, mas os metadados do sistema estão ocupando apenas 1,4 MB de espaço. Veja minha edição. - sixtyfootersdude
Eu 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 sendo maiores em seus arquivos xml do que em seus arquivos vazios. - Ben Richards
Esse foi meu primeiro pensamento. Informações do cabeçalho do arquivo zip - WernerCD
Isso explica apenas a diferença entre 2 e 3 - não 4. - Luaan
@Luaan Não, no 2 e no 3, os metadados de todos os 10.000 arquivos são incluídos no arquivo zip ou nos arquivos, de modo que o tamanho total do arquivo é quase do mesmo tamanho. Em 4, há apenas metadados para um arquivo e o arquivo zip é muito menor. - Mike Scott


Uma opção perdida pelo OP é compactar todos os arquivos com a compactação desativada e, em seguida, zipar o zip resultante com a compactação definida no máximo. Isso praticamente emula o comportamento dos arquivos compactados * nix .tar.Z, .tar.gz, .tar.bz, etc., permitindo que a compactação explore as redundâncias nos limites dos arquivos (que o algoritmo ZIP não pode executar quando executado em um único arquivo). 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 a etapa extra, usando temporariamente muito mais espaço em disco do que seria necessário para um .zip normal.

Com a onipresença de ferramentas gratuitas como o 7-Zip para estender a família de tar ao Windows, não há realmente nenhuma razão para não usar um .tar.gz ou .tar.bz, etc., já que o Linux, OS X e os BSDs todos têm ferramentas nativas para manipulá-las.


6



O gzip e o bzip2 podem acabar ainda pior, porque eles são projetados tendo em mente os fluxos de compactação, portanto, eles terão que iniciar a saída de dados compactados antes que todos os dados para compactação sejam conhecidos. - rackandboneman
@rackandboneman: Esta é a troca que você deve fazer ao compactar arquivos maiores do que a quantidade de memória que você está disposto a usar no momento da compactação. (E também, a quantidade de tempo de CPU necessária para encontrar algo globalmente ideal seria enorme.) Um dicionário de compactação enorme também pode aumentar a memória necessária para descompressão. Esta é uma opção para LZMA (xz / 7-zip). De qualquer forma, dicionários adaptativos podem captar padrões assim que estiverem visíveis. Não é como se ele apenas construísse um sistema de codificação estático baseado nos primeiros 32k. É por isso que o gzip não é uma droga. - Peter Cordes


O formato de compactação zip armazena e compacta cada arquivo separadamente. Não aproveita a repetição entre arquivos, somente dentro de um arquivo.

A concatenação do arquivo permite que o zip aproveite as repetições em todos os arquivos, resultando em uma drástica maior compactação.

Por exemplo, digamos que cada arquivo XML tenha um determinado cabeçalho. Esse cabeçalho só ocorre 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 podia ser compactado para isso, mas no método 4 poderia.


5



Como isso é diferente de uma das 3 principais respostas já postadas 5 horas antes? - Xen2050
@ Xen2050 Não é muita diferença, eu só pensei que eu poderia explicar isso de forma mais clara. - BonsaiOak
@BonsaiOak - em seguida, adicione um comentário à resposta correta ou edite se você tiver bastante representante. Se não, mas o seu comentário adiciona clareza, alguém pode pegar isso e editar a postagem de qualquer maneira. - AdamV
@AdamV eu vejo o seu ponto. Minha resposta atualmente não adiciona nenhuma informação útil, embora tenha sido feita quando eu a escrevi. Já existem comentários apropriados na primeira resposta, então também não vejo sentido em adicioná-los. Você está dizendo que eu deveria apenas fechar minha resposta? Que mal há em deixá-lo aberto? - BonsaiOak


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

Ao compactar vários arquivos pequenos individuais, você terá muita sorte de poder compactá-los para preencher um bloco de compactação. Ao compactar um único bloco monolítico, o sistema pode continuar apenas a transmitir dados para seu algoritmo, ignorando os "limites" (por falta de uma palavra melhor) dos arquivos individuais.

Também o ASCII é conhecido por ter um alto fator de compressão. Além disso, o xml costuma ser muito repetitivo, tornando os metadados uma grande parte dos dados que não podem ser facilmente compactados como o conteúdo xml.

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

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


4





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 construir um dicionário do qual padronizar tem mais ocorrências e depois, ao comprimir, usa menos bits para armazenar mais repetidas padrões e mais bits para armazenar menos repetidos padronizar.

Quando você concatenar esses arquivos, o arquivo de origem (a origem do zip) é grande, mas contém muito mais padrões repetidos porque de distribuição das estruturas de perfuração de um XML são amortizado no grande arquivo inteiro, dando a chance de ZIP para armazenar os padronizar 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á o melhor padronizardistribuição em todos os arquivos e não arquivo por arquivo.

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


3





Além da resposta do 7-Zip, há outra abordagem que não é tão boa, mas valeria a pena ser testada 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 ele contém muitos arquivos idênticos, o compressor pode encontrar essa redundância e compactá-lo. Note que eu também vi um pequeno ganho ao lidar com um grande número de arquivos sem redundância. Se você realmente se importa com tamanho, vale a pena tentar se você tiver muitos arquivos no seu zip.


-1



Isso só funciona se você fizer o primeiro zip com a compactação desativada, como mencionado acima. - Monty Harder
@MontyHarder Eu já vi isso funcionar com a compressão ativada. - Loren Pechtel