Questão Por que compactar um arquivo compactado não reduz seu tamanho?


Com base na idéia de que um arquivo zipado é um novo arquivo binário, por que não posso reduzir o tamanho de um Zip fechando-o novamente - até um arquivo resultante muito pequeno?


4


origem


Relacionado: Posso compactar um arquivo RAR novamente para reduzir seu tamanho? - slhck


Respostas:


Com base na idéia de que um arquivo zipado é um novo arquivo binnary, por que não posso reduzir seu tamanho compactando-o novamente e sucessivamente em um arquivo muito pequeno?

Porque a compactação funciona com base na localização de padrões e na redução de dados semelhantes.

Por exemplo, RLE (Codificação de comprimento de execução) é um método de compactação simples no qual os dados são examinados e as execuções de dados semelhantes são compactadas da seguinte forma:

AAABCEEEJFFYYYYYYYYYYOOAAAAGGGGGAAA

becomes

3ABC3EJ2F10YOO4A5G3A

Como você pode ver, substituindo dados repetidos apenas pelos dados e uma contagem de quantas vezes isso ocorre, você pode reduzir esse exemplo específico de 35 bytes para 20 bytes. Isso não é enorme redução, mas ainda é 42% menor. Além disso, este é um pequeno exemplo inventado; exemplos maiores e reais poderiam ter uma compactação ainda melhor. (O OO foi deixado sozinho porque substituí-lo com 2O não salvaria nada.)

Os arquivos de texto geralmente são muito bem compactados porque tendem a ter muitos padrões que podem ser compactados. Por exemplo, a palavra a é muito comum em inglês, então você pode soltar todas as instâncias da palavra com um identificador que é apenas um byte (ou até menos). Você também pode comprimir mais com partes de palavras que são semelhantes como cAKE, bAKE, shAKE, undertAKE, e assim por diante.

Então, por que você não pode compactar um arquivo que já está compactado? Porque quando você fez a compressão inicial, você removeu os padrões.

Veja o exemplo de RLE comprimido. Como você pode comprimir isso ainda mais? Não há execuções de dados idênticos para compactar. Na verdade, quando você tenta compactar um arquivo que já está compactado, você pode acabar com um maior Arquivo. Por exemplo, se você forçou o exemplo acima a ser recodificado, pode acabar com algo parecido com isto:

131A1B1C131E1J121F11101Y2O141A151G131A

Agora, os dados de compactação (as contagens de execução) estão sendo tratados como dados, então você acaba com um arquivo maior do que começou.

O que você poderia try é usar um algoritmo de compressão diferente porque é possível que a saída de um algoritmo de compactação possa ser primo para um algoritmo diferente, no entanto, isso geralmente é bastante improvável.

Claro, isso é tudo sobre compressão sem perdas onde os dados descompactados devem ser exatamente idênticos aos dados originais. Com compressão com perdaGeralmente, você pode remover mais dados, mas a qualidade diminui. Além disso, a compactação com perdas geralmente usa algum tipo de esquema baseado em padrões (não  descarte os dados), de modo que você acabará alcançando um ponto em que simplesmente não há padrões para encontrar.


7





Se todos os arquivos compactados após a compactação novamente reduzirem seus tamanhos (ou tiverem tamanhos não maiores que seus pais), então, em algum momento, o tamanho se tornará 0, o que não pode ser verdadeiro. Se isso é verdade, quase não precisamos de armazenamento de arquivos.

Algoritmos de compactação de dados sem perdas não pode garantir a compactação para todos os conjuntos de dados de entrada. Em outras palavras, para qualquer algoritmo de compressão de dados sem perda, haverá um conjunto de dados de entrada que não será menor quando processado pelo algoritmo e para qualquer algoritmo de compactação de dados sem perdas que torne pelo menos um arquivo menor, haverá pelo menos um arquivo que faz maior. Isso é facilmente comprovado com matemática elementar usando um argumento de contagem, como segue:

  • Suponha que cada arquivo seja representado como uma seqüência de bits de um comprimento arbitrário.
  • Suponha que haja um algoritmo de compactação que transforme cada arquivo em um arquivo de saída que não seja maior que o arquivo original e que pelo menos um arquivo seja compactado em um arquivo de saída menor que o arquivo original.
  • Seja M o menor numero tal que haja um arquivo F com comprimento M bits que comprime para algo menor. Seja N o comprimento (em bits) da versão compactada de F.
  • Como N <M, todo arquivo de comprimento N mantém seu tamanho durante a compactação. Há 2N esses arquivos. Junto com F, isso faz 2NArquivos +1 que são compactados em um dos doisN arquivos de comprimento N.
  • Mas 2N é menor que 2N+1, então pelo princípio do escaninho deve haver algum arquivo de comprimento N que seja simultaneamente a saída da função de compressão em duas entradas diferentes. Esse arquivo não pode ser descompactado de forma confiável (qual dos dois originais deve resultar?), O que contradiz a suposição de que o algoritmo foi sem perdas.
  • Devemos, portanto, concluir que nossa hipótese original (de que a função de compactação não faz mais arquivos) é necessariamente falsa.

https://en.wikipedia.org/wiki/Lossless_compression#Limitations


2





Um arquivo que foi compactado otimamente não terá nenhum padrão ou qualquer coisa que possa ser reduzida.

Vamos imaginar um arquivo simples que contenha isso.

AAAAAAAAAAAAAAAAAAAA
BBBBBBBBBBBBBBBBBBBB
CCCCCCCCCCCCCCCCCCCC

Se comprimirmos, podemos dizer que são 20 A's, newline, seguidos por 20 B's, newline, seguidos por 20 C's. Ou algo parecido 20xA\n20xB\n20xC\n. Uma vez que tenhamos feito a primeira compressão, não há novos padrões para comprimir. Todo bit se a informação é única.


1





Eu diria que você não pode comprimir arbitrário arquivos binários, em grande medida - pense em imagens JPEG, x264 vídeos e assim por diante. Especialmente desde que você quer reconstruir seu arquivo original exatamente (ou seja, pouco a pouco) você precisa de um compressão sem perdas.1

A razão para esta compressão limitada é declarada neste Artigo da Wikipedia sobre o Entropy  que quantifica o valor esperado da informação contida em uma mensagem:

Entropia efetivamente limita o desempenho dos mais fortes sem perdas   (ou quase lossless) compressão possível, que pode ser realizada em   teoria usando o conjunto típico ou na prática usando Huffman,   Lempel-Ziv ou codificação aritmética. (...)


1A "compactação" muito forte de imagens JPEG só é possível, pois algumas informações são descartadas (de uma maneira que o olho humano não consegue reconhecê-las à primeira vista; compressão com perda).


1



I'd say can't compress any binary file Isso não é verdade, você pode geralmente comprimir exectuables um pouco, daí UPX. - Synetech
@Synetech: Você está absolutamente certo, isso foi uma armadilha de linguagem. Eu não quis dizer qualquer, mas arbitrário arquivo (no sentido de dados aleatórios). - mpy
Ah tudo bem, entendo. Sim, um arquivo contendo bytes aleatórios é simplesmente terrível para compactação. - Synetech