Algorimo de Compresión Huffman

La Necesidad del ser humano de procesar mayor cantidad datos en alguna computadora ha causado un problema debido  a que se ha maximizado la cantidad de información generada y transmitida, este incremento ha llevado a la necesidad de establecer mecanismos que permitan aprovechar de manera más eficiente los recursos a la hora de generar o transmitir datos.

Para resolver este problema representantes del mundo de la ciencia de la computación han trabajando en  la codificación eficiente de los símbolos (alfabeto), obteniendo representaciones de la información original utilizando una menor cantidad de unidades de información (bits).

 

Existen dos formar para comprimir información una es con pérdida de datos y la otra es sin pérdida de datos.

 

La compresión con pérdida de datos puede llegar a reducir el número de bits usados para su representación en mayor grado que los algoritmos de compresión sin pérdida, el problema está en que al reducir con pérdida de datos la reconstrucción será solo una aproximación de los datos originales. Por otra parte esta la codificación sin pérdidas de binarios será la reconstrucción exacta.

Shannon establece una cota inferior de la longitud del código en términos de Entropía (el mínimo al que puede llegar la información, a ser comprimida para que sea sin pérdida)  y Huffman genera un ambicioso algoritmo el cual comprime sin pérdida de datos.

¿Cómo lograr una codificación eficiente de los datos?, supongamos  que un texto posee los caracteres A, B, C., vamos a representar cada carácter con 2 bits, A=00; B=01; C=10, al hacer esto ya estamos proporcionando un ahorro en bits a la hora de representar estos caracteres, a diferencia de la representación ASCII  o Unicode la cual usaría 8 bits o más para cada carácter. Bajo esta misma lógica se puede representar un alfabeto que contiene N símbolos diferentes mediante log2(n) bits por símbolo.

Descargar Informe

Descargar Programa C++