jueves, 25 de abril de 2013

[IT] Homework 4: Adaptative methods

For the homework of this week, we had to design an algorithm to turn our implementation of Huffman's Coding into an adaptative implementation of Huffman's coding.



Since the Huffman's coding needs to build a binary tree, there is a possibility to improve the three construction.
So, my approaching is to improve the tree construction everytime when a new node is added to it.

A common Huffman's coding tree looks like tihis:

When the structure of the tree is too deep,  we will get very large huffman codes for the less frequent letters.

Maybe, rebalancing the tree in each run, shorters codes could be generated and a little more space could be saved.

So, my approaching is center the huffman's coding in the frequencies of the character to reconstruct and rebalance the tree in each run and get a structure like this:

Where we can get more and shorter codes.

It's expected that this implementation will be more resource and time expensive, but also it's expected that the final results will be better.

There is no code :(

I don't have enough time to complete the homework this time, I hope don't fail with the other ones.

1 comentario:

  1. three != tree; en la idea no queda bien explicado qué en sí se pone en la salida al actualizar el árbol. 0+3.