-
huffman encoding help
I'm having problems figuring out how to encode/decode.
This is the code i've got for encoding:
Code:
f = fopen("out.txt", "w");
for (i = 0; i < strlen(data); i++) {
if (bit_pos == 8) {
fputc(ch, f);
ch = 0;
bit_pos = 0;
}
for (y = 0; ; y++) {
if (tree[data[i]].huf[y] == '\0') break;
ch <<= 1;
ch |= (tree[data[i]].huf[y] - 48);
bit_pos++;
}
}
and the test string i'm been using is: "hello"
char : freq
h 1
e 1
l 2
o 1
encoded then is:
h : 111
e : 110
l : 0
o : 10
which then encoded with the above code comes out as: 1111100000000010
when its decoded then it comes out as:
hellllllllo
because the decoder is picking up the extra 0's as 'l' (which i suppose is right) but is there anyway around that or a better way of encoding?
Thanks
-
I always liked this page, you may find it useful.
http://ciips.ee.uwa.edu.au/~morris/Y...0/huffman.html
-Prelude
-
i know i'm stating the obvious here...
the problem is in encoding your zero. maybe you're encoding an 'l' as 0000 but decoding it as 0
-
update
while the way i tried to get around it was once the for loop had ended to put this:
for (bit_pos; bit_pos < 8; bit_pos++) {
ch <<= 1;
}
to try and get rid of the redundant bits, that worked. But when i then tried with the string "hello*", it didn't work.
It seems to work about 80% of the work, but of course thats not good enough.
Any ideas?
-
Ok, i've managed to fix the problems i was having but now another problem.
I'm dynamic creating the huffman tree based on the frequency of the characters entered. The problem is once the program has ended the huffman tree to do the encoding/decoding is lost, so what is the best way to write out the huffman tree to the file?
Thanks
-
-