Traversing Huffman Tree

[A_StClaire_]

hi all,

I'm trying to implement Huffman coding on letters of a string. I've
written functions to define the initial leaf nodes (letters and their
frequencies) and to sort them. I've also put together the actual tree
with its appropriate nodes and child nodes.

however I'm having some trouble developing a means of traversing the
tree itself to create the binary key table. i.e., how would I know how
many levels the tree has? this will change with every different string
length. should I store the number of levels in a variable? should I
write a recursive function?

thx for your help

 

[Flavius Vespasianus]

(e-mail address removed) wrote in @z34g2000cwc.googlegroups.com:

hi all,

I'm trying to implement Huffman coding on letters of a string. I've
written functions to define the initial leaf nodes (letters and their
frequencies) and to sort them. I've also put together the actual tree
with its appropriate nodes and child nodes.

however I'm having some trouble developing a means of traversing the
tree itself to create the binary key table. i.e., how would I know how
many levels the tree has? this will change with every different string
length. should I store the number of levels in a variable? should I
write a recursive function?

The best explaination I have seen is in the JPEG standard which can be
found (but shouldn't be) on-line. The fact is you don't need an actual tree
to encode/decode.

The image library at www.colosseumbuilders.com has some examples.

 

[A_StClaire_]

I've got this resolved.

unfortunately that moves me to another problem. how do I distinguish
between Huffman codes 10 and 010, for example, after these values have
been assigned to char's?

I'm writing char's to my output file as part of the compression process
but when I read them back char's that had 10 and 010 assigned to them
cannot be distinguished.

thx

 

[pepp]

The whole point of huffman code is that you dont get any ambiguity.
i.e. Make sure that no key is a substring for any other key.

to get a better understanding at huffman algorithm you can do follow.
1. read a good algorithm book.
2. look into 2^
3. learn logs

 

[A_StClaire_]

The whole point of huffman code is that you dont get any ambiguity.
i.e. Make sure that no key is a substring for any other key.

right but I think that's "no key can be a prefix of any other key", not
"substring". so 10 and 010 shouldn't be a problem as far as I can
tell.