1. Este site usa cookies. Ao continuar a usar este site está a concordar com o nosso uso de cookies. Saber Mais.

Compressor Huffman Duvida

Discussão em 'Programação' iniciada por ryotsu, 15 de Outubro de 2012. (Respostas: 8; Visualizações: 1037)

  1. Boas pessoal,

    Tenho estado a desenvolver um compressor de ficheiros utilizando o algoritmo de Huffman.

    Apos construir a arvore, restame apenas ler novamente o ficheiro byte a byte e ir codificando. Pois a minha duvida é o seguinte... imaginemos que obtenho o seguinte:

    A - 000
    U - 11
    S - 001

    Temos que a palavra "SUAS" = 00111000001 pois a duvida está mesmo aqui... como podemos ver a string binária é relativamente maior que a inicial o que faz com que o espaço que ocupa é maior... pelo que tenho visto é preciso passar este numero binario para bytes ... estará isto certo? como se converte ?

    Cumprimentos e desde já Obrigado
     
  2. Cfreitas

    Cfreitas Power Member

    Não sei se é o que estas a perguntar...
    2351 (2 0 seguidos de 3 1 seguidos de 5 0 seguidos de 1 1) também representa a palavra e não é maior que a string. Além disso tu precisas de um espaço de 8bytes para uma char e de 4 para um int. como tal a palavra original ocupa 8*4 e a "nova" ocupa 4*4.
    Isto tudo MUITO por alto.
     
  3. Sl0w

    Sl0w Power Member

    Também estou com dificuldades em perceber o que estás a perguntar.

    Tu tens de passar esse número binário para...bits. Essa string binária não é maior que a inicial, repara que:
    'S','U','A','S' são 4 bytes; se comprimires usando o algoritmo E a árvores que apresentas ficas com "00011001" que não passa de 1 byte! Comprimiste "SUAS" num único byte. Não sei se percebeste muito bem a ideia do algoritmo, mas agora que já tens árvore construida tens de codificar input e despejar tudo numa Stream de bits. Uma Stream de bits é uma coisa suja de se fazer, vais ter de andar a brincar com uns "shifts" e uns "ors" mas não é nada de transcendente :) De qualquer das formas, a codificação dessa árvore é um pouco estranha, mas acho que não é crítico.
     
  4. Boas Sl0w

    Sim à primeira vista as codificações que dei podem fazer parecer a árvore um pouco estranha mas isso foi só pq a árvore tem mais caracteres e eu não os coloquei aqui todos :X
    Em relação ao que descreveste de comprimir tudo usando o algoritmo E... não percebi como passaste de 'S','U','A','S' para "00011001" consegues explicar-me melhor este processo?
    Em relação á stream de bits consegues explicar-me mais ou menos o processo?

    Cumprimentos e obrigado
     
  5. Sl0w

    Sl0w Power Member

    http://rosettacode.org/wiki/Bitwise_IO

    Como não faço ideia que linguagem estás a usar, fica com esse link que tem exemplos em várias linguagens. A ideia é teres uma função: write_bits. Está função pode ser implementada de várias maneiras. Se não estás particularmente preocupado com a eficiência podes simplesmente criar uma função:
    Código:
    write_bits(int b)
    Que mete um "despeja" um bit a 1 ou a 0 na Stream, conforme o b. Precisas de ter um Byte que vai servir de buffer. Quando precisas de escrever um bit na stream, fazes shift do byte uma posição para a esquerda e fazes OR com o bit que estás a escrever (se o b=0 apenas fazes o shift).
    Código:
    buf = (buf << 1) | 1; 
    
    Podes tornar isto numa macro:
    Código:
    #define PUT0(X) X = X << 1
    #define PUT1(X) X = (X << 1) | 1
    
    Agora o "write_bits" simplesmente usa estas duas macros para fazer a sua tarefa. Quando fazer 7 shifts, escreves esse byte "buf" para o ficheiro e metes o byte a 0. Repetes o processo. Quando a codificação terminas, despejas o byte no ficheiro mesmo que ainda não tenhas feito os 7 shifts.
     
    Última edição: 15 de Outubro de 2012
  6. A linguagem de programação que estou a utilizar é o C# essa função write_bits recebe um inteiro que será o tal 0 ou 1 certo? se for um 0 faço apenas um shift se for um 1 faço shift e dpx OR correcto? A variavel buf que deste como exemplo é de que tipo? byte[] ? Vou tentar implementar o que me disseste... será que me podias mandar uma pm com o teu mail caso me surgisse mais alguma duvida?

    Cumprimentos
    Obrigado
     
  7. Já agr dizme outra coisa... depois é possível voltar atrás ? tipo obter a codificação por trás do caracter que é imprimido no ficheiro? xD é que depois tenho de conseguir descomprimir o ficheiro xD

    Cumprimentos
     
  8. Sl0w

    Sl0w Power Member

    Quanto ao C# não faço ideia, nunca programei muito nessa linguagem. Vê se não existe já uma implementação da bitstream nas bibliotecas do C#.

    A variável buf, no caso do C, seria um unsigned char. Também podes usar um "unsigned int" e assim só despejas os 4bytes ao fim de 32 shifts.

    Sim, é essa a ideia do huffman. Podes implementar o descompressor à custa de uma função GETBIT que obtém um bit da stream. Começas na raiz da árvore e vais chamando constantemente o GETBIT; conforme o bit que obténs, segues esse caminho na árvore. Sempre que chegares a uma folha da árvore, ou seja, um nó da árvore sem descendentes, escreves o "char" que lhe está atribuido e em de seguida voltas à raiz. Iteras este processo até que a stream esteja vazia. Se a árvore for uma árvore de huffman válida e se a árvore usada no processo de descompressão é a mesma que foi obtida no processo de compressão, então o ficheiro obtido através deste processo será o ficheiro original.
     
  9. Então mas o que irei estar a ler do ficheiro comprimido irá ser o byte resultante ja junção daqueles 1's e 0's que vou inserindo... como é que eu volto a transformar esse byte nos bits 0 e 1's que tinha anteriormente ? para depois recorrer á arvore e ver realmente o que lhe está associado

    Cumprimentos
    Obrigado
     

Partilhar esta Página