Desarrollo de una utilidad de compresión de datos basada en códigos Huffman con Haskell

Implementación de un programa de compresión de datos con codificación Huffman

• ¿Qué es un código Huffman?
  • Realiza compresión de datos al mapear cada carácter a una secuencia de bits única
  • Los caracteres que aparecen con frecuencia se mapean a secuencias de bits cortas, y los que aparecen rara vez a secuencias más largas
  • Ejemplo: en la cadena aaab, a se mapea a 1 y b a 0, por lo que se comprime como 1110

Códigos sin prefijo

• ¿Qué es un código sin prefijo?
  • Garantiza que ninguna palabra de código sea prefijo de otra
  • Ejemplo: en aaabc, a se mapea a 1, b a 00 y c a 01, por lo que se comprime como 1110001

Generación de códigos sin prefijo

• Cómo generar códigos sin prefijo
  • Colocar todos los caracteres como hojas de un árbol binario completo
  • Etiquetar la rama izquierda como 1 y la derecha como 0
  • La ruta desde la raíz hasta la hoja describe la palabra de código de cada carácter

Escritura del codificador

• Definición de tipos

  • Definición de los tipos Bit, Code, FreqMap, CodeMap, Weight, HTree
  • HTree está compuesto por Leaf y Fork

• Función de codificación

  • Función que convierte una cadena en bits
  • Usa FreqMap para calcular la frecuencia de cada carácter y, con base en eso, genera el árbol Huffman
  • Genera la palabra de código de cada carácter a partir del árbol Huffman

• Función de decodificación

  • Función que convierte bits en la cadena original
  • Usa el árbol Huffman para decodificar los bits de forma secuencial

Integración con archivos binarios

• Codificación de datos binarios
  • Usa el módulo Data.ByteString.Char8 para leer bytes como caracteres
  • Usa el codificador de texto para codificar datos binarios

Serialización

• Función de serialización
  • Convierte FreqMap y los bits en bytes reales y los guarda en un archivo
  • Usa la mónada Put para generar ByteString de manera eficiente

Deserialización

• Función de deserialización
  • Convierte los datos leídos del archivo en FreqMap y bits
  • Usa la mónada Get para deserializar FreqMap

Integración del código completo

• Funciones de compresión y descompresión de archivos
  • Función compress: lee el archivo, genera el mapa de frecuencias, codifica los datos y los guarda como archivo comprimido
  • Función decompress: lee el archivo comprimido, decodifica los datos y los guarda como archivo original

Mejoras

• Multithreading

  • Decodifica en paralelo las secciones del archivo
  • Agrega una tabla que especifica los límites de las secciones y el tamaño de decodificación esperado para permitir el procesamiento en paralelo

• Codificación de una sola pasada

  • Codifica mientras genera el mapa de frecuencias en tiempo real
  • No es necesario incluir el mapa de frecuencias al inicio del archivo

• Códigos Huffman canónicos

  • Decodifica con complejidad temporal O(1) indexando vectores en lugar de recorrer el árbol

• Generación de código más rápida

  • Si se intenta una codificación de una sola pasada, hay que acelerar la generación del mapa de códigos

Opinión de GN⁺

• Ventajas de la codificación Huffman

  • Permite una compresión de datos eficiente al mapear los caracteres frecuentes a secuencias de bits cortas
  • Puede manejar grandes volúmenes de datos minimizando el uso de memoria

• Ventajas de Haskell

  • Permite escribir código modular aprovechando las ventajas de la programación funcional
  • Puede optimizar el uso de memoria mediante evaluación perezosa

• Proyectos con funciones similares

  • Existen varias herramientas de compresión de datos como gzip y bzip2
  • Es importante comparar las ventajas y desventajas de cada herramienta para elegir la más adecuada

• Aspectos a considerar al adoptar nuevas tecnologías

  • Hay que elegir el algoritmo adecuado considerando el rendimiento y el uso de memoria
  • Se puede mejorar la eficiencia aplicando técnicas de optimización como la codificación de una sola pasada

[GN⁺]

Opiniones de Hacker News

• Existe un algoritmo in-place basado en arreglos que reduce la necesidad de asignar árboles y seguir punteros

  • Cuando aprendí el enfoque basado en árboles en la universidad, no sabía que había otra forma
  • El enfoque con árboles es intuitivo y útil, pero cuando necesitas procesar muchos datos rápidamente, usar arreglos in-place tiene más sentido
  • Referencia: "In-Place Calculation of Minimum-Redundancy Codes" (Moffat, Katajainen, 1995)

• No es técnicamente correcto decir que hay que evitar que una palabra de código sea prefijo de otra palabra de código

  • La clase de códigos únicamente decodificables es un superconjunto de los códigos prefijo
  • Por ejemplo, la versión invertida de un código prefijo sigue siendo decodificable de forma no ambigua
  • Código de ejemplo:

    a 1
    b 00
    c 10
    

  • El código de 'a' es prefijo del código de 'c', pero si se procesa al revés, sigue siendo decodificable de forma no ambigua

• Me pregunto si existe un tutorial similar que cubra funciones más avanzadas para escribir programas en Haskell, como transformadores de mónadas, lentes, etc.

• El curso de programación funcional de Coursera (Scala) ofrece una tarea similar sobre codificación Huffman

  • Enlace: Coursera Scala Functional Programming

• Usé códigos Huffman para ejecutar un programa de macros del procesador MICMAC con el mínimo de microciclos y microinstrucciones

  • Hice un histograma de las instrucciones macro y, con base en eso, escribí un programa de microcódigo de decodificación progresiva
  • En la práctica, probablemente habría sido lento e incómodo
  • La ventaja de los códigos Huffman es que permiten ajustar la profundidad de los prefijos según la distribución de los valores
  • Tuve que manejar predicción de saltos en un modelo de procesador no superescalar

• Más información sobre codificación Huffman: Rosetta Code Huffman Coding

• Pregunta para programadores de Haskell: me da curiosidad cómo es el rendimiento de Haskell para quienes buscan escribir código optimizado

  • En particular, me interesa el rendimiento en cálculo numérico con operaciones de matrices y aprovechando SIMD

• Gracias por compartirlo

• Hay un error tipográfico en la tabla de la sección "Creating prefix-free codes"

  • D debería ser '0010' (ahora aparece incorrectamente como '0110')
  • Fuera de eso, fue una lectura excelente

• Los códigos aritméticos son mejores en casi todos los aspectos

  • Se pueden implementar con menos RAM y menos código
  • Ofrecen mejores tasas de compresión y descompresión
  • Es más fácil actualizar dinámicamente la probabilidad de que aparezcan otros símbolos durante el stream
  • Los códigos Huffman se usaron porque se inventaron antes y la codificación aritmética estaba patentada
  • Ahora que las patentes expiraron, deberíamos usar un diseño mejor