La codificación Huffman es un algoritmo usado para la compresión de datos. Dicho algoritmo hace uso de una tabla de códigos para escribir un determinado símbolo, donde la tabla ha sido rellenada basándose en la probabilidad estimada de aparición de cada símbolo. A cada símbolo le corresponde un código (secuencia de 1 y 0) de longitud variable, puesto que los símbolos cuya aparición es menos frecuente reciben códigos más largos, mientras que los que aparecen más reciben códigos más cortos.
Para la ESCOM, el trabajo fue hacer la implementación voraz de dicho algoritmo, la cual tiene como variante que la comstrucción de la tabla de códigos es distinta para cada archivo, tomando solo en cuenta los símbolos contenidos en él y la cantidad de veces que aparecen.
He de decir que es de las prácticas más pesadas que he tenido en todo lo que llevo en la escuela, dentro del programa se hace uso de recursividad, operaciones a nivel de bits y estructuras de datos a más no poder:
- Se usa una lista para para ir almacenando las frecuencias de cada caracter
- Se usa un arreglo de árboles para generar el árbol único de códificación
- Se usa una cola para obtener el código asignado a cada símbolo
El código, que se encuentra en el proyecto analizando-algo en GitHub, está muy comentado tratando de hacerlo lo más entendible posible.
¡Saludos!
@fferegrino :)
No comments:
Post a Comment
¡Hey, gracias por tu comentario! No seas anónimo, inicia sesión para que te responda más fácilmente.