Compressão sem perda

Algoritmos de compressão de dados sem perda não podem garantir compressão para todos os conjuntos de dados de entrada. Em outras palavras, para qualquer algoritmo de compressão de dados sem perdas, haverá um conjunto de dados de entrada que não fica menor quando processado pelo algoritmo, e para qualquer algoritmo de compressão de dados sem perdas que torna pelo menos um arquivo menor, haverá pelo menos um arquivo que ele torna maior. Isto é facilmente comprovado com matemática elementar usando um argumento de contagem, como se segue:

• Conteça que cada arquivo é representado como uma seqüência de bits de algum comprimento arbitrário.
• Ponha que existe um algoritmo de compressão que transforma cada arquivo em um arquivo de saída que não seja mais longo que o arquivo original, e que pelo menos um arquivo será comprimido em um arquivo de saída que seja mais curto que o arquivo original.
• Deixe M ser o menor número de forma que exista um arquivo F com bits M de comprimento que comprima para algo mais curto. Deixe N ser o comprimento (em bits) da versão comprimida de F.
• li> porque N<M, todo arquivo de comprimento N mantém seu tamanho durante a compressão. Existem 2N tais arquivos possíveis. Juntamente com F, isto faz com que 2N+1 arquivos que comprimem todos em um dos arquivos 2N de comprimento N.
• mas 2N é menor que 2N+1, então pelo princípio do buraco do pombo deve haver algum arquivo de comprimento N que é 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 render?), o que contradiz a suposição de que o algoritmo foi sem perdas.
• Devemos portanto concluir que nossa hipótese original (que a função de compressão não faz mais arquivo) é necessariamente falsa.

Um algoritmo de compressão sem perdas que faz alguns arquivos mais curtos deve necessariamente fazer alguns arquivos mais longos, mas não é necessário que esses arquivos fiquem muito mais longos. A maioria dos algoritmos de compressão práticos fornecem uma facilidade de “escape” que pode desligar a codificação normal para arquivos que se tornariam mais longos ao serem codificados. Em teoria, apenas um bit adicional é necessário para dizer ao descodificador que a codificação normal foi desligada para toda a entrada; no entanto, a maioria dos algoritmos de codificação usa pelo menos um byte completo (e tipicamente mais do que um) para este propósito. Por exemplo, arquivos compactados deflacionados nunca precisam crescer mais de 5 bytes por 65.535 bytes de entrada.

Na verdade, se considerarmos arquivos de comprimento N, se todos os arquivos fossem igualmente prováveis, então para qualquer compressão sem perdas que reduza o tamanho de algum arquivo, o comprimento esperado de um arquivo compactado (com média sobre todos os possíveis arquivos de comprimento N) deve necessariamente ser maior que N. Então se não sabemos nada sobre as propriedades dos dados que estamos compactando, podemos muito bem não comprimi-los de forma alguma. Um algoritmo de compressão sem perdas só é útil quando temos mais probabilidade de comprimir certos tipos de arquivos do que outros; então o algoritmo poderia ser projetado para comprimir melhor esses tipos de dados.

Assim, a principal lição do argumento não é que se arrisca grandes perdas, mas apenas que não se pode ganhar sempre. Escolher um algoritmo significa sempre implicitamente seleccionar um subconjunto de todos os ficheiros que se tornarão mais curtos de forma útil. Esta é a razão teórica pela qual precisamos ter diferentes algoritmos de compressão para diferentes tipos de arquivos: não pode haver nenhum algoritmo que seja bom para todos os tipos de dados.

O “truque” que permite algoritmos de compressão sem perdas, usados no tipo de dados para os quais foram desenhados, para comprimir consistentemente tais ficheiros para uma forma mais curta é que os ficheiros que os algoritmos são desenhados para actuar em todos têm alguma forma de redundância facilmente modelável que o algoritmo é desenhado para remover, e assim pertencem ao subconjunto de ficheiros que esse algoritmo pode tornar mais curto, enquanto outros ficheiros não seriam comprimidos ou até mesmo maiores. Algoritmos são geralmente muito especificamente ajustados a um tipo particular de arquivo: por exemplo, programas de compressão de áudio sem perdas não funcionam bem em arquivos de texto, e vice versa.

Em particular, arquivos de dados aleatórios não podem ser consistentemente comprimidos por qualquer algoritmo de compressão de dados sem perdas concebível: de fato, este resultado é usado para definir o conceito de aleatoriedade na teoria da complexidade algorítmica.

É provavelmente impossível criar um algoritmo que possa comprimir sem perdas qualquer dado. Embora tenha havido muitas reivindicações ao longo dos anos de empresas alcançando “compressão perfeita” onde um número arbitrário N de bits aleatórios pode sempre ser comprimido para N – 1 bits, este tipo de reivindicações podem ser descartadas com segurança sem sequer olhar para mais detalhes sobre o suposto esquema de compressão. Tal algoritmo contradiz as leis fundamentais da matemática porque, se existisse, ele poderia ser aplicado repetidamente para reduzir sem perdas qualquer arquivo a tamanho 0. Alegadamente, algoritmos de compressão “perfeitos” são muitas vezes referidos ironicamente como algoritmos de compressão “mágicos” por esta razão.

Por outro lado, também foi provado que não há algoritmo para determinar se um arquivo é incompressível no sentido da complexidade de Kolmogorov. Assim é possível que qualquer ficheiro em particular, mesmo que pareça aleatório, possa ser significativamente comprimido, mesmo incluindo o tamanho do descompressor. Um exemplo são os dígitos da constante matemática pi, que parecem aleatórios mas podem ser gerados por um programa muito pequeno. No entanto, mesmo que não se possa determinar se um determinado arquivo é incompressível, um simples teorema sobre strings incompressíveis mostra que mais de 99% dos arquivos de qualquer comprimento não podem ser comprimidos por mais de um byte (incluindo o tamanho do descompressor).

Fundo matemáticoEditar

Abstractamente, um algoritmo de compressão pode ser visto como uma função em seqüências (normalmente de octetos). A compressão é bem sucedida se a sequência resultante for menor do que a sequência original (e as instruções para o mapa de descompressão). Para um algoritmo de compressão ser sem perdas, o mapa de compressão deve formar uma injeção de sequências de bits “simples” a “comprimidas”.

O princípio do pombinho proíbe uma bijeção entre a coleção de sequências de comprimento N e qualquer subconjunto da coleção de sequências de comprimento N-1. Portanto, não é possível produzir um algoritmo sem perdas que reduza o tamanho de cada seqüência de entrada possível.

Pontos de aplicação na teoria de compressão realEditar

Concebedores de algoritmos de compressão real aceitam que fluxos de alta entropia de informação não podem ser comprimidos e, portanto, incluem facilidades para detectar e manipular esta condição. Uma forma óbvia de detecção é aplicar um algoritmo de compressão bruta e testar se a sua saída é menor que a sua entrada. Às vezes, a detecção é feita por heurística; por exemplo, uma aplicação de compressão pode considerar arquivos cujos nomes terminam em “.zip”, “.arj” ou “.lha” não compressível sem nenhuma detecção mais sofisticada. Uma forma comum de lidar com esta situação é citando a entrada, ou partes nãopressíveis da entrada na saída, minimizando a sobrecarga de compressão. Por exemplo, o formato de dados zip especifica o ‘método de compressão’ de ‘Stored’ para arquivos de entrada que foram copiados para o arquivo verbatim.

The Million Random Digit ChallengeEdit

Mark Nelson, em resposta às reivindicações de algoritmos mágicos de compressão que aparecem na comp.Compressão, construiu um arquivo binário de 415.241 bytes de conteúdo altamente entropic, e lançou um desafio público de $100 para qualquer um escrever um programa que, junto com sua entrada, seria menor do que os dados binários fornecidos, mas ainda assim seria capaz de reconstituí-lo sem erros.

O FAQ do comp.compression newsgroup contém um desafio de Mike Goldman oferecendo $5.000 para um programa que pode comprimir dados aleatórios. Patrick Craig aceitou o desafio, mas ao invés de comprimir os dados, ele os dividiu em arquivos separados, todos os quais terminaram no número 5, que não foi armazenado como parte do arquivo. Omitir este caracter permitiu que os arquivos resultantes (mais, de acordo com as regras, o tamanho do programa que os remontou) fossem menores do que o arquivo original. No entanto, não houve compressão real e as informações armazenadas nos nomes dos arquivos foram necessárias para remontá-los na ordem correta no arquivo original, e essas informações não foram levadas em conta na comparação do tamanho do arquivo. Assim, os próprios arquivos não são suficientes para reconstituir o arquivo original; os nomes dos arquivos também são necessários. Patrick Craig concordou que não houve compressão significativa, mas argumentou que a redação do desafio não exigia isso. Um histórico completo do evento, incluindo discussão sobre se o desafio foi ou não tecnicamente cumprido, está no website de Patrick Craig.