Algoritmo de compresión de huffman

Algoritmo de compresión de Huffman
Por: Salvador Pozo Coronado
[Principal] [Índice de artículos]
Generalidades:
Se trata de un algoritmo que puede ser usado para compresión o encriptación dedatos.
Este algoritmo se basa en asignar códigos de distinta longitud de bits a cada uno de los caracteres de un fichero. Si se asignan códigos más cortos a los caracteres que aparecen más a menudo seconsigue una compresión del fichero.
Esta compresión es mayor cuando la variedad de caracteres diferentes que aparecen es menor. Por ejemplo: si el texto se compone únicamente de números o mayúsculas,se conseguirá una compresión mayor.
Para recuperar el fichero original es necesario conocer el código asignado a cada carácter, así como su longitud en bits, si ésta información se omite, y elreceptor del fichero la conoce, podrá recuperar la información original. De este modo es posible utilizar el algoritmo para encriptar ficheros.
Mecanismo del algoritmo:
• Contar cuantas veces aparece cadacarácter en el fichero a comprimir. Y crear una lista enlazada con la información de caracteres y frecuencias.
• Ordenar la lista de menor a mayor en función de la frecuencia.
• Convertir cadaelemento de la lista en un árbol.
• Fusionar todos estos árboles en uno único, para hacerlo se sigue el siguiente proceso, mientras la lista de árboles contenga más de un elemento:
o Con los dosprimeros árboles formar un nuevo árbol, cada uno de los árboles originales en una rama.
o Sumar las frecuencias de cada rama en el nuevo elemento árbol.
o Insertar el nuevo árbol en el lugar adecuadode la lista según la suma de frecuencias obtenida.
• Para asignar el nuevo código binario de cada carácter sólo hay que seguir el camino adecuado a través del árbol. Si se toma una rama cero, seañade un cero al código, si se toma una rama uno, se añade un uno.
• Se recodifica el fichero según los nuevos códigos.
Veamos un ejemplo:
Tomemos un texto corto, por ejemplo:
"ata la jaca a la...