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

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.

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.

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.

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.

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.

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.

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.

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

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.

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.