codigos de huffman

Disponível somente no TrabalhosFeitos
  • Páginas : 4 (936 palavras )
  • Download(s) : 0
  • Publicado : 26 de setembro de 2014
Ler documento completo
Amostra do texto
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ãosendo 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 conseguimosidentificar 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 formaprecisarí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. Vamosanalisar 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üênciasterã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 fatode 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...
tracking img