Smallest Huffman Binary Decoding Tree Header 
Author Message
 Smallest Huffman Binary Decoding Tree Header

I have written a compression programme to compress text(ASCII 0-255)
files using Binary Huffman Compress Method. However, I don't know how
to write the decode tree as the header of the file efficiently! (What
i mean by efficiently is to write to header that is as small as
possible!) Can anybody help me? Thanks in advance!

P.S. I don't know if it is the suitable newsgroup for me to ask such
question, but the programme is written in C, so I suppose I can ask it
here.



Sat, 02 Oct 1999 03:00:00 GMT  
 Smallest Huffman Binary Decoding Tree Header

Quote:

> I have written a compression programme to compress text(ASCII 0-255)
> files using Binary Huffman Compress Method. However, I don't know how
> to write the decode tree as the header of the file efficiently! (What
> i mean by efficiently is to write to header that is as small as
> possible!) Can anybody help me? Thanks in advance!

I'm no compression expert, so I'm sure this can be done better, but I
wrote something like this for a school project ages ago. I stored
the shape of the tree as a string of bits, so

         /\       is (l-r) down, down, down, up, down, down, up, etc
        /\          
       /\         which becomes 1110110100010010 (I think)
        /\

It should be possible to reconstruct the shape of the tree from
this. I then had a simple array of the symbols as they appeared
in left-to-right order. You also need a byte at the beginning
to say how many symbols occur in the tree. So the header looked
like

1 byte = number of symbols, N
N bits for the tree
N bytes for the array of characters

Note that this was for a program with a static tree derived from the
number of each kind of symbol in the whole file; if you update the
tree as you go along this wouldn't be suitable.

Quote:
> P.S. I don't know if it is the suitable newsgroup for me to ask such
> question, but the programme is written in C, so I suppose I can ask it
> here.

I don't think anyone will mind. You might want to try comp.compression
(or is it alt.compression?) as well, though.

-Edwin



Sat, 02 Oct 1999 03:00:00 GMT  
 
 [ 2 post ] 

 Relevant Pages 

1. Huffman coding/huffman tree

2. HELP with Huffman Tree

3. HELP with Huffman Tree Traversal - huff2.c (1/1)

4. HELP with Huffman Tree Traversal - huff2.c (1/1)

5. HELP with Huffman Tree Traversal - huff2.c (0/1)

6. HELP Huffman Tree Traversal

7. Help on Huffman trees 2

8. Help on Huffman trees

9. huffman tree source code

10. huffman tree/coding

11. AVL tree (Binary Balanced tree) using C or C++

12. Serialize small image/sound files into one binary file

 

 
Powered by phpBB® Forum Software