No such thing as a small change | |
PerlMonks |
A Golf question maybe? Huffman with a twistby demerphq (Chancellor) |
on Sep 03, 2001 at 05:50 UTC ( [id://109803]=perlmeditation: print w/replies, xml ) | Need Help?? |
Well, I dont know if this counts as a golf question, but considering BooK's obfus Huffman encoder i thought maybe people would find this interesting.
Ok to steal a useful diagram from BooKs explaination of Huffman encoding we have the following tree:
If we assume a left branch represents a 0 then for D we have 00100. What we want to do is to end up with a tree that has the same properties as a huffman tree, but with its branches organised so that D would be 00000. More specifically we want to produce a tree so that a depth first left iteration over the leafs gives us the elements ordered from least frequent to most frequent. This type of ordering would conver the huffmann tree into the following: In this case the change is trivial, a swap of one node. But for larger alphabets and more evenly distributed weights it is not so.
The challenge then is to create a program that fixes a huffmann tree. The input should be a list of symbols weights and paths from a huffman encoder and the ouptut a similer list but adjusted as stated ealier. Would produce
I have implemented a solution to this but I will hold out on posting it till I see some replies. Bonus points if you can figure out a way to build the tree properly *without* using the path information provided, merely the weights.
UPDATE
Yves
Back to
Meditations
|
|