Huffman encoding algorithm

For this week's class theory of information we were given the task of building an implementation of the Huffman compression algorithm, this publication will serve as a way to report for the task.

Huffman compression algorithm

The Huffman algorithm is a coding or compression algorithm, which takes a group of characters and their frequencies and generates Huffman codes which are used to perform compression.
The algorithm works by using frequencies of each character to build a binary tree, the path made from the root of the tree is the Huffman code character associated with the character and is used for compression.
The algorithm works on the premise that the more frequently characters should have shorter Huffman codes.
To ensure that the most frequent characters are shorter, We create the tree gathering the leaves are less frequently as children of a new node, this continue until it is a single root node for all characters.

An example and an explanation of the method that helped me to understand the workings of the algorithm is in the following video on the channel www.youtube.com "soguw".

To unzip the file, I use a code implementation that used the tree and data bits, bit by bit is traversed the encoded text and each iteration moves through the tree according to bits of the encoded text. It runs from the root, until a final leave, the character of the leave is added to the file decrypted and we get back to the root, go finish it until the bits of the encoded file is traversed.
Code


program running

To demonstrate the program, this running will show the output for text "Huffman", the output of the program was:

max@juan-laptop:~/Dropbox/teoria_informacion/homework3$ python huffman.py

Encoding...

Encoding dictionary: {'a': '100', 'f': '01', 'H': '101', 'm': '110', 'n': '111', 'u': '00', 'root': ''}

Original text: Huffman

Encoded text: 101000101110100111

Compression ratio (compressed / original): 0.0128571428571

Decoding...

Original text: 101000101110100111

Decoded text: Huffman

And the program generated the following tree:

Testing
Now to test the algorithm did some graphs showing various steps of the run of the program, shown in red runs the program on a regular character, these were obtained from the common frequency of occurrence of certain characters in Spanish texts. Green is shown in the worst case, that is one in which the frequency is the same for all characters.

This shows the compression time in seconds, the red line shows a typical case and worst case green, time running time increase en normal case because it need more calculations to find the less frequency nodes, but it is good because if the difference between frequencies increase the compression works better:

This shows the decompression times in seconds:

The amount of memory used for compression:

This shows the compression ratio is the approximate amount of memory of the compressed file divided by the weight of the original file.

As you can see the time to compress and decompress increases for typical cases, but the memory used and clearly the compression ratio decreases.

References:
http://es.wikipedia.org/wiki/Algoritmo_de_Huffman
http://www.cprogramming.com/tutorial/computersciencetheory/huffman.html