Como a compactação de arquivos funciona?

Então, eu percebi hoje que tomo como garantida a compactação de arquivos. A capacidade de agrupar alguns arquivos em um e ter um tamanho menor do que qualquer um deles é algo que eu apenas aceito como um fato, mas como ele realmente funciona?

Eu tenho um conhecimento limitado disso, que inclui algo a ver com a substituição de todas as entradas duplicadas por ponteiros, para diminuir dessa maneira, mas além disso, eu sou bastante ignorante!

Como estou sempre aberto a novos conhecimentos, como imagino que a maioria de nós esteja aqui, pensei em perguntar. Então, superusuário, como a compactação realmente funciona?

Compressão sem perdas

A compactação sem perdas é onde nenhum dado é perdido. Tudo o que é inserido pode ser recuperado perfeitamente. Isso funciona bem para arquivos de texto ou binários nos quais o menor erro será percebido.

A compactação de arquivos funciona pegando o arquivo e procurando padrões, e convertendo esses padrões em outra coisa que ocupa menos espaço.

Por exemplo, "AAAAAAAA" pode ser transformado em "8A".

É verdade que não é assim que funciona exatamente porque você tem o problema e se "8A" estivesse no texto simples. Você descompactaria o arquivo e ele estaria errado. Um bom lugar para começar é a Wikipedia ou o algoritmo de compactação de dados LZW .

Existe algum código psuedo para isso, copiado abaixo:

STRING = get input character
WHILE there are still input characters DO
    CHARACTER = get input character
    IF STRING+CHARACTER is in the string table then
        STRING = STRING+character
    ELSE
        output the code for STRING
        add STRING+CHARACTER to the string table
        STRING = CHARACTER
    END of IF
END of WHILE
output the code for STRING

Toda compactação usa um dicionário de pesquisa que é usado para compactar e descompactar o arquivo. Quanto maior o dicionário, mais você pode compactá-lo, embora se depare com a Lei dos Retornos Diminutos .

Também é importante notar que a compactação nem sempre gera um arquivo menor. Existem situações (com arquivos pequenos ou ao compactar dados aleatórios ) em que você não obterá um arquivo menor após a compactação. Houve alguns desafios divertidos relacionados à capacidade de compactar dados aleatórios.

"Compressão com perda

O acima mencionado refere-se principalmente à compactação sem perdas . Outros tipos de compactação usados ​​em aplicativos de vídeo / áudio como MP3, JPG e h.264 são exemplos de compactação com perda .

A compactação com perdas funciona descartando dados com menor probabilidade de serem notados. No áudio, isso soa cerca de 30.000 Hrz e abaixo de 100 Hrz, junto com outras coisas. Na imagem (estática), ele remove várias coisas e mescla pixels, juntamente com o descarte de dados.

A compactação com perdas é uma forma de codificação de transformação . Ele calcula a média dos dados para reduzir o tamanho geral. Por exemplo, um bloco de 10 pixels em uma imagem, todas as cores ligeiramente diferentes podem ser mescladas em uma cor e, assim, compactadas.

Na compactação de vídeo, muitas vezes as instruções são colocadas para redesenhar pixels que foram alterados desde o último quadro ou quadro-chave .

A compactação funciona encontrando padrões nos dados e substituindo-os por padrões menores especiais. A descompressão é o inverso: encontre os padrões especiais e substitua-os pelos padrões maiores que eles representam. Saber que padrões são prováveis ​​é importante; por exemplo, os padrões encontrados no texto podem ser bem diferentes dos encontrados nas imagens. Algumas técnicas de compressão são com perdas; eles não garantem que a expansão recupere exatamente a entrada. Isso geralmente é bom para dados analógicos, como músicas e imagens, se a perda for pequena o suficiente. Mas dados como texto devem ser compactados com técnicas sem perdas.

É importante perceber que é impossível compactar, sem perda, dados aleatórios por um único bit. Considere um arquivo com N bits de dados binários. Existem 2 ^ N arquivos possíveis. Se você compactar qualquer um desses arquivos por um único bit, para que o arquivo compactado tenha tamanho N-1 bits, haverá apenas 2 ^ (N-1) possíveis representações compactadas. Em outras palavras, cada arquivo compactado possível deve representar mais de um arquivo não compactado possível. Sem uma representação compactada exclusiva, o algoritmo de descompressão não pode garantir a descompressão sem perdas.