Homework 4: adaptive coding

For this week's class information theory and coding methods, we were given the task of thinking and to code a Huffman algorithm version made ​​of the last implementation made for the last class (link) to be able to function, taking as input the text online, this is getting character by character without actually knowing the frequency of all characters in the text.

My implementation of adaptative Huffman 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.

In order to function adaptively, what i added is very simple, before you can compress character by character, the program stored in a variable buffer indicated amount of characters, this is used to calculate an initial tree Huffman coding, only that it add a node with zero frequency as a character, the character which is given the name of 'Joker', it has low frequency and represents the characters that have not appeared yet since these also have low frequency.

Now once we have an initial tree we can encode character by character as they come, the idea is that if you get a character that is not in the tree, add two children to the node "Joker", the new character and another "Joker" node, if we find another character that is not in the tree we will add this in the same way in the last "Joker" node.

In this example draws only the nodes that are added, the final Huffman code gather all nodes "Joker for convenience but serves to explain how adding nodes that have not yet appeared. the added nodes are" Y "and" U ".

Code


Results
To display a graphical results, this graphs are made similar to those of the non-adaptive Huffman task. As initial buffer size chosen 10% of the input text, input texts length vary, red lines are the distribution of letters in Spanish distribution, and the green uniform distribution, these distributions to show Huffman switching between Normal and my implementation of adaptive Huffman.

 The compression ratio estimated from the data compresed split between original data:

 

Time data encoding of the complete characters:

Time data decoding of the complete characters:

Size of the data obtained:

Suggestions of improvement
My implementation is very simple but I think it could be improved by:

• Predefined frequencies:Choosing input character frequencies knowing what kind of text is, for example if it is a common text in Spanish there are many frequency tables, as input would receive the characters more frequent in that kind of text.
   
• Adaptive node adding:
  Seeking a way to accommodate in a adaptive way nodes which are not found in the tree.

References:
http://elisa.dyndns-web.com/~elisa/teaching/comp/info/adaptive.pdf