Home  |  About Us  |  Link To Us  |  FAQ  |  Contact

# Algorithm::Huffman 0.09

Date Added: July 09, 2010  |  Visits: 695

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 doesnt 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. Lets 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 its also possible to get e.g. the coding scheme: a 0 b 100 c 101 d 110 e 111.

 Requirements: No special requirements Platforms: Linux Keyword: Algorithm,  Algorithmhuffman,  Libraries,  Next Step,  Programming Users rating: 0/10