O que é árvore binária e como funcionam arquivos .zip

Poder comprimir o tamanho dos arquivos que estamos compartilhando é, sem dúvida, uma grande ajuda. Entender como esses arquivos funcionam pode ser necessário para poder usá-los, mas para além disso é um conhecimento fascinante. Você sabia que o .zip funciona por um sistema de árvore binária, por exemplo?

O que é árvore binária

As árvores binárias são modelos de compressão e compactação de arquivos sem perda de dados. Trata-se de uma estrutura de dados com uma raíz comum que passa a se dividir em um espaço vazio (sub-árvore esquerda) e em um espaço com elemento (sub-árvore direito).

A árvore binária garante que nenhum dado seja perdido na compressão, de forma que quando o arquivo seja descomprimido todas as informações sejam encontradas exatamente como eram originalmente. Isso porque a árvore binária funciona diferente de outros algoritmos de compressão, como os codecs dos vídeos ou os algoritmos de compressão de imagens responsáveis por gerar jpgs.

Como criar uma árvore binária

Para aprender como funciona e como criar uma árvore binária, vamos comprimir a frase “amo leer panama papers”. Originalmente, essa frase teria 22 bytes (ou 176 bits), já que uma letra tende a ocupar 8 bits.

1. Verificar repetição da informação

No nosso caso, vamos contar quantas vezes cada letra se repete, seguindo um padrão lógico: começando pela primeira letra em diante.

a = 5
m = 2
r = 2
s = 1
o = 1
| | = 3
p = 3
l = 1
e = e
n = 1

2. Criar a primeira raíz

Como dissemos anteriormente, nas árvores binárias, de uma mesma raíz sempre saem dois ramos. Assim, criamos a nossa primeira raíz com a sub-árvore esquerda sendo representada por um 0 (vazio) e a sub-árvore direita sendo representada por um 1.

3. Adicionar os dados por frequência

Como mote para a compressão, começamos a adicionar os dados por aquele que aparece mais vezes. No nosso caso, pela letra A. Dessa forma, ao invés de ocupar 8 bits, a letra A terá um peso de apenas 1 bit.

Lembre-se também que todas as letras/dados devem ser representados nos galhos à direita, mantendo o da esquerda vazio.

Nosso exercício até aqui fica assim:

4. Representar os dados

Vamos supor que queremos representar a letra M de acordo com essa árvore binária. A representação se dá por meio de bits e ficaria assim:

00001

Isso porque para chegar até o 1 que representa essa letra você teria que passar por 4 ramos vazios. Assim, todas as letras são uma sequência de zeros que terminam em um.

Fez sentido? Vamos continuar!

5. Comprimir os dados

Para finalizar o nosso exercício, vamos representar a frase “amo leer panama papers” a partir dessa árvore binária.

O resultado deve ficar assim:

1 00001 0000001 01 00000001 001 001 000001 01 0001 1 0000000001 1 00001 1 01 0001 1 0001 001 000001 000000001

Conclusão

No exercício que fizemos juntos, comprimimos uma frase simples diminuindo seu tamanho quase pela metade. Se você contar no código acima, perceberá que ele passou a ter 11 bytes (ou 88 bits) para passar a mesma informação.

Esse exemplo é educativo e é claro que num código real você também precisa contar o peso das informações da árvore binária criada, por exemplo. Mas você pode imaginar o impacto desse tipo de estrutura de dados na compressão de arquivos como softwares?