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)

In reply to A Golf question maybe? Huffman with a twist by demerphq

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.