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.The Huffman algorithm pairs the sub-trees by weight. As long as there +are more than one sub-tree, pairs the lightest two into one sub-tree. + I chose to have the lightest branches on the left (bit 0). 49 For a file containing: 27 A /\ 15 B 22 A 3 C /\ 1 D 7 B 1 E /\ 1 F C 4 1 G /\ 2 2 the resulting tree is (with the weight of eac +h /\ /\ sub-tree noted at its root) drawn on the left +. D EF G
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.49 For alphabet and: 27 A /\ and weights as so: 15 B 22 A 3 C /\ 1 D 7 B 1 E /\ 1 F 4 C 1 G /\ 2 2 Ordered so that the most frequent /\ /\ have the least 0's in their path D EF G A=1 C=001 E=00001 G=00011 B=01 D=00000 F=00010
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.
Input can be matched with the regex /^\s*(\w+)\s+(\d+)\s+([01]+)\s*$/ where $1 is the symbol, $2 is the weight of the symbol and $3 is the path (in 1's and 0's) in the huffman tree.
Would producea 27 1 b 15 01 c 3 000 d 1 00100 e 1 00101 f 1 00110 g 1 00111
a 27 1 b 15 01 c 3 001 d 1 00000 e 1 00001 f 1 00010 g 1 00011
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
A little tip: Sometimes you miss the forest for the trees.
Yves
--
You are not ready to use symrefs unless you already know why they are bad. -- tadmc (CLPM)
|
---|
Replies are listed 'Best First'. | |
---|---|
Re (tilly) 1: A Golf question maybe? Huffman with a twist
by tilly (Archbishop) on Sep 04, 2001 at 20:30 UTC | |
by demerphq (Chancellor) on Sep 04, 2001 at 20:51 UTC | |
by tilly (Archbishop) on Sep 04, 2001 at 21:03 UTC | |
by demerphq (Chancellor) on Sep 05, 2001 at 02:52 UTC | |
by tilly (Archbishop) on Sep 05, 2001 at 19:40 UTC |