Como funciona a compactação de arquivos?

Question

Então, percebi que hoje considero a compactação de arquivos como certa. A capacidade de agrupar alguns arquivos em um, e fazer com que ele seja menor do que qualquer um deles, é algo que eu aceito como fato, mas como ele realmente funciona?

Eu tenho um conhecimento limitado sobre isso, o que inclui alguma coisa a ver com a substituição de todas as entradas duplicadas por ponteiros, para encolher dessa maneira, mas além disso eu sou razoavelmente sem noção!

Como estou sempre aberto a novos conhecimentos, como imagino que a maioria de nós é aqui, pensei em perguntar. Então, SuperUser, como funciona a compressão ?

    

Answer 1

Compressão sem perdas

Compressão sem perdas é quando nenhum dado é perdido. Tudo o que é digitado pode ser recuperado perfeitamente. Isso funciona bem para arquivos de texto ou binários onde o menor erro será notado.

A compactação de arquivos funciona pegando o arquivo e digitalizando padrões, e traduzindo esses padrões em algo que ocupa menos espaço.

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

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

Existe algum código simplesmente psuedo para este 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 a 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 você se deparar com a Lei dos retornos decrescentes .

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 ) 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 perdas"

Acima, a maioria diz respeito à 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 perdas .

A compactação com perdas funciona descartando dados com menor probabilidade de serem percebidos. Em áudio, isso soa a cerca de 30.000 Hrz e abaixo de 100 Hrz, juntamente com várias outras coisas. Na imagem (estática), ele remove várias coisas e mescla os pixles, juntamente com os dados descartados.

A compactação com perdas é uma forma de transformar a codificação . 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, portanto, compactadas.

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

    

Answer 2

A compactação funciona localizando padrões nos dados e substituindo esses padrões por padrões menores e especiais. A descompressão é o inverso: encontre os padrões especiais e substitua-os pelos padrões maiores que eles representam. Saber quais padrões são prováveis é importante; por exemplo, os padrões encontrados no texto podem ser bem diferentes daqueles encontrados nas imagens. Algumas técnicas de compactação são com perdas; eles não garantem que a expansão recuperará exatamente a entrada. Isso geralmente é bom para dados analógicos, como música 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 comprimir, 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 descompactado possível. Sem uma representação compactada exclusiva, o algoritmo de descompactação não pode garantir a descompressão sem perdas.