sevensven has it right on the nose. The only missing part is what the encoding algorithm is. It's called 'Huffman Compression' or a 'Huffman Tree'...named after some guy...named...Huffman...that's it. Anyways, here's an explanation of the algorithm (for those that are interested.

/me digs out notes...

The basic point of the algorithm is to compress the data by substituting the shortest string of bits for the most commonly occurring byte.

So, step one is to make a frequency chart of the data (this isn't the output BTW for those that haven't ran it yet).

J u s t  a n o t h e r  p e r l  h a c k e r
^ ^ ^ ^  ^ ^ ^   ^ ^ ^  ^     ^      ^ ^
1 1 1 2  2 1 1   2 3 3  1     1      1 1
[download]

sort low to high by occurrence

1 (j)
1 (u)
1 (s)
1 (n)
1 (o)
1 (p)
1 (l)
1 (c)
1 (k)
2 (t)
2 (a)
2 (h)
3 (e)
3 (r)
[download]

combine the two smallest 'occurrences', add their frequencies, and the resort the list.

1 (s)
1 (n)
1 (o)
1 (p)
1 (l)
1 (c)
1 (k)

  j
2<
  u

2 (t)
2 (a)
2 (h)
3 (e)
3 (r)
[download]

repeat until you end up with a tree like so

               j
             <
            /  u
           0 
          / \
         /   t 
        0                   Isn't ASCII art wonderful?
       / \      o
      /   \   <
     /     \ /  p
    /       0 
   /         \  s
  /           <
 /              n
21
 \             k
  \           /
   \         0
    \       / \  l
     \     0   <
      \   / \    c
       \ /   e
        0
         \   r
          \ /
           0
            \
             \  a
              <
                h
[download]

Where 21 is (hopefully) the total number of bytes of input. I say hopefully, because, yes, I did built both trees by hand.

Ok, so now that we have our tree (tilt your head 90 degrees to the left), you'll notice that the most common bytes (r and e) have the lowest depth in the tree. A byte's encoding is found by walking the tree depth first to the leaf of the byte...keeping track of the direction either left/down (0) or right/up (1). So, the encoding for 'e' is '010' and 'o' is '1011'. Get it?

Thus the sequence 'perl' (4 bytes) could be encoded as 101001000101101, or 15 bits.

Decoding requires that you have the tree that the stream is encoded against, in this case $h in the code. Then you descend the tree one bit at a time, until you hit a leaf node and then you start over at the top.

1010  = p
010   = e
010   = r
01101 = l
[download]

I alluded to sevensven (while were we talking in the CB) that we were both using a program right now that has a Huffman decompressor in it. Any guesses? The web browser. Unless you use lynx, odds are you can display .jpg files...and they're compressed with...bingo...a Huffman tree.

HTH

/me leaves the lectern

/\/\averick
perl -l -e "eval pack('h*','072796e6470272f2c5f2c5166756279636b672');"

---

---

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