Existe um máximo conhecido de quanto uma cadeia de 0 e 1 pode ser compactada?

Há muito tempo, li um artigo de jornal em que algum tipo de professor disse que, no futuro, poderemos comprimir dados em apenas dois bits (ou algo assim).

É claro que isso não está correto (e pode ser que minha memória do que ele exatamente tenha declarado não esteja correta). Compreensivelmente, não seria prático compactar qualquer sequência de 0 e 1 para apenas dois bits porque (mesmo que fosse tecnicamente possível), muitos tipos diferentes de cadeias acabariam comprimindo para os mesmos dois bits (já que temos apenas 01 'e' 10 'para escolher).

Enfim, isso me fez pensar sobre a viabilidade de compactar uma sequência arbitrária de 0 e 1 de acordo com algum esquema. Para esse tipo de string, existe uma relação conhecida entre o comprimento da string (a relação entre 0 e 1 provavelmente não importa) e a compressão máxima?

Em outras palavras, existe uma maneira de determinar qual é o comprimento mínimo (menor possível) em que uma cadeia de 0 e 1 pode ser compactada?

(Aqui estou interessado na compressão máxima matemática, não no que é tecnicamente possível no momento.)

A complexidade de Kolmogorov é uma abordagem para formalizar isso matematicamente. Infelizmente, calcular a complexidade de Kolmogorov de uma string é um problema incontestável. Consulte também: Aproximando a complexidade de Kolmogorov .

É possível obter melhores resultados se você analisar a origem da string em vez da própria string . Em outras palavras, frequentemente a fonte pode ser modelada como um processo probabilístico, que escolhe aleatoriamente uma string de alguma forma, de acordo com alguma distribuição. A entropia dessa distribuição indica a matematicamente a melhor compressão possível (até uma pequena constante aditiva).

Sobre a impossibilidade de compactação perfeita, você também pode estar interessado no seguinte.

• Nenhum algoritmo de compactação pode compactar todas as mensagens de entrada?
• As funções de compactação são práticas apenas porque "as cadeias de bits que ocorrem na prática estão longe de serem aleatórias"?
• Existe algum algoritmo de compressão ideal teoricamente comprovado?

Para qualquer string, existe um esquema de compactação que a comprime na string vazia. Portanto, não faz sentido perguntar quanto uma única string pode ser compactada, mas sim quanto uma coleção (ou distribuição ) de strings pode ser compactada, em média. Em geral, dada uma coleção de strings, qualquer esquema de compactação precisa de pelo menos bits ou mais para codificar uma string da coleção no pior caso.log 2$N$$\log_2 N$

Além disso, em muitos casos, não nos preocupamos com a reconstrução exata . Isso se chama compressão com perdas e é assim que as músicas e vídeos são compactados. Nesse caso, o limite inferior indicado acima não se mantém, mas você pode criar outros limites inferiores.

Aqui está um esquema simples que pode comprimir seqüências de bits arbitrárias sem perdas, com o menor resultado sendo apenas um bit:

Se a string for uma correspondência idêntica para a gravação da 9ª sinfonia de Beethoven, quarto movimento, no formato AAC armazenado no disco rígido do meu computador, a saída será um único bit '0'.

Se a string for qualquer outra coisa, a saída será um único bit '1', seguida por uma cópia idêntica da string original.

Esse esquema reduz uma entrada possível para exatamente um bit e aumenta todas as outras entradas em comprimento. Existe um princípio geral: se um algoritmo de compactação pode mapear qualquer sequência de entrada para uma sequência compactada, e existe um algoritmo de descompressão correspondente que mapeia qualquer sequência compactada de volta para a sequência original e o algoritmo de compactação mapeia qualquer entrada para uma sequência mais curta, então ele deve mapear algumas cadeias de entrada para cadeias mais longas.

Para cada esquema de compactação que você criar, é possível produzir dados que não serão compactados por ele. Portanto, mesmo que seu esquema de compactação seja muito eficiente com alguns tipos de dados, ele nunca será compactado consistentemente até uma determinada proporção.

A maneira de produzir um exemplo de dados não compactáveis ​​para um algoritmo de compactação específico é simples: pegue qualquer tipo de dados e execute-o repetidamente no algoritmo de compactação, até que o tamanho não diminua mais.

Portanto, a compressibilidade de uma sequência de bits não é realmente uma função do comprimento da sequência, mas de sua complexidade em relação ao algoritmo de compactação.

Existe um algoritmo interessante e completamente diferente que é usado pelos sistemas de backup corporativo. A idéia é que, se você tiver uma empresa com 10.000 computadores, muitos desses computadores conterão muitos arquivos idênticos. Por exemplo, um email enviado a todos na empresa pode acabar como um arquivo idêntico em cada disco rígido.

Portanto, um sistema de backup que tenta fazer backup de um arquivo deve obviamente tentar compactá-lo para economizar espaço, mas primeiro o sistema de backup verifica se um arquivo absolutamente idêntico já foi salvo! Portanto, em vez de fazer backup de qualquer coisa , tudo o que o sistema de backup faz é, por exemplo, lembrar que você tem o número de arquivo 1.487.578 no sistema de backup no disco rígido.

Isso é especialmente eficiente, por exemplo, quando 10.000 usuários têm sistemas operacionais e aplicativos idênticos instalados. Para usuários únicos, não é muito útil.