Como funciona a compactação de dados sem perdas | Revista Quanta

Com mais de 9 bilhões de gigabytes de informações viajando pela Internet todos os dias, os pesquisadores estão constantemente procurando novas maneiras de compactar dados em pacotes menores. As técnicas de ponta concentram-se em abordagens com perdas, que atingem a compressão intencionalmente “perdendo” as informações de uma transmissão. O Google, por exemplo, revelou recentemente uma estratégia com perdas em que o computador remetente descarta detalhes de uma imagem e o computador receptor usa inteligência artificial para adivinhar as partes que faltam. Até a Netflix usa uma abordagem com perdas, diminuindo a qualidade do vídeo sempre que a empresa detecta que um usuário está assistindo em um dispositivo de baixa resolução.

Muito pouca pesquisa, por outro lado, está sendo realizada atualmente em estratégias sem perdas, onde as transmissões são reduzidas, mas nenhuma substância é sacrificada. A razão? Abordagens sem perdas já são notavelmente eficientes. Eles alimentam tudo, desde o padrão de imagem JPEG até o onipresente utilitário de software PKZip. E tudo por causa de um aluno de pós-graduação que estava simplesmente procurando uma saída para um exame final difícil.

Setenta anos atrás, um professor do Instituto de Tecnologia de Massachusetts chamado Robert Fano ofereceu aos alunos de sua aula de teoria da informação uma escolha: fazer um exame final tradicional ou melhorar um algoritmo de ponta para compactação de dados. Fano pode ou não ter informado a seus alunos que ele era o autor daquele algoritmo existente ou que estava procurando uma melhoria há anos. O que sabemos é que Fano lançou a seus alunos o seguinte desafio.

Considere uma mensagem composta de letras, números e pontuação. Uma maneira direta de codificar essa mensagem seria atribuir a cada caractere um número binário exclusivo. Por exemplo, um computador pode representar a letra A como 01000001 e um ponto de exclamação como 00100001. Isso resulta em códigos fáceis de analisar – cada oito dígitos, ou bits, correspondem a um único caractere – mas terrivelmente ineficiente, porque o mesmo número de dígitos binários é usado para entradas comuns e incomuns. Uma abordagem melhor seria algo como o código Morse, onde a letra frequente E é representada por apenas um único ponto, enquanto o Q menos comum requer o traço-traço-ponto-traço mais longo e trabalhoso.

No entanto, o código Morse também é ineficiente. Claro, alguns códigos são curtos e outros são longos. Mas como os comprimentos dos códigos variam, as mensagens em código Morse não podem ser compreendidas a menos que incluam breves períodos de silêncio entre cada transmissão de caracteres. De fato, sem essas pausas dispendiosas, os destinatários não teriam como distinguir a mensagem Morse traço ponto-traço-ponto ponto-ponto traço ponto (“banal”) de traço ponto-traço-ponto ponto-ponto-traço ponto (“verdadeiro” ).

Fano resolvera essa parte do problema. Ele percebeu que poderia usar códigos de tamanhos variados sem precisar de espaços dispendiosos, desde que nunca usasse o mesmo padrão de dígitos como um código completo e o início de outro código. Por exemplo, se a letra S fosse tão comum em uma mensagem específica que Fano atribuisse a ela o código extremamente curto 01, nenhuma outra letra nessa mensagem seria codificada com qualquer coisa que começasse com 01; códigos como 010, 011 ou 0101 seriam todos proibidos. Como resultado, a mensagem codificada pode ser lida da esquerda para a direita, sem qualquer ambigüidade. Por exemplo, com a letra S atribuída a 01, a letra A atribuída a 000, a letra M atribuída a 001 e a letra L atribuída a 1, de repente a mensagem 0100100011 pode ser imediatamente traduzida na palavra “pequeno”, embora L seja representado por um dígito, S por dois dígitos e as outras letras por três cada.

Para realmente determinar os códigos, Fano construiu árvores binárias, colocando cada letra necessária no final de um ramo visual. O código de cada letra foi então definido pelo caminho de cima para baixo. Se o caminho desviasse para a esquerda, Fano acrescentava um 0; os ramos certos obtiveram um 1. A estrutura da árvore facilitou para Fano evitar essas sobreposições indesejáveis: uma vez que Fano colocasse uma letra na árvore, esse ramo terminaria, significando que nenhum código futuro poderia começar da mesma maneira.

Para decidir quais letras iriam para onde, Fano poderia ter testado exaustivamente todos os padrões possíveis para máxima eficiência, mas isso seria impraticável. Então, em vez disso, ele desenvolveu uma aproximação: para cada mensagem, ele organizaria as letras relevantes por frequência e, em seguida, atribuiria as letras aos ramos, de modo que as letras à esquerda em qualquer par de ramos fossem usadas na mensagem aproximadamente o mesmo número de vezes que o letras à direita. Dessa forma, os caracteres usados ​​com frequência acabariam em ramificações mais curtas e menos densas. Um pequeno número de letras de alta frequência sempre compensaria um número maior de letras de baixa frequência.

O resultado foi uma compressão notavelmente eficaz. Mas era apenas uma aproximação; uma melhor estratégia de compressão tinha que existir. Então Fano desafiou seus alunos a encontrá-lo.

Fano havia construído suas árvores de cima para baixo, mantendo o máximo de simetria possível entre os galhos emparelhados. Seu aluno David Huffman inverteu o processo, construindo os mesmos tipos de árvores, mas de baixo para cima. A percepção de Huffman foi que, aconteça o que acontecer, em um código eficiente, os dois caracteres menos comuns devem ter os dois códigos mais longos. Assim, Huffman identificou os dois caracteres menos comuns, agrupou-os como um par ramificado e repetiu o processo, desta vez procurando as duas entradas menos comuns entre os caracteres restantes e o par que acabara de construir.

Considere uma mensagem em que a abordagem de Fano vacila. Em “sala de aula”, O aparece quatro vezes e S/C/H/L/R/M aparece uma vez cada. A abordagem de equilíbrio de Fano começa atribuindo o O e uma outra letra ao ramo esquerdo, com os cinco usos totais dessas letras equilibrando as cinco aparências das letras restantes. A mensagem resultante requer 27 bits.

Huffman, por outro lado, começa com duas das letras incomuns - digamos, R e M - e as agrupa, tratando o par como uma única letra.

Seu gráfico de frequência atualizado oferece a ele quatro opções: o O que aparece quatro vezes, o novo nó RM combinado que é funcionalmente usado duas vezes e as letras únicas S, C, H e L. Huffman novamente escolhe as duas opções menos comuns, combinando (diga) H com L.

O gráfico é atualizado novamente: O ainda tem um peso de 4, RM e HL agora têm um peso de 2, e as letras S e C ficam sozinhas. Huffman continua a partir daí, em cada etapa agrupando as duas opções menos frequentes e atualizando a árvore e o gráfico de frequência.

Por fim, “sala de aula” se torna 11101111110000110110000101, eliminando um pouco a abordagem de cima para baixo de Fano.

Um bit pode não parecer muito, mas mesmo pequenas economias crescem enormemente quando dimensionadas para bilhões de gigabytes.

De fato, a abordagem de Huffman revelou-se tão poderosa que, hoje, quase todas as estratégias de compressão sem perdas usam o insight de Huffman no todo ou em parte. Precisa do PKZip para compactar um documento do Word? A primeira etapa envolve ainda outra estratégia inteligente para identificar a repetição e, assim, comprimir o tamanho da mensagem, mas a segunda etapa é pegar a mensagem compactada resultante e executá-la pelo processo de Huffman. Armazenar uma imagem como JPEG? Seu computador primeiro traduz a imagem em uma representação baseada em texto e, novamente, usa a codificação Huffman para compactar esse texto.

Nada mal para um projeto originalmente motivado pelo desejo de um aluno de pós-graduação de faltar a um exame final.