A Golf question maybe? Huffman with a twistby demerphq (Chancellor)
|on Sep 03, 2001 at 05:50 UTC||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.
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.