Beefy Boxes and Bandwidth Generously Provided by pair Networks
Think about Loose Coupling

comment on

( #3333=superdoc: print w/replies, xml ) Need Help??

Cet assombrissement est soumis au nom de canal assombri.

This program perform a Huffman compression to its STDIN or to the files given on the command-line. One drawback is that I was too lazy to write the code to output the compressed data of different files to different output files...


First $/ and $" are undefined, so that the first use of the diamond operator slurps the whole file, and that the double-quoting of array(slice)s don't result in unwanted spaces. map is used instead of for because I like returning lists in a void context. Furthermore, it saves a few ()'s.

Stéphane Payrard (of OPC3 fame) taught me that @0 is a perfectly valid array. That's a good enough reason to use it. The same goes for %0.

Thanks to O::Deparse, I learned a few tricks like writing $a->[1] as $$a[1]... (Take this as a proof that one can learn something through obfuscation.) Naturally, I doubt that O::Deparse helped you much, since here it spits out:

Can't call method "sibling" on an undefined value at /usr/lib/perl5/5.6.0/i386-linux/B/ line 257.
CHECK failed--call queue aborted.

I must admit I don't know at all how it is possible. But, hey that's one more hurdle on your way to understanding this program.

So, %0 holds the count for each character (the character is the key, the count is the value). Given the character, we create a array containing one array by character, containg: one sub-tree of the Huffman tree (at first, it's only a leaf (i.e. the character itself)), its weight, and a string containing all the sub-tree leaves.


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 each
       /\  /\            sub-tree noted at its root) drawn on the left.
      D  EF  G

This tree is encoded at the beginning of the file in the following manner:

            01           Two bits are used by node (in the previous example,
            /\           there are 6 nodes and 7 leaves), one for each branch.
          01  A
          /\             0 means non-terminal node and 1 means terminal node
        10  B            (i.e. there is a leaf hanging there).
       C 00              Our tree looks like the one on the left.
       11  11            The recursive procedure that builds the tree
       /\  /\            represents the data in the following manner:
      D  EF  G           [left-leaf][sub-tree][right-leaf]

Applying this procedure (named _) recursively, we obtain: 010110C0011DE11FGBA (every character being replaced with its bit representation).


While we build the tree (line 2 and 3), we also create a HASH %t which keys are the characters in the file to be compressed and which values are the bit string (the path in the tree). This path is constructed as we creare the tree itself. $; and $/ are used to create the needed 0's and 1's... $/ equals 2 (whose modulus helps), and $; is first undefined and is an even number each time we need it again in our map.

Finally, we perform a substitution on the data, replacing each character by the bit string that represents the path in the tree. The compressed file is the concatenation of the length of the data (since pack will pad the file with null bits, we need this information for the decompressor), the dictionary (which is self-explaining: no need for its size), and the data itself.


This program was designed to have as little distinct characters as possible, and also so as some character appear really a lot. It was too difficult for me to write it so that the respective probability of each character would be a negative power of 2 (1/2**$k if you like), which is when Huffman encoding performs at its best. My goal was to write a compressor / decompressor all in one obfuscation. Alas, Huffman doesn't perform well enough (it's that lousy dictionary's fault!). OK, next time I'll try with Lempel-Ziv...


crazyinsomniac asked me to add this link to a site with explanations and a Java animation.

In reply to Huffman encoder SOLUTION by BooK
in thread Huffman encoder by BooK

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

  • 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 or How to display code and escape characters are good places to start.
Log In?

What's my password?
Create A New User
Domain Nodelet?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others romping around the Monastery: (5)
As of 2022-08-18 00:40 GMT
Find Nodes?
    Voting Booth?

    No recent polls found