Como funciona a compactação de arquivos?

Os engenheiros de software sempre desenvolveram novas maneiras de ajustar muitos dados em um espaço pequeno. Era verdade quando nossos discos rígidos eram minúsculos e o advento da Internet acabou de torná-los mais críticos. A compactação de arquivos desempenha um grande papel em nos conectar, permitindo-nos enviar menos dados ao longo da linha, para que possamos fazer downloads mais rápidos e colocar mais conexões em redes ocupadas.

Então, como isso funciona?

Responder a essa pergunta envolveria explicar algumas matemáticas muito complicadas, certamente mais do que podemos cobrir neste artigo, mas você não precisa entender precisamente como funciona matematicamente para entender o básico.

As bibliotecas mais populares para compactar texto contam com dois algoritmos de compactação, usando os dois ao mesmo tempo para atingir taxas de compactação muito altas. Esses dois algoritmos são “LZ77” e “codificação Huffman”. A codificação de Huffman é bastante complicada e não entraremos em detalhes sobre ela aqui. Primeiramente, ele usa matemática sofisticada para atribuir códigos binários mais curtos  a letras individuais, reduzindo o tamanho dos arquivos no processo. Se você quiser saber mais sobre isso, consulte este artigo  sobre como o código funciona ou este explicador da Computerphile .

LZ77, por outro lado, é relativamente simples e é sobre o que falaremos aqui. Visa remover palavras duplicadas e substituí-las por uma “chave” menor que representa a palavra.

Veja este pequeno texto, por exemplo:

O algoritmo LZ77 iria olhar para este texto, perceber que ele repete “howtogeek” três vezes e alterá-lo para este:

Então, quando quiser ler o texto de volta, ele substituirá todas as ocorrências de (h) por “howtogeek”, nos trazendo de volta à frase original.

Chamamos essa compactação de “sem perdas” – os dados que você insere são iguais aos dados que obtém. Nada está perdido.

Na realidade, LZ77 não usa uma lista de chaves, mas substitui a segunda e a terceira ocorrência por um link de volta na memória:

Portanto, agora, quando chegar a (h), ele irá olhar para trás em “howtogeek” e ler isso.

Se você estiver interessado em uma explicação mais detalhada, este vídeo da Computerphile é muito útil.

Agora, este é um exemplo idealizado. Na realidade, a maior parte do texto é compactada com teclas tão pequenas quanto alguns caracteres. Por exemplo, a palavra “o” seria compactada mesmo quando aparecesse em palavras como “lá”, “deles” e “então”. Com o texto repetido, você pode obter algumas taxas de compressão absurdas. Pegue este arquivo de texto com a palavra “howtogeek” repetida 100 vezes. O arquivo de texto original tem três kilobytes de tamanho. Quando compactado, porém, ocupa apenas 158 bytes. Isso é quase 95% de compressão.

Obviamente, esse é um exemplo extremo, já que repetimos a mesma palavra indefinidamente. Na prática geral, você provavelmente obterá cerca de 30-40% de compactação usando um formato de compactação como ZIP em um arquivo que contém principalmente texto.

Este algoritmo LZ77 se aplica a todos os dados binários, a propósito, e não apenas ao texto, embora o texto geralmente seja mais fácil de compactar devido ao número de palavras repetidas que a maioria dos idiomas usa. Um idioma como o chinês pode ser um pouco mais difícil de compactar do que o inglês, por exemplo.

Como funciona a compactação de imagem e vídeo?

A compressão de vídeo e áudio funciona de maneira muito diferente. Ao contrário do texto, onde você pode ter compactação sem perdas e nenhum dado é perdido, com imagens, temos o que é chamado de “compactação com perdas”, onde você perde alguns dados. E quanto mais você compacta, mais dados você perde.

Isso é o que leva a aqueles JPEGs de aparência horrível que as pessoas carregaram, compartilharam e capturaram várias vezes. Cada vez que a imagem é compactada, ela perde alguns dados.

Aqui está um exemplo. Esta é uma captura de tela que tirei e não foi compactada.

Em seguida, tirei essa captura de tela e a executei várias vezes no Photoshop, sempre exportando-a como JPEG de baixa qualidade. Aqui está o resultado.

Parece muito ruim, certo?

Bem, este é apenas o pior cenário, exportando com qualidade JPEG de 0% todas as vezes. Para comparação, aqui está um JPEG de qualidade de 50%, que é quase indistinguível da imagem PNG de origem, a menos que você a amplie e dê uma olhada mais de perto.

O PNG desta imagem tinha 200 KB, mas este JPEG de 50% de qualidade tem apenas 28 KB.

Então, como isso economiza tanto espaço? Bem, o algoritmo JPEG é uma façanha de engenharia. A maioria das imagens armazena uma lista de números, com cada número representando um único pixel.

JPEG não faz nada disso. Em vez disso, ele armazena imagens usando algo chamado Discrete Cosine Transform , que é uma coleção de ondas sinusoidais adicionadas em intensidades variáveis. Ele usa 64 equações diferentes, mas a maioria delas não é usada. Isso é o que o controle deslizante de qualidade para JPEG no Photoshop e outros aplicativos de imagem faz – escolher quantas equações usar. Os aplicativos então usam a codificação Huffman para reduzir o tamanho do arquivo ainda mais.

Isso dá aos JPEGs uma taxa de compactação insanamente alta, que pode reduzir um arquivo de vários megabytes a alguns kilobytes, dependendo da qualidade. Claro, se você usar muito, você acaba com o seguinte:

Essa imagem é horrível. Mas pequenas quantidades de compactação JPEG podem ter um impacto significativo no tamanho do arquivo, e isso torna o JPEG muito útil para compactação de imagens em sites. A maioria das fotos que você vê online são compactadas para economizar no tempo de download, especialmente para usuários móveis com conexões de dados ruins. Na verdade, todas as imagens do How-To Geek foram compactadas para tornar o carregamento da página mais rápido e você provavelmente nunca percebeu.

Compressão de Vídeo

O vídeo funciona um pouco diferente das imagens. Você pensaria que eles apenas compactariam cada quadro de vídeo usando JPEG, e certamente fazem isso, mas há um método melhor para vídeo.

Usamos algo chamado “compressão interframe”, que calcula as mudanças entre cada quadro e apenas as armazena. Então, por exemplo, se você tiver uma tomada relativamente estática que ocupa vários segundos em um vídeo, muito espaço é economizado porque o algoritmo de compressão não precisa armazenar todas as coisas na cena que não mudam. A compressão entre quadros é a principal razão de termos TV digital e vídeo na web. Sem ele, os vídeos teriam centenas de gigabytes, mais do que o tamanho médio do disco rígido em 2005, quando o YouTube foi lançado.

Além disso, como a compactação entre quadros funciona melhor com vídeo principalmente estático, é por isso que o confete prejudica a qualidade do vídeo .

Nota: GIF não faz isso, é por isso que GIFs animados são geralmente muito curtos e pequenos, mas ainda têm um tamanho de arquivo muito grande.

Outra coisa a se ter em mente sobre o vídeo é sua taxa de bits – a quantidade de dados permitida a cada segundo. Se sua taxa de bits for de 200 kb / s, por exemplo, seu vídeo ficará muito ruim. A qualidade aumenta conforme a taxa de bits aumenta, mas depois de alguns megabytes por segundo, você obtém retornos decrescentes.

Este é um quadro ampliado obtido de um vídeo de uma água-viva. O da esquerda está a 3 Mb / s, e o da direita está a 100 Mb / s.

Um aumento de 30x no tamanho do arquivo, mas não muito aumento na qualidade. Geralmente, os vídeos do YouTube ficam em torno de 2 a 10 Mb / s dependendo da sua conexão, pois qualquer coisa a mais provavelmente não seria notada.

Esta demonstração funciona melhor com o vídeo real, então se você quiser dar uma olhada por si mesmo, pode baixar os mesmos vídeos de teste de taxa de bits usados ​​aqui.

Compressão de Áudio

A compressão de áudio funciona de forma muito semelhante à compressão de texto e imagem. Enquanto o JPEG remove detalhes de uma imagem que você não verá, a compactação de áudio faz o mesmo com os sons. Talvez você não precise ouvir o rangido da palheta da guitarra na corda se a guitarra real estiver muito, muito mais alta.

MP3 também usa taxa de bits, variando de 48 e 96 kbps (o limite inferior) a 128 e 240 kbps (muito bom) a 320 kbps (áudio de alta qualidade), e provavelmente você só ouvirá a diferença com fones de ouvido excepcionalmente bons ( e orelhas).

Existem também codecs de compressão sem perdas para áudio – o principal é o FLAC – que usa codificação LZ77 para fornecer áudio totalmente sem perdas. Algumas pessoas juram pela qualidade de áudio perfeita do FLAC, mas com a prevalência do MP3, parece que a maioria das pessoas não consegue perceber ou não se importa com a diferença.