Algoritmos de compressão

Este artigo faz uma apresentação dos algoritmos de compressão e qual a lógica de funcionamento dos mesmos. É o primeiro de uma série de três artigos que pretendo escrever falando sobre isso, que serão divididos em como começou, o que usamos hoje em dia, e por último a prática com implementação dos mais usados.

[ Hits: 9.686 ]

Por: Pablo Margreff em 23/03/2016 | Blog: https://pmargreff.wordpress.com/


Árvores de Huffmann



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.
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.
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.
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. : )
Aqui o link para o árvore correta.

Fontes:
Página anterior     Próxima página

Páginas do artigo
   1. Introdução
   2. Códigos de comprimento variável
   3. Árvores de Huffmann
   4. Classe Lempel-Ziv-Welch
   5. Conclusões
Outros artigos deste autor

Manipulação de imagens no formato PPM

Gerando Números Aleatórios

Aumentando sua produtividade com o teclado padrão Dvorak

Leitura recomendada

Kernel Hacking (RootKits)

Compilação do kernel v3.x no CentOS e Debian

Slackware 13 - Compilando o kernel 2.6.32rc6

Compilação comentada do kernel

Experimento com Linux: Misturando Sabayon com Gentoo

  
Comentários
[1] Comentário enviado por ivo_cruz em 29/03/2016 - 08:30h

A saída do Q é 0100


Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts