Entropia: o limite que o Universo impõe à compressão de arquivos

_{Texto: Bruno Vaiano | Design: Juliana Krauss}

Era uma vez o código Morse. Nele, letras e números se tornam sequências de pontos e traços transmitidos por um fio. Os pontos são representados por um pulso elétrico breve e os traços por um pulso mais longo. Para mandar uma mensagem por esse WhatsApp do século 19, bastava ligar e desligar o interruptor do telégrafo, que permitia ou interrompia a passagem da corrente. Essa forma de comunicação minimalista, equivalente a acender e apagar uma lâmpada, revolucionou as telecomunicações.

O código Morse já nasceu com um meio pioneiro de compressão de arquivo, já que as letras mais comuns do inglês ganharam os sinais mais curtos. Por exemplo: o “e”, que corresponde a 12,4% de um texto na língua de Shakespeare, em média, passou a ser representado por um único ponto. Enquanto isso, o “z”, que é raríssimo (0,09%), exige a sequência traço-traço-ponto-ponto. A ideia, claro, é otimizar o tempo de digitação.

Esse alfabeto se baseia no mesmo princípio por trás de alguns dos primeiros algoritmos de compactação de arquivo, criados muito antes da existência de computadores como os conhecemos: a codificação de Shannon-Fano (de 1948) e sua versão aperfeiçoada, a codificação de Huffman (de 1952). Elas partem da premissa de que, se você está tentando diminuir o tamanho de uma sequência de símbolos qualquer – como, por exemplo, letras –, o mais lógico é atribuir códigos menores aos símbolos mais comuns. 

A capacidade de diminuir o tamanho de um arquivo sem mexer na informação contida lá dentro (ou, pelo menos, sem mexer perceptivelmente) soa como uma minúcia técnica, destinada a economizar espaço em servidores ou acelerar o carregamento de fotos em páginas na internet.

Mas, ao longo do século 21, ela transbordou para muito além da bolha dos programadores: permitiu distribuir músicas e filmes piratas online, um incêndio na indústria do entretenimento que culminou com os serviços de streaming atuais e moldou a maneira como consumimos áudio e vídeo para sempre. Nas próximas páginas, vamos entender a longa trilha que leva de Morse e Huffman ao MP3.

O código binário

Toda a ciência da computação, até hoje, gira em torno do mesmo princípio básico do código Morse. Não importa quão complexo seja um arquivo ou programa, ele pode ser representado, em última instância, por uma sequência de dois dígitos diferentes: zeros e uns. É o código binário. 

Você pode pensar nesses zeros e uns como pontos e traços, como um interruptor ligado ou desligado ou até como duas bases nitrogenadas de DNA. A representação física não interessa. O importante é que haja dois estados possíveis.  

Filosoficamente, uma escolha entre duas possibilidades é o dado mais simples que pode existir; a resposta mais curta possível para uma pergunta. Sim ou não. Por isso, essa se tornou a unidade básica para medir informação, batizada de bit. O nome é a abreviação de “dígito binário”, binary digit.

Comunicar o resultado de um lançamento de moeda, cara ou coroa, exige apenas um bit. Quando os gregos precisaram transmitir à cidade-estado de Micenas a notícia de que haviam vencido Troia, a solução foi uma sequência de fogueiras distribuídas em fila ao longo de 600 km. Fogueira acesa significava “vitória”, fogueira apagada, “derrota”. As fogueiras se acenderam, uma a uma, transmitindo um bit solitário pelo maior telefone sem fio da Antiguidade. 

Bits são uma ideia poderosa porque é possível escrever qualquer quantidade de informação na forma de uma sequência de perguntas de sim ou não, representada por uma longa fileira de zeros e uns. Os telegrafistas já faziam isso quando convertiam para o código Morse mensagens que usam um alfabeto de 26 letras, e nossos computadores fazem isso todos os dias quando salvam textos, fotos e vídeos em seus HDs (no disco rígido, cada bit é representado por uma minúscula região de um ímã, cuja polaridade pode ser norte ou sul). 

O autor dessa ideia – a ideia fundadora do mundo como você o conhece – foi o engenheiro Claude Shannon. Ele trabalhava no Bell Labs, a divisão de pesquisa da empresa de telefonia AT&T, e embora sua dissertação de mestrado seja um dos documentos mais importantes da história da ciência, Shannon permanece sumido do imaginário popular. 

Com o conceito de bit na cabeça, demos o primeiro passo na explicação de como nossos computadores espremem arquivos. Para dar o próximo, precisamos mergulhar no trabalho de Shannon: o número de bits importa, mas a maneira como eles estão organizados importa muito mais.

Entropia

Em um vídeo do canal do YouTube Computerphile, o professor da Universidade de Nottingham Tim Muller explica que a quantidade de informação embutida em um acontecimento tem a ver com o quanto ele é surpreendente. Vamos explicar.

Você já sabe que o lançamento de uma moeda contém 1 bit de informação. Se você lançar duas moedas e acertar cara ou coroa em ambas, ficará ainda mais surpreso: são 2 bits. 

A maior parte dos acontecimentos não é simples como um round de cara ou coroa. Eles envolvem cenários complexos, como a chance de ganhar prêmios parciais ou totais na loteria. Por isso, há uma fórmula para calcular quanta informação está contida em um evento qualquer. 

Primeiro, você divide 1 pela probabilidade de que algo aconteça. No caso da moeda, por exemplo, temos 1 ÷ 50% (pois  há dois resultados possíveis). Mas é necessário representar a porcentagem como um número decimal. 50% se torna 0,5. Então vamos com 1 ÷ 0,5, que dá 2. 

Depois, vem a parte chata: pegar esse resultado da divisão e tirar o logaritmo dele na base 2. Não se preocupe, você não precisa realmente fazer a conta (nem tirar o pó do livro de matemática do colégio para lembrar como fazê-la). O resultado foi 2, e o logaritmo de 2 na base 2 é 1. Feito: o resultado é 1 bit de informação, confirmando o que você já sabia desde o início.

O importante é entender por que o logaritmo foi usado. Pense em quão surpreendente seria se você desse cem palpites sobre o lançamento de cem moedas e acertasse todos. A probabilidade de isso acontecer é muito baixa. E é claro: quando você divide 1 por um número muito pequeno, o resultado é muito grande. Se os bits representassem mesmo a sua surpresa, precisaríamos de um caminhão deles. 

O logaritmo entra em cena para filtrar a subjetividade da coisa. Depois de incluí-lo na conta, você descobre que a informação contida em cem lançamentos de moeda corretos é exatamente 100 bits, 1 bit para cada cara ou coroa, não importa quão surpreendente esse desfecho seja. O logaritmo é uma operação usada para domar números grandes, trazê-los de volta para um tamanho lidável quando eles saem de controle. 

Lançamentos de moeda são uma situação idealizada. Na vida real, quase nenhum acontecimento tem dois desfechos igualmente prováveis. Por exemplo: há uma chance minúscula de que você ganhe o sorteio de um carro e uma chance bem maior de que você não ganhe. A vitória, portanto, carrega um montão de bits. E a derrota, que não é nem um pouco surpreendente, carrega pouquíssimos bits (menos de um). Na média, a sua chance de ficar surpreso com o desfecho é baixa, porque existem muitos resultados frustrantes e apenas um vitorioso. 

Essa média da quantidade de informação contida em um evento – ou, em outras palavras, a possibilidade de que você se surpreenda com o desfecho dele – é chamada nas ciências exatas de entropia. A entropia de um sorteio é baixa, porque ele é extremamente previsível: é quase certo que você vai perder. 

Para facilitar, pense na entropia como o grau de desordem de alguma coisa. Um sorteio é altamente ordenado, porque a maioria esmagadora dos jogadores não ganha nada. Esse dado se repete, de novo e de novo, como o padrão geométrico em um tapete. O vencedor do sorteio é um ponto fora da curva, algo inesperado e desorganizado. Uma mancha no tapete, que aumenta a entropia. 

Para um computador, a entropia é o grau de desordem não de um tapete, mas da informação. “Por exemplo: uma mensagem consistindo em mil repetições do número zero contém pouca informação e tem uma entropia muito baixa. A mensagem pode ser resumida a ‘1000 vezes o zero”, escreve o matemático George Szpiro no livro A vida secreta dos números.

“Por outro lado, uma sequência completamente aleatória de zeros e uns tem uma entropia muito alta. Essa sequência não pode ser comprimida de forma alguma e a única maneira de armazená-la é repetindo cada caractere.” Arquivos organizados são mais compactáveis, enquanto os arquivos caóticos são irredutíveis. 

Compressão na prática

Por exemplo: suponha que a sequência 000010100010111110100101000101 apareça 453 vezes no código de um programa. Para compactá-lo, basta atribuir uma etiqueta mais curta à sequência (digamos que você queira batizá-la de “01”) e então usar essa etiqueta em vez do trecho inteiro. Na hora de descompactar o programa, o PC desfaz essa operação e bingo: ele estará intacto. Todo arquivo compactado viaja carregando um dicionário de si mesmo, em que todas essas equivalências estão anotadas: “01 corresponde a 0000101000…” e assim por diante. 

O mais influente algoritmo desse tipo, o LZ77, foi publicado em 1977 pelos israelenses Abraham Lempel e Jacob Ziv. Até hoje, as iniciais dos sobrenomes deles aparecem em dezenas de algoritmos derivados: LZR, LZSS, LZH, LZMA… A sopa de letrinhas é longa. Além do dicionário, um aspecto importante desses algoritmos é algo chamado “janela deslizante” (sliding window), que tem a ver com a maneira como a longa sequência de bits é vasculhada pelo algoritmo em busca de redundâncias.

No final da década de 1980, um jovem programador do interior dos EUA chamado Phil Katz combinou o LZ77 com o código de Huffman para criar o algoritmo DEFLATE (“desinflar”, em inglês), que se tornaria o canivete suíço da compressão: está na base de diversos formatos, como o PNG.  

Katz embutiu seu trabalho de compressão e descompressão em um programa chamado ARC, da empresa de software System Enhancement Associates (SEA). A partir daí, o programa passou a rodar mais rápido. Nascia o PKARC, com as iniciais de Katz adicionadas. 

A SEA foi conversar com Katz para licenciar sua versão envenenada do programa, mas ele se negou a colaborar. Foi processado e vencido no tribunal em 1988. Então, Katz escreveu um novo código do zero para diferenciá-lo do original, rebatizou sua versão de PKZIP e criou o lendário formato de arquivo ZIP, que se tornaria o meio mais comum de comprimir arquivos na web nos anos 2000 – até hoje, usuários de Windows usam o programa WinZip.

Katz foi um rockstar disfarçado de programador, com pitadas de gênio, mocinho e bandido. Era um administrador errante de sua empresa, a PKWARE, mas tinha fama de ser afável com os funcionários. Sofria com alcoolismo crônico e problemas de sociabilidade, e acabou morrendo em 14 de abril de 2000 com um sangramento agudo no pâncreas. Foi encontrado em um quarto de hotel com uma garrafa vazia na mão e outras cinco ao redor. 

A morte trágica de Katz, porém, não bastou para que Henderson o perdoasse. Na época, Henderson escreveu: “Não consigo pensar em um epitáfio mais adequado do que a cláusula final de copyright do ARC: se você não cumprir os termos desta licença, sua consciência irá assombrá-lo pelo resto da sua vida”.

A gênese do MP3

A entropia determina o máximo que se pode espremer um arquivo sem perder nenhum dado. É o que se chama de compressão lossless (“sem perdas”, em inglês). O problema é que, para muitas finalidades, essa compactação fiel não é pequena o suficiente. Chega uma hora em que é preciso sacrificar um pouco de informação para reduzir um arquivo. E o segredo, claro, é saber quais bits são imprescindíveis e quais não farão falta. No caso de sons, imagens e vídeos, o trabalho de separar o essencial do supérfluo tem uma ajudinha da biologia. 

Vamos começar explicando a compressão de uma foto em JPEG, que ocorre em cinco etapas. Mais especificamente, a segunda dessas etapas, chamada downsampling de crominância, que se aproveita do funcionamento dos nossos olhos para manipulá-los.

A retina, localizada no fundo do globo ocular, tem dois tipos de células detectoras: 6,5 milhões de cones e 130 milhões de bastonetes. Os bastonetes captam apenas variações de luminância, ou seja: enxergam em preto e branco. Porém, eles são muito mais sensíveis (motivo pelo qual, em situações com pouquíssima luz, você não vê em cores. Faça o teste em um quarto escuro). 

Os cones, por outro lado, vêm em três tipos: vermelhos, verdes e azuis. Isso não significa que eles só captem essas três cores, e sim que eles ficam responsáveis por fatias diferentes do espectro visível: um cuida da ponta de com ondas eletromagnéticas de menor energia (que nossos olhos enxergam como as cores vermelho e laranja), um cuida do meio (onde estão tons próximo do amarelo e do verde) e um cuida da ponta mais energética (onde ficam os azuis e roxos). Chamamos a informação captada pelos cones de crominância.

Vermelho, verde e azul são as cores primárias usadas para gerar imagens em todos os aparelhos com tela colorida. É o sistema RGB (sigla de red, green, blue em inglês). Cada quadradinho de uma foto – um pixel – consiste nessas três cores misturadas em algum grau. Por exemplo: se você está vendo um gramado verdinho, a maioria dos pixels terá valores altíssimos na cor verde e valores mais baixos ou nulos para o azul e o vermelho.

Como os bastonetes são mais sensíveis, temos uma acuidade ótima em preto e branco. Por outro lado, somos meio ruins com cores. Por isso, no downsampling de crominância, o algoritmo do JPEG pega as informações de cor de quatro pixels, tira uma média e os transforma em um só (reduzindo o tamanho dessa parte do arquivo a apenas um quarto do original), enquanto as informações de luminância, em preto e branco, permanecem idênticas. Nosso cérebro mal percebe a diferença.

A gênese do MP3

A história do MP3 começa com o doutorando Dieter Seitzer e seu orientador Eberhard Zwicker, dois nerds alemães que disputavam partidas de pingue-pongue diárias na Universidade Erlangen-Nuremberg. Zwicker era pioneiro em uma área de pesquisa chamada psicoacústica, que estuda as limitações do ouvido humano. Ele evoluiu por seleção natural para responder a necessidades básicas, como entender o que os outros estão falando ou detectar a aproximação de predadores. Isso significa que nossa audição é enviesada: dá atenção redobrada a sons com certas características enquanto ignora outros.

Seitzer percebeu que essas limitações auditivas poderiam servir para tirar bits de um arquivo de áudio sem percebermos. Sua intenção, com isso, era construir uma tal jukebox digital: um avô do Spotify que mandaria música on demand pelas linhas telefônicas a partir de servidores. 

O problema é que isso exigiria arquivos de áudio doze vezes menores do que era possível na época – algo que o escritório de patentes julgou impossível (e a ideia, de fato, nunca saiu do papel). Um pupilo de Seitzer, Karlheinz Brandenburg, concordava que o plano era ousado. Mas tentou colocá-lo em prática. E criou um algoritmo eficaz de compactação de áudio, que daria origem ao MP3. Não em tempo de usá-lo pelo telefone, mas na hora certa para a ascensão da internet. 

Brandenburg se baseou em três constatações básicas, que o jornalista Stephen Witt lista no livro Como a música ficou grátis. A primeira é que nossa capacidade de audição é mais afiada nas frequências equivalentes à voz humana. Isso significa que é possível eliminar alguns bits dos sons graves – e um montão de bits dos sons extremamente agudos – sem nenhum prejuízo perceptível.  

A segunda é que, quando há dois sons sendo reproduzidos simultaneamente, um grave e um agudo, o grave tende a anular alguns detalhes da percepção do agudo. Isso tem a ver com a arquitetura da cóclea, o minúsculo órgão do ouvido que converte vibrações em sinais elétricos para o cérebro.

A terceira constatação é que sons que vêm alguns milissegundos antes ou logo depois de um evento muito intenso (como os pratos da bateria) acabam ignorados pelo nosso cérebro, e portanto, podem ser eliminados. Voilà: temos um arquivo de música de qualidade convincente, cujo download não leva dias. 

O MP3 provavelmente é o padrão de compressão mais influente da história. Ele permitiu a pirataria de música pela internet em uma época em que não existia banda larga, bateu todos os pregos no caixão do CD – o formato de distribuição que havia dominado a década de 1990 – e quebrou as pernas das grandes gravadoras, desencadeando uma sequência de eventos que culminou com a fundação do Spotify e a supremacia da distribuição de música e podcasts legalmente por streaming. 

O mais interessante, porém, é que após submeter o arquivo de áudio às três intervenções psicoacústicas que listamos acima – bem como a outras transformações –, o passo final do algoritmo do MP3 é um round de compactação pelo código de Huffman, que é lossless. Aquele de 1952, citado no começo do texto, que foi um aperfeiçoamento do trabalho de Claude Shannon.  

Moral da história: não importa quão avançados nossos chips se tornem, nossa capacidade de encolher um arquivo sempre estará condicionada a uma limitação fundamental do Universo, descoberta nos anos 1940: a proporção entre ordem e caos em seu código binário. Shannon foi o primeiro a se dar conta de que a capacidade de espremer informação tem a ver com o conceito de entropia. E seu fantasma assombra cada arquivo .ZIP até hoje. 

• Mais lidas

1

Ciência

Marte é atingido por muito mais meteoroides do que pensávamos

2

Cultura

Divertida Mente 2: a origem peculiar do nome da personagem Ennui

3

Cultura

Desafio Pepsi: como foi o capítulo mais emblemático da “guerra das colas”

4

Ciência

Iminente explosão estelar será visível a olho nu

5

Sociedade

Existem mais notas de R$1 do que de R$200 em circulação

• computador