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

Question

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 zipando-o novamente - até um arquivo resultante muito pequeno?

    

Answer 1

Based on the idea that a zipped file is a new binnary file, why I can't reduce it's size by zipping it again and successively up to a very small file?

Como 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 em que os dados são examinados e executados de dados semelhantes são compactados 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 é uma redução enorme , 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 por 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 compactar mais com partes de palavras 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 compactaçã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, pode acabar com um arquivo maior . 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 tentar é 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, mas isso geralmente é pouco provável.

Naturalmente, isso é tudo sobre compactação sem perdas , em que os dados descompactados devem ser exatamente idênticos aos dados originais. Com a compactação com perdas , geralmente é possível remover mais dados, mas a qualidade diminui. Além disso, a compactação com perdas normalmente usa algum tipo de esquema baseado em padrões (ele não somente descarta os dados), de modo que você acabará alcançando um ponto em que simplesmente não há padrões para localizar.

    

Answer 2

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 será 0, o que não pode ser verdadeiro. Se isso é verdade, quase não precisamos de armazenamento de arquivos.

Lossless data compression algorithms cannot guarantee compression for all input data sets. In other words, for any lossless data compression algorithm, there will be an input data set that does not get smaller when processed by the algorithm, and for any lossless data compression algorithm that makes at least one file smaller, there will be at least one file that it makes larger. This is easily proven with elementary mathematics using a counting argument, as follows:

• Assume that each file is represented as a string of bits of some arbitrary length.
• Suppose that there is a compression algorithm that transforms every file into an output file that is no longer than the original file, and that at least one file will be compressed into an output file that is shorter than the original file.
• Let M be the least number such that there is a file F with length M bits that compresses to something shorter. Let N be the length (in bits) of the compressed version of F.
• Because N < M, every file of length N keeps its size during compression. There are 2^N such files. Together with F, this makes 2^N+1 files that all compress into one of the 2^N files of length N.
• But 2^N is smaller than 2^N+1, so by the pigeonhole principle there must be some file of length N that is simultaneously the output of the compression function on two different inputs. That file cannot be decompressed reliably (which of the two originals should that yield?), which contradicts the assumption that the algorithm was lossless.
• We must therefore conclude that our original hypothesis (that the compression function makes no file longer) is necessarily untrue.

link

    

Answer 3

Um arquivo que tenha sido compactado de maneira ideal 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 com 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.

    

Answer 4

Eu diria que você não pode compactar arquivos binários arbitrários em grande medida - pense em imagens JPEG, vídeos x264 e assim por diante. Especialmente desde que você queira reconstruir seu arquivo original exatamente (isto é, bit por bit) você precisa de uma compressão sem perdas . ¹

O motivo dessa compactação limitada é declarado neste artigo da Wikipedia sobre Entropy que quantifica o valor esperado da informação contida em uma mensagem :

Entropy effectively bounds the performance of the strongest lossless (or nearly lossless) compression possible, which can be realized in theory by using the typical set or in practice using Huffman, Lempel-Ziv or arithmetic coding. (...)

¹ A "compressão" muito strong de imagens JPEG só é possível, pois algumas informações são descartadas (de uma maneira que o olho humano não pode reconhecê-lo à primeira vista; com perdas compressão ).