[Resolvido] Compressor Huffman DUVIDA

[programmer1337]

Boas pessoal

Tenho estado a construir um compressor de Huffman para ficheiros, e deparei-me com uma duvida...

Após ter realizado a contagem da frequência de cada byte do ficheiro e a construção da arvore binaria necessária para a codificação do byte em questão, imaginemos que obtive o seguinte:

A = 000

S = 001

M = 1010

Podemos ver então que a codificação do nome SAM = 001 000 1010 a minha duvida é a seguinte.. quando for escrever o ficheiro escrevo a string "001 000 1010" ? tentei fazer isto e observei que o tamanho aumenta quando devia diminuir.... pois passei de 3 caracteres para 10 caracteres :X

O que devo escrever para o ficheiro comprimido?

Cumprimentos e desde já Obrigado!

[HappyHippyHippo]

em vez de usares string com 3 caracteres, experimenta para textos grandes.

experimenta com o lorem ipsum

no que toca a o que escrever : wikipedia

[programmer1337]

tentei para textos grandes como me disseste e continuo a obter o mesmo resultado o tamanho do file aumenta na mesma ...

Não percebi o que quiseste dizer quanto ao que devia escrever ... não escrevo a string?

[pedrosorio]

programmer1337, acho que não estás a compreender algo: a codificação é binário. Ou seja, não tens que escrever a string "0010001010", mas sim o número (binário) 0010001010. Como não podes escrever menos que um byte de cada vez, na prática o que vais querer fazer é pegar no ficheiro completo, ir acrescentando o código huffman de cada caracter a um array de caracteres (porque cada caracter tem 1 byte), e depois escrever esse array para um novo ficheiro que passa a ser o teu ficheiro comprimido.

Dito de outra forma, se o teu ficheiro fosse SAMSAMSAMSAM, o código seria 0010001010001000101000100010100010001010 (que equivale a 40 bits ou 5 bytes, bastante menos que os 12 bytes necessários inicialmente).

Para perceberes como isso funcionaria, tens um array lido do input e um para o output. Tens que manter uma variável que indique em que byte do ouput estás e em que bit desse byte. Assim, para cada caracter do input, encontras o código binário que lhe corresponde e acrescenta-lo ao array de output.

Como estavas a pensar escrever o código de huffman sob a forma de string, não sei se percebes como fazer esta manipulação de bytes e bits, se precisares de mais esclarecimento diz.

Edited October 14, 2012 at 10:17 PM by pedrosorio

[programmer1337]

Olá

pedrosorio

pelo que tu disseste percebi que após ter construido a arvore iremos ter um numero binário para cada simbolo... Ou seja a cada byte que lemos do ficheiro temos de escrever o numero binario no ficheiro de output certo?

Gostava que me ajudasses com a manipulação de bytes e bits... não sei como isso se faz :X este processo é aquele em que passo o numero binário para bytes certo?

Cumprimentos

Edited October 14, 2012 at 10:46 PM by programmer1337