Furthermore, you store the determined tree with your compressed data so that you know how to decompress it later. This is sometimes referred to as a dictionary.

For decompression, with every bit you traverse the tree until you reach a leaf node. When you reach the leaf, output the uncompressed byte at that node and start traversing from the root of the tree again.

EDIT: ASCII amateurs [grin]

    (root)     /  \     0    1 (c)   / \   0   1 (a) (b)

Quote:Original post by McZ
when decompressing later how can I know how many bits I need to read before I get to a leaf?

bits: 0100100101001010010111001101011010101

this could generate many different trees because you could read all bits and just move left/right depending on 0/1 and then ju finaly hit a leaf at the end or you could read 3 bits and then start over at the top, or 5 bits and so on.

hmm, It sounds like you don't quite understand the principle yet.

You don't know how many bits you need to read before you get to a leaf, that's the whole point. You read 1 bit at a time, and if it's a zero you go left, if it's a one you go right, and if you hit a leaf then you output the symbol and the very next bit immediately tells you the first way to branch from the top of the tree again, for the next symbol. There only way for it to produce multiple different out symbol lists, is if you were to start from somewhere other than the very start of the bitstream when decompressing. You must always start from the start.

OK, let's take this from the top. You have the following string that you want to compress:

abccccba

And you have built the following tree (through whatever method) to compress the data with:

(root)
/ \
0 1 (c)
/ \
0 1
(a) (b)


Firstly, since you need the dictionary to decompress your data at the other end, you write out your dictionary. You can use one of the methods Enigma has mentioned above, or some other creative way of your own. All that matters is that you can reconstruct the same tree in the decompressor as you created in the compressor.

Next, you start compressing the data. You read in a symbol, look up the codeword for that symbol (eg, 'a'=00), and then write those bits to your output stream. Wash, rinse, repeat. This will give you the following output bits:

000111110100

You now have a compressed file that starts off with a description of your dictionary and the compressed data. The decompress this, first read your dictionary info and reconstruct your tree. Now start at the top of the tree and read your compressed data 1 bit at a time, taking the left/right branch for 0/1. When you reach a leaf node stop reading bits, spit out the symbol at that leaf node (the uncompressed data), move back to the top of your tree and start reading bits again. Keep going until you run out of bits and you (should) end up with your original data.

Going through the above compressed data, we start at the top of the tree. Read in the 0 so take the left branch, read in another 0 and take the next left branch. We find ourselves at a leaf node (a) so spit out an 'a' and go back to the top of the tree. Read in a 0 -> left branch. Read in a 1 -> right branch. We're at a leaf, spit out 'b', back to the top. Read in a 1 -> right branch, but we don't read in another bit because we've already reached a leaf so we spit out 'c' and go back to the top. Doing this, there is no way to confuse the bits '01' with '1'.

In general for a correct (but not necessarily optimal) Huffman tree, the codeword for any 1 symbol CANNOT be found at the start of the codeword for any other symbol. In the example tree, the codeword for 'c' is '1' so no other codeword can start with a '1'. Alternatively, if in some other tree 'c' was '01011', then no other codeword could start with the sequence '01011'. This is direct result of symbols only being on leaf nodes.