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:

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
[download]

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:

            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
[download]

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.
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.

a 27 1
b 15 01
c 3  000
d 1  00100
e 1  00101
f 1  00110
g 1  00111
[download]

Would produce

a 27 1
b 15 01
c 3  001
d 1  00000
e 1  00001
f 1  00010
g 1  00011
[download]

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)

---

---

• Are you posting in the right place? Check out Where do I post X? to know for sure.
• Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:

  <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>

• Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
• Want more info? How to link or How to display code and escape characters are good places to start.