Esta é uma tradução automática e o texto em inglês é o original. Ler o original
Nenhum compressor consegue reduzir todos os ficheiros, e a demonstração ocupa um parágrafo
De poucos em poucos anos, alguém anuncia um algoritmo que comprime qualquer ficheiro em 50%. Aplicado duas vezes, comprimiria qualquer ficheiro a um quarto, e aplicado vezes suficientes, a um único bit.
Considere todos os ficheiros possíveis de exatamente 1 000 bits. Existem 2¹⁰⁰⁰ desses ficheiros. Considere agora todos os ficheiros possíveis mais curtos do que isso — 999 bits, 998, e assim sucessivamente até zero. Somando todos esses ficheiros, obtêm-se 2¹⁰⁰⁰ − 1 ficheiros, menos um do que no início.
Um compressor sem perdas tem de mapear entradas distintas em saídas distintas, caso contrário não conseguiria inverter o processo. No entanto, não é possível colocar 2¹⁰⁰⁰ elementos em 2¹⁰⁰⁰ − 1 caixas sem colocar dois na mesma caixa. Portanto, nenhum compressor sem perdas reduz todas as entradas. Se reduz algumas, tem de expandir outras.
Não foram necessárias quaisquer suposições sobre o algoritmo, pelo que nenhuma engenhosidade o consegue contornar. Trata-se do princípio da casa dos pombos, e é por isso que qualquer compressor real tem um pior caso em que a saída é ligeiramente maior do que a entrada: o original mais alguns bytes de cabeçalho.
O que está, afinal, a ser explorado
Estrutura. A compressão não remove a "redundância" num sentido vago; reatribui os códigos curtos aos elementos que ocorrem com frequência.
O texto em inglês é extremamente previsível. A seguir a "th", a letra seguinte é esmagadoramente "e". Os espaços são o carácter mais comum. Uma imagem de uma parede tem longas sequências de pixéis quase idênticos. Em cada um dos casos, o ficheiro, considerado como uma variável aleatória, apresenta uma entropia baixa — a surpresa média por símbolo é pequena — e Shannon demonstrou em 1948 que essa quantidade é o limite mínimo exato. Não é possível codificar uma fonte com menos bits por símbolo do que a sua entropia, e é sempre possível ficar arbitrariamente próximo desse limite.
O que transforma a compressão numa competição de previsão. Um compressor que modele bem a fonte atribui códigos curtos com precisão e aproxima-se da entropia. Um compressor que a modele mal desperdiça bits. É por isso que o estado da arte na compressão de texto se assemelha cada vez mais a um modelo de linguagem: prever bem o símbolo seguinte e comprimir bem são o mesmo problema com roupagens diferentes.
É possível observar a aproximação a esse limite na ferramenta Entropy Coding, e ver a própria atribuição de códigos em Huffman Encoding.
Por que razão comprimir um zip não faz nada
De um ficheiro bem comprimido foi removida a sua estrutura. O que resta assemelha-se, estatisticamente, a ruído: todos os símbolos são sensivelmente igualmente prováveis, sem correlações úteis entre vizinhos. A sua entropia por bit é próxima de 1, pelo que não resta nada para explorar, e uma segunda passagem irá tipicamente torná-lo muito ligeiramente maior — o cabeçalho, somado à incapacidade do compressor para encontrar qualquer padrão digno de codificação.
O mesmo explica por que razão um JPEG num arquivo ZIP quase não reduz de tamanho, por que razão os dados cifrados são incompressíveis (uma boa cifragem é concebida especificamente para se parecer com ruído) e por que razão comprimir antes de cifrar é a ordem correta — depois disso, não há nada para comprimir.
A versão honesta de "50% mais pequeno"
Todas as alegações verdadeiras sobre compressão são alegações relativas a uma classe de entradas. "Reduz para metade o tamanho de prosa em inglês" é uma afirmação real e útil. "Reduz para metade o tamanho de qualquer ficheiro" é comprovadamente falso, e a demonstração é o parágrafo no topo.
Onde a compressão com perdas é algo totalmente diferente
Nada disto limita a compressão com perdas, uma vez que esta não tem de ser reversível. O JPEG, o MP3 e todos os codecs de vídeo descartam informação deliberadamente, escolhendo o que perder através de modelos do que os olhos e ouvidos humanos não conseguem notar.
Isso altera a questão de "quanta estrutura existe" para "quanto se pode descartar antes de alguém se queixar", o que é uma questão de perceção e não de matemática. É também por isso que a relação de compromisso na compressão com perdas tem um botão de ajuste e a compressão sem perdas não: a entropia é um facto relativo aos dados, mas a distorção aceitável é um juízo de valor sobre o público.
O único aspeto que ambas partilham é que a especificação honesta é sempre condicional. Um compressor sem perdas é bom para uma classe de entradas. Um compressor com perdas é bom para uma dada distorção.