Codificação de Huffman e compressão de dados…

Para mostrar o poder de uma árvore binária e para acalentar a sugestão de dois associados do grupo “C & Assembly para arquitetura x86-64”, lá no Facebook (aqui), eis um artiguinho sobre Huffman Coding. Essa técnica é muito usada em algorítmos de compressão como zlib e usada nos utilitários ZIP e RAR, por exemplo…

Eis o problema: Dado um array com um monte de bytes, como podemos reduzi-lo a um tamanho menor que o original? Como compactá-lo? Como codificar cada um dos ‘caracteres’ com a menor sequência de bits que seja única para cada byte? Para mostrar como isso é feito vou usar o seguinte texto como exemplo:

ESTE TEXTO CONTEM UM EXEMPLO QUE PODE SER COMPACTADO

Ou seja, esse texto que estará contido no que chamarei de “buffer original”, obedece a seguinte sequência:

00000000 45 53 54 45 20 54 45 58 54 4f 20 43 4f 4e 54 45 |ESTE TEXTO CONTE|
00000010 4d 20 55 4d 20 45 58 45 4d 50 4c 4f 20 51 55 45 |M UM EXEMPLO QUE|
00000020 20 50 4f 44 45 20 53 45 52 20 43 4f 4d 50 41 43 | PODE SER COMPAC|
00000030 54 41 44 4f                                     |TADO|

O algoritmo de Huffman:

No algoritmo de Huffman a primeira coisa que temos que fazer é contar quantas vezes cada byte aparece na string. Ou seja, calcular a frequência com que eles aparecem. Uma vez que as frequências são conhecidas, ordenamos o array e obtemos isso:

char: freq
 'L': 1
 'N': 1
 'Q': 1
 'R': 1
 'A': 2
 'D': 2
 'S': 2
 'U': 2
 'X': 2
 'C': 3
 'P': 3
 'M': 4
 'T': 5
 'O': 6
 ' ': 8
 'E': 9

Ficamos sabendo de duas coisas aqui: Quantos bytes de ‘tipos’ diferentes existem no buffer e quantas vezes eles ocorrem. Cada byte da string suporta até 256 valores (de 0x00 até 0xff), mas não usamos todos eles. Esse texto usa apenas 16 valores!

Quanto as frequências, espaços, por exemplo, ocorrem 8 vezes na string. O byte ‘E’ ocorre mais que ‘O’ e assim por diante…

A partir dessa lista de frequências montamos uma árvore binária para determinarmos os códigos únicos de cada byte…

Montando a árvore binária:

A árvore binária é montada obtendo sempre as menores frequências da lista e combinando-as numa subárvore onde os nós “folha” são organizados colocando-se às ocorrências com maior frequência à esquerda e os com menor frequência à direita. O nó raiz conterá a soma das frequências dos nós “folha”.

Para a lista de frequências anterior, a sequência de montagem da árvore de Huffman é mostrada na figura abaixo… Note que os nós acinzentados são os agrupamentos de dois outros nós, seguindo a regra citada anteriormente. Uma vez que as novas sub-árvores vão sendo criadas, os nós que a compuseram são retirados da lista e a nova sub-árvore é colocada no início da lista de frequências, de acordo com o valor contido no nó raiz.

Escolhi colocar a nova sub-árvore antes da primeira ocorrência da frequência maior ou igual a do nó raiz. Ou seja… Na primeira iteração, ao combinar ‘L’ e ‘N’ (que têm menor frequência), o nó raiz dessa sub-árvore terá frequência 2 — frequencia_{raiz}=frequencia_{L}+frequencia_{N} — e será colocada antes do item contendo ‘A’ (que também tem frequência 2). Na segunda iteração os itens ‘Q’ e ‘R’ são agrupados noutra sub-árvore e colocados, novamente, no início da sequência das frequências 2 e por ai vai (leia as iterações do lado esquerdo, de cima para baixo, continuando do lado direito):

steps

Repare: Toda sub-árvore é calculada sempre a partir dos itens de menor frequência, mas, na sub-árvore, a maior frequência sempre vai para o lado esquerdo! O que nos deixa, depois do último passo, com a seguite árvore de distribuição de frequências:

Distribuição de frequências
Distribuição de frequências

Essa é a árvore de Huffman para a sequência de caracteres de nossa string… Mas, em que ela nos ajuda?

Usando a árvore para obter os códigos

Se caminharmos na árvore para a esquerda, a cada vez que mudarmos de nível acrescentaremos um bit ‘0’ no código do caractere. A cada vez que caminharmos para a direita, adicionaremos um bit ‘1’. Isso é feito ao percorrermos a árvore até achar o nó folha correspondente ao caractere desejado. Por exemplo, para chegarmos no caractere ‘E’ precisamos caminhar, à partir do nó raiz, da seguinte maneira: Direita→direita. Isso nos dá os bits “11” e esse, então, é o código para ‘E’.

Note que ‘E’, no buffer original, é codificado em 8 bits (0x45, em ASCII) e, agora, é codificado em apenas dois bits “11”. Da mesma forma, para chegarmos no espaço (cujo código ASCII é 0x20, de 8 bits) precisamos caminhar para esquerda→esquerda→direita, nos dando o código “001” e, quase que por mágica, 8 bits tornaram-se 3!

Assim, a tabela abaixo mostra os caracteres usados na string e seus respectivos códigos de acordo com a árvore de Huffman:

char: bits
 'L': 010110
 'N': 010111
 'Q': 010100
 'R': 010101
 'A': 01000
 'D': 01001
 'S': 01100
 'U': 01101
 'X': 00001
 'C': 00000
 'P': 0111
 'M': 0001
 'T': 101
 'O': 100
 ' ': 001
 'E': 11

Não é coincidência que os caracteres com maior frequência tenham a menor codificação binária! E se os bytes mais frequentes serão codificados com menos bits, e vice versa, conseguimos comprimir o buffer original num bitstream, como mostrado abaixo:

11011001 01110011 01110000 11011000
01000001 00010111 10111000 10010110
10001001 11000011 10001011 10101101
00001010 10001101 11001011 11000100
11100101 10011010 10100100 00010000
01011101 00000000 10101000 01001100

Veja: 11=’E’, 01100=’S’, 101=’T’, 11=’E’, 001=’ ‘, … Dividi o bitstream em bytes para que você entenda o que vai ser gravado num arquivo compactado e para ver que, da string de 52 bytes temos agora um bitstream com 24 bytes. Claramente ocupando menos da metade do texto original.

Cuidados com o bitstream:

Para a nossa sorte o bitstream acima coube exatamente em 24 bytes, mas isso nem sempre ocorre… O byte final pode ter de 1 a 8 bits de tamanho, dependendo da string original e de como os bytes foram codificados na árvore de Huffman. É prudente guardar, em algum lugar, o número de bits que “faltam” no último byte para que a decodificação termine no ponto correto.

O termo técnico para pedaços de informações que “faltam” e são preenchidas com algum valor inócuo é padding.

O que precisamos armazenar no “arquivo compactado”?

Em teoria só precisamos armazenar a árvore de Huffman e o bitstream. Na prática, armazenar a árvore significa inserir “ponteiros”, que tornam a estrutura de armazenamento muito grande. É mais prático armazenar a tabela de frequências, como foi usada para montar a árvore (antes da primeira iteração). Mas, isso também nos cria um problema: Qual deve ser o tamanho do tipo que conterá a frequência?

Se sua implementação calcula as frequências de um arquivo completo, pode-se usar um contador do tamanho de um unsigned int (32 bits) e limitar os arquivos a 4 GB. Podemos também usar uma estrutura “bitmapeada” e usarmos um contador de 48 bits e limitarmos os arquivos a 256 TB, por exemplo.

Como a tabela de frequências só precisa ter o valor do byte e sua frequência, então, em memória, poderíamos usar uma estrutura assim:

struct freq_table {
  unsigned short num_items;
  struct freq_entry *freqs;
};

É claro, cada entrada seria assim:

struct freq_entry {
  unsigned long freq:48;
  unsigned char data;
};

Com isso podemos ter a tabela de frequências, para cada arquivo compactado, ocupando no máximo 1794 bytes (sizeof(struct freq\_entry) \cdot 256 + sizeof(unsigned short)).

Depois da tabela de frequências precisamos armazenar informações sobre o bitstream. Precisamos informar a quantidade de bytes do stream e os bits de padding do byte final. De novo, podemos usar um contador de 48 bits para o tamanho do bitstream (256 TB é mais que suficiente, né?) e 3 bits para o tamanho do padding (que só pode variar entre zero e 7):

struct stream_header {
  unsigned long size:48;
  unsigned long padding:3;
};

Isso ocupará exatamente 7 bytes… Assim, o total do tamanho do header, por arquivo compactado, é de 1801 bytes, no máximo. A esse header segue o bitstream…

Decomprimindo (expandindo) o bitstream:

O processo de descompressão é bem mais simples que o que compressão… basta montar a árvore, à partir da tabela de frequências, e percorrê-la, de acordo com o bitstream. Sempre que acharmos um bit 0, vamos para a esquerda e ao acharmos um bit 1, para a direita, até achar um nó folha, que será o byte que será colocado no array… O tamanho do bitstream pode ser calculado como bitstream\_size = size \cdot 8 - padding, onde size é o tamanho, em bytes do bitstream na estrutura stream_header, que mostrei antes…

Quando a compressão vale à pena?

Lembrando que temos, no máximo, 1801 bytes de header por arquivo, se o tamanho do arquivo for menor que 1801+bitstream\_size, então não vale a pena a compressão! Já que esses registros ficarão maiores que o arquivo original, vale a pena acrescentar um byte adicional ao header para informar o tipo de compressão em uso… Podemos usar outras técnicas para conseguir compressão adequada, como Lempel-Ziv-Welch, por exemplo, ou até mesmo nenhuma compressão. Utilitários como ZIP e RAR possuem o método de armazenamento store, que não comprime, justamente para esses casos.

Outro detalhe importante é que os arquivos “compactados” (com extensão ZIP ou RAR, por exemplo) precisam armazenar uma estrutura de diretórios. Isso significa que esses arquivos são um filesystem em si. Essas estruturas adicionais devem ser levadas em conta na decisão pelo uso ou não da compressão…

Mas, o fator mais crítico é, justamente, o tamanho do buffer original. Se usarmos um buffer muito grande provavelmente conseguiremos valores de frequência mais ou menos iguais para todos os bytes do buffer e, talvez, as tabelas de frequência ficarão grandes… Assim, a árvore de Huffman estará mais ou menos balanceada e, por causa disso, não conseguiremos “resumir” os bits de itens com maior frequência, causando baixa compressão… Pense bem: Num arquivo de 4 GB de tamanho temos mais chances de termos todos os 256 bytes possíveis e distribuídos mais ou menos uniformemente do que num arquivo de 64 kB.

Para resolver isso os compactadores usam um buffer de tamanho fixo e dividem os dados originais em blocos. Blocos muito grandes tendem a criar compressão pobre, mas blocos muito pequenos também (graças ao header antes do bitstream). O RAR permite o uso de blocos de tamanhos entre 64 kB e 4 MB (o que ele chama de “dicionário”). Essencialmente, isso é como dividir o arquivo em blocos e compactar esses “pedaços” separadamente… Obviamente,  exige também um header adicional contendo uma lista de “pedaços” que o arquivo contém…

Essa complicação tem outra vantagem: Como os blocos são relativamente pequenos, os contadores de tamanho podem usar menos bits. O header do tamanho do bitstream, por exemplo, poderia ficar assim, para blocos de tamanho até 2 MB:

struct stream_header {
  unsigned long size:21;  // 2^21 - 1 = 2 MB (aprox).
  unsigned long padding:3;
};

Ocupando 3 bytes ao invés de 7. Do mesmo jeito, a tabela de frequências pode usar um contador do mesmo tamanho:

struct freq_entry {
  unsigned long freq:21;
  unsigned char data;
};

Assim, o header fica com tamanho máximo de 771 bytes (3 \cdot 256 + 3).

Anúncios