Compressor Huffman Duvida | ZWAME Fórum
Compressor Huffman Duvida
Discussão em 'Programação' iniciada por ryotsu, 15 de Outubro de 2012. (Respostas: 8; Visualizações: 1037)
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:
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 ?
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.
Também estou com dificuldades em perceber o que estás a perguntar.
pelo que tenho visto é preciso passar este numero binario para bytes
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.
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?
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:
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).
buf = (buf << 1) | 1;
Podes tornar isto numa macro:
#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.
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?
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
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 variavel buf que deste como exemplo é de que tipo? byte[]
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.
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