| Pregunta: | 33239 - ALGORITMOS DE COMPRESION |
| Autor: | Carlos Gomez Martin |
| Me gustaria conocer diferentes tipos de algoritmos de compresion para utilizarlos en la realizacion de un compresor de ficheros en C. Gracias de antemano. | |
| Respuesta: | Armando Matamoros Rosabal |
| Algoritmo de compresión de Huffman
Generalidades: Se trata de un algoritmo que puede ser usado para compresión o encriptación de datos. 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 se consigue 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 el receptor 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 cada cará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 cada elemento 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: Con los dos primeros árboles formar un nuevo árbol, cada uno de los árboles originales en una rama. Sumar las frecuencias de cada rama en el nuevo elemento árbol. Insertar el nuevo árbol en el lugar adecuado de 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, se añ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. | |