codigos de huffman

Trabalho de complexidade de algoritmos

Códigos de Huffman

André Massaioli
Altair Araújo
Rodolfo Martins
Victor Forato
Engenharia da Computação 07/11/12
1. Introdução
Os códigos de Huffman constituem uma técnica amplamente utilizada e muito eficiente para comprimir dados, guardando a relação típica de 20 a 90%, dependendo das características dos dados que estão sendo comprimidos.
O algoritmo guloso de Huffman utiliza uma tabela das freqüências de ocorrência dos caracteres para elaborar um modo ótimo de representar cada caractere como uma cadeia binária.
Assim como é descrito na tabela ASCII, onde há os caracteres e ocorre a conversão para outros valores, como é possível observar na imagem abaixo:

Tabela ASCII
A codificação binária é atribuída à palavra de código, dizemos que isso é o caminho desde a raiz até esse caractere, onde zero é dado ao arco da árvore da esquerda e um é dado ao arco da árvore da direita. Com esse caminho conseguimos identificar qual o endereço binário que leva a cada caractere, como exemplo podemos utilizar um código de comprimento fixo, seria preciso 3 bits para representar seis caracteres, dessa forma precisaríamos de 300.000 bits para codifica – lo. Mas se usarmos o código de comprimento variável precisaríamos somente de 224.000 bits.
Há muitas maneiras de representar um arquivo de informações. Vamos analisar o problema de construir um código de caracteres binários no qual cada caractere é representado por uma cadeia binária única.
Se utilizarmos um código de tamanho fixo, todas as seqüências terão o mesmo tamanho, como por exemplo, esta representação onde cada código possui três bits: a = 000, b = 001 e c = 010. Deste modo, temos mais agilidade ao realizar a decodificação devido ao fato de sabermos exatamente onde inicia e termina cada cadeia. O lado negativo da utilização desta técnica é a questão do armazenamento, na qual acaba ocupando maior espaço de memória.
Um código de comprimento