Algorithm::Huffman 0.09

Algorithm::Huffman is a Perl extension that implements the Huffman algorithm.

SYNOPSIS

use Algorithm::Huffman;

my %char_counting = map {$_ => int rand(100)} ('a' .. 'z', 'A' .. 'Z');
# or better the real counting for your characters
# as the huffman algorithm doesn't work good with random data :-))

my $huff = Algorithm::Huffman->new(%char_counting);
my $encode_hash = $huff->encode_hash;
my $decode_hash = $huff->decode_hash;

my $encode_of_hello = $huff->encode_bitstring("Hello");

print "Look at the encoding bitstring of 'Hello': $encode_of_hellon";
print "The decoding of $encode_of_hello is '", $huff->decode_bitstring($encode_of_hello), "'";

This modules implements the huffman algorithm. The aim is to create a good coding scheme for a given list of different characters (or even strings) and their occurence numbers.

ALGORITHM

Please have a look to a good data compression book for a detailed view. However, the algorithm is like every good algorithm very easy.

Assume we have a heap (keys are the characters/strings; values are their occurencies). In each step of the algorithm, the two rarest characters are looked at. Both get a suffix (one "0", the other "1"). They are joined together and will occur from that time as one "element" in the heap with their summed occurencies. The joining creates a tree growing on while the heap is reducing.
Let's take an example. Given are the characters and occurencies.

a (15) b(7) c(6) d(6) e(5)

In the first step e and d are the rarest characters, so we create this new heap and tree structure:

a(15) de(11) b(7) c(6)

de
/
"0"/ "1"
d e

Next Step:

a(15) bc(13) de(11)

de bc
/ /
"0"/ "1" "0"/ "1"
d e b c

Next Step:

a(15) bcde(24)

bcde
/
"0"/ "1"
/
de bc
/ /
"0"/ "1" "0"/ "1"
d e b c

Next Step unifies the rest:

Huffman-Table
/
"0"/ "1"
/
/
bcde a
/
"0"/ "1"
/
de bc
/ /
"0"/ "1" "0"/ "1"
d e b c

Finally this encoding table would be created:

a 1
b 010
c 011
d 000
e 001

Please note, that there is no rule defining what element in the tree is ordered to left or to right. So it's also possible to get e.g. the coding scheme:

a 0
b 100
c 101
d 110
e 111

Product's homepage

Requirements:

· Perl