Códigos de tamanho variável

Toda a informação que geramos em qualquer área associada/derivada à computação é binária, o que a codificação tenta fazer é representar em menos bits e ter o mesmo significado (compressão) ou que possa representado em menos bits e possa ser transformado de volta na informação original (compactação). Resumindo: Quanto menor, melhor.

Começaremos com códigos de comprimento variável, que nada mais são que o número de bits que um certo código (letra, número ou símbolo) ocupa. Esse tipo de compressão necessita de zero de perda de informação.

A teoria de informação fundamentada por Claude Shannon relaciona a conteúdo de uma informação com a probabilidade de um símbolo aparecer em uma sequência. O que mede esta probabilidade é uma função logarítmica. Que consegue encontrar o tamanho que teremos de informação binária. A função logarítmica é definida por:

funcao1

Outra fórmula que teremos que entender será a definição de entropia, que é o número mínimo de bits que conseguimos representar uma informação, definida por:

funcao2

Achou complicado meu/minha jovem? Tudo bem, vamos por isso em prática. Imaginemos que temos uma palavra com apenas quatro símbolos e a mesma probabilidade de ocorrência para todos os símbolos, como mostra a tabela  abaixo

table1_1

Neste caso, se aplicarmos a fórmula teremos uma entropia igual a 2 o que nos diz que precisamos em média do dois bits para representar cada símbolo. A representação se faz como na tabela a seguir.

table1_2

Agora vamos alterar apenas a frequência que a primeira e a última letras aparecem. Como a próxima tabela.

table1_3

Aplicando a fórmula novamente então temos que uma entropia de 1.57, isso quer dizer que cada símbolo tem tamanho médio de 1.57 bits. Mas como isso pode acontecer? Na verdade é bem simples, se sabemos que uma variável aparece mais que outras, podemos representar a mesma com um código menor.

table2_1

Eficiente, porém pare, volte a tabela anterior e pense qual o problema que ela pode gerar. Encontrou? Não, então pense mais um pouco. Sim, é isso mesmo, não podemos ser formar palavras que contenham sub-palavras que já estão na tabela, isso (a não ser que tenhamos uma máquina que possa gerar soluções não determinísticas) nos resulta em um problema de indecidibilidade. No exemplo da tabela a baixo temos que o código de D é formado por sub-palavras que formam os códigos de A e B.

table2_2

Isso para o exemplo da palavra formada por 000011 nos deixa impossibilitados de sabermos com absoluta certeza se estávamos representando CD ou CBA.

Este foi o primeiro tipo de codificação usada na área, existem diversos códigos de comprimento variável, você pode se aprofundar neles aqui.

Árvores do Huffman

David Huffman foi um estudante de computação que se dispôs a se debruçar sobre o problema de codificação de caracteres em binários. Após vários meses de estudo, tentativa e erros ele chegou no que hoje conhecemos como árvores de Huffman.

O funcionamento das árvores de Huffman são ao mesmo tempo simples e eficiente. A ideia do algoritmo é quanto menos vezes um símbolo aparece, mais distante ele irá ficar da raiz da árvore, e logicamente quanto mais vezes ele aparece, mais próximo ele estará perto da raiz. Outro passo essencial para que a árvore possa se bifurcar quando necessário é que todo símbolo seja uma folha, e nunca um nodo da árvore. Vamos começar com a cadeia de caracteres “AACBAAABAC”. O Primeiro passo é, conferir o número de vezes que cada símbolo aparece. Nesse caso: A -> 6 , B & C -> 2. Sabendo disso, já temos que a letra que irá ficar mais próxima da raiz. Como temos apenas três letras fica fácil de montar a árvore. Nos exemplos, irei representar no nodo o número de caracteres restante, mais para ficar mais claro podemos usar os símbolos que estão a partir daquele ramo.

HuffmanTree1Step1

Esse foi o primeiro passo para construirmos a árvore, mas ainda precisamos construir a representação binária a partir da árvore, o que é tão simples quanto o passo anterior, a única coisa à fazer é definir se o caminho será representado por um ou por zero em cada bifurcação, e então quando chegarmos em uma folha juntamos todos os bits do caminho até chegarmos no ponto desejado e assim teremos a representação binária para um determinado símbolo.

HuffmanTree1Step2

Neste exemplo temos a representação da letra B. Considerando que para as bifurcações escolhemos primeiramente um à esquerda e zero à direita e no ramo seguinte o contrário. Para chegar na representação do “B” tudo que precisamos fazer é sair da raiz e percorrer a árvore até o B juntando todos símbolos binários que se encontram no mesmo caminho (nesse caso primeiro o zero o depois o um), assim descobrimos a representação de B como sendo 01. Aplicando esta mesma regra para as outras letras, chegamos a árvore completa.

HuffmanTree1Step3

Para melhor fixação do algoritmo também deixarei uma árvore com dois erros, se você encontrar deixe a resposta nos comentários.  Não haverá prêmio além da satisfação de ter encontrado e uma leve massagem no ego. : )

HuffmanTree2Wrong

Aqui o link para o árvore correta

Fontes:

http://bit.ly/1DjG6qJ

http://bit.ly/1Iy3BYW

http://bit.ly/1LYJ6tX

Anúncios

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s