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

 (lazamar.github.io)
1 puntos por GN⁺ 2024-07-06 | 1 comentarios | Compartir por WhatsApp
  • Implementa un compresor con Huffman coding en apenas 150 líneas de Haskell, mostrando una estructura que procesa codificación y decodificación de archivos binarios arbitrarios con memoria constante
  • El código Huffman asigna secuencias de bits cortas a los valores más frecuentes y, con la condición de prefix-free code, permite que el decodificador interprete los bits sin ambigüedad
  • La implementación usa FreqMap, HTree y CodeMap para construir el árbol a partir de la tabla de frecuencias, y genera resultados de forma gradual gracias a la evaluación perezosa de concatMap y un decodificador recursivo
  • Los archivos binarios se manejan con Data.ByteString.Char8, tratando los bytes como si fueran Char; al inicio del resultado comprimido se serializa la tabla de frecuencias y la secuencia de bits se guarda con padding a nivel de byte
  • En las pruebas, War and Peace pasó de 3.2M a 1.9M, y el binario ghcup de 106M se redujo a 84M; el máximo resident set size observado fue menor a 300KB

La idea básica de la compresión con códigos Huffman

  • El objetivo es implementar una utilidad de compresión de datos usando Huffman coding en unas 150 líneas de Haskell
  • El código completo está publicado en este repositorio de GitHub
  • El código Huffman asigna una secuencia de bits única a cada carácter o valor
    • Los valores que aparecen con frecuencia usan secuencias de bits cortas
    • Los valores raros usan secuencias de bits largas
    • El efecto de compresión aparece cuando los valores comunes se representan con menos bits que en su forma original
  • En el ejemplo aaab, si se define a = 1 y b = 0, el resultado es 1110
    • Es un ejemplo en el que una cadena que necesitaría 4 bytes en UTF-8 se representa en medio byte

Prefix-free code y árbol de Huffman

  • Para que la decodificación no sea ambigua, ninguna codeword puede ser prefijo de otra
    • Por ejemplo, en aaabc, si se asigna a = 1, b = 10, c = 01, entonces 101 podría interpretarse ambiguamente como ac o ba
  • Un prefix-free code puede representarse como un árbol binario completo
    • Todos los valores se colocan en las hojas
    • La arista izquierda se etiqueta con 1 y la derecha con 0
    • La ruta desde la raíz hasta una hoja se convierte en la codeword de ese valor
  • El árbol de Huffman se construye agrupando desde abajo los valores menos frecuentes
    • Cada carácter se convierte en un nodo junto con su weight, que es la cantidad de apariciones
    • Se agrupan en un árbol los dos nodos con menor weight
    • El weight del nuevo árbol es la suma de los weights de ambos nodos
    • Se repite hasta que solo queda un árbol
  • Con este proceso, los valores más frecuentes quedan más cerca de la raíz y terminan con codewords más cortas

Estructura del codificador en Haskell

  • Los tipos principales de la implementación son Bit, Code, FreqMap, CodeMap, Weight y HTree
    • Bit es One o Zero
    • Code es [Bit]
    • FreqMap es Map Char Int y guarda la cantidad de apariciones por carácter
    • CodeMap es Map Char Code y guarda la codeword de cada carácter
    • HTree es Leaf Weight Char o Fork Weight HTree HTree
  • HTree puede compararse según su weight, lo que simplifica el ordenamiento y la inserción durante la construcción del árbol
  • countFrequency calcula cuántas veces aparece cada carácter en una cadena
  • buildTree convierte el FreqMap en una lista de hojas, la ordena y combina repetidamente los dos nodos más pequeños para crear el árbol de Huffman
  • buildCodes recorre el árbol y genera la codeword de cada carácter, agregando One a la izquierda y Zero a la derecha
  • encode :: FreqMap -> String -> [Bit] construye el árbol y el mapa de códigos a partir de FreqMap, y reemplaza cada carácter de la entrada por su codeword para producir una lista de bits

Procesamiento gradual con evaluación perezosa

  • La transformación central de la codificación es concatMap codeFor str
    • Conceptualmente, convierte [Char] en [[Bit]] y luego lo aplana de nuevo a [Bit]
    • Gracias a la evaluación perezosa de Haskell, no funciona como un proceso que primero codifica toda la entrada y luego la concatena
  • Las listas pequeñas avanzan de izquierda a derecha y se aplanan dentro de una gran lista de resultado
    • El tail de la lista de resultado queda como un thunk aún no evaluado
    • La siguiente parte se calcula cuando se solicita
  • El decodificador genera la salida de forma gradual de la misma manera
    • decode :: FreqMap -> [Bit] -> String avanza a la izquierda o derecha del árbol según los bits
    • Al llegar a una hoja, emite el carácter y vuelve a empezar desde la raíz
    • Repite hasta que la cantidad total de caracteres decodificados sea igual al weight del árbol de Huffman
  • El decodificador no se detiene al final de la lista de bits de entrada, sino según la cantidad de caracteres
    • Esto se debe a que en la serialización se agregan bits de padding al final para alinear a bytes
  • La función go, al llegar a una hoja, devuelve una lista cuyo head ya se conoce junto con la llamada recursiva en el tail, por lo que el resultado puede evaluarse antes de que termine toda la recursión

Manejo de archivos binarios y serialización

  • Los datos binarios pueden verse como una repetición de uno entre 256 bytes posibles
  • Data.ByteString.Char8 permite tratar un ByteString con operaciones de Char, y cada Char se trunca a 8 bits
    • Gracias a esta propiedad, el mismo codificador para texto puede aplicarse también a datos binarios sin grandes cambios
  • En el archivo comprimido se guarda primero el FreqMap necesario para decodificar, y después la secuencia de bits codificada
  • serializeFreqMap escribe la tabla de frecuencias con el siguiente formato
    • La longitud del mapa se guarda como Word8, pero almacenando el valor menos 1 para ajustar el rango representable
    • Cada entrada guarda la clave como Word8 y la frecuencia como entero big-endian de 64 bits
  • serialize genera un ByteString con la mónada Put del paquete binary
    • Lee los bits uno por uno para llenar un byte
    • Cuando completa 8 bits, los escribe con putWord8
    • El último byte se rellena con Zero en el espacio sobrante

Deserialización y estrategia de memoria constante

  • deserializeFreqMap lee la tabla de frecuencias serializada usando Data.Binary.Get
    • Primero lee la longitud y le suma 1 para obtener la cantidad real de entradas
    • Luego reconstruye el FreqMap leyendo en cada entrada una clave Word8 y un valor de frecuencia de 64 bits
  • El resto de la entrada no se procesa con Get; en cambio, se toma desde el offset del ByteString y se convierte en una lista de bits
  • deserialize devuelve (FreqMap, [Bit]), donde [Bit] es una lista perezosa que no se calcula completa de inmediato
    • Si se pide la longitud de esa lista, habría que evaluarla completa, así que conviene evitarlo
  • La razón para no usar Get con toda la entrada es que el bind de la mónada fuerza el orden
    • Eso llevaría a una estructura donde solo puede devolverse la lista después de procesar toda la entrada
  • La estrategia de memoria constante consiste en evaluar solo la siguiente pequeña parte de la entrada cada vez que se escribe un bit de salida
    • Se evalúa una parte del ByteString y se lee ese fragmento del archivo
    • La salida procesada se escribe al archivo
    • Los fragmentos de entrada y las listas de bits que ya no se referencian pueden ser liberados por el garbage collector
  • FreqMap tiene como máximo 256 entradas a nivel de byte, así que el overhead se mantiene de tamaño constante

CLI para comprimir y descomprimir archivos

  • compress lee el archivo de entrada dos veces
    • En la primera pasada construye el FreqMap
    • En la segunda pasada codifica los datos usando ese FreqMap
  • Si el archivo se leyera una sola vez y se pasara la misma referencia a encode, habría que conservar la referencia a toda la entrada incluso después de crear la tabla de frecuencias, por lo que todo el archivo tendría que permanecer en memoria
  • Leerlo dos veces permite liberar progresivamente la memoria procesada tanto durante la generación de la tabla de frecuencias como durante la codificación
  • decompress lee el archivo comprimido, obtiene FreqMap y la lista de bits con deserialize, y guarda el resultado de decode en un archivo
  • El CLI recibe los siguientes argumentos
    • compress FILE FILE
    • decompress FILE FILE
  • Como solo usa paquetes incluidos con GHC, puede compilarse sin cabal usando ghc -O2 Main.hs -o main

Resultados de ejecución y uso de memoria

  • En la prueba con el archivo de texto War and Peace de Tolstói, el resultado tras comprimir y descomprimir es idéntico según diff
    • Original WarAndPeace.txt: 3.2M
    • Archivo comprimido: 1.9M
    • Archivo descomprimido: 3.2M
    • El tamaño se reduce aproximadamente un 40%
  • También funciona con un archivo binario más grande, ghcup
    • Original ghcup: 106M
    • Archivo comprimido: 84M
    • Archivo descomprimido: 106M
    • El tiempo de compresión es de unos 15.173 segundos y el de descompresión de unos 14.555 segundos
  • Según +RTS -s, el máximo resident set size durante el procesamiento de ghcup fue menor a 300KB
  • Ambos procesos usan menos de 10MB de memoria durante la ejecución
  • La distribución del tiempo puede verse en este perfil

Puntos que podrían mejorarse

  • El objetivo de la implementación fue crear una utilidad de compresión lo más simple y clara posible; para mejorar la eficiencia haría falta una implementación más compleja
  • Algunas mejoras posibles son las siguientes
    • Multithreading: decodificar en paralelo segmentos del archivo, aunque como no puede saberse el límite de una codeword desde una posición arbitraria, habría que agregar al inicio del archivo comprimido una tabla con fronteras de segmentos y tamaños esperados de decodificación
    • Codificación en una sola pasada: comenzar con una tabla de frecuencias inicial en la que todos los bytes tengan frecuencia 1, y cada vez que se vea un byte, codificarlo primero y luego actualizar la tabla de frecuencias
    • Canonical Huffman codes: en lugar de recorrer el árbol en O(log n) al decodificar, usar los códigos como índices de un vector para buscar acceso O(1); más detalles en Canonical Huffman code
    • Generación de códigos más rápida: en la codificación de una sola pasada, habría que construir CodeMap mucho más rápido, y existe una forma más eficiente de generar codewords sin construir el árbol
  • En el futuro, usando LZ77 como esquema de diccionario adaptativo, sería posible implementar gzip junto con códigos Huffman

Lecturas relacionadas

1 comentarios

 
GN⁺ 2024-07-06
Opiniones de Hacker News

  • Para esta tarea existe un algoritmo in situ basado en arreglos que reduce la asignación de árboles y el seguimiento de punteros.
    Cuando aprendí en la universidad el enfoque basado en árboles, no sabía que existía otra forma, y me pregunto si a otras personas también les pasó.
    El método con árboles es intuitivo y ayuda a entender, pero las situaciones en las que la compresión es más importante suelen ser aquellas con muchos datos y en las que uno quiere ejecutar rápido, así que manejarlo con arreglos in situ puede tener más sentido.
    In-Place Calculation of Minimum-Redundancy Codes, Moffat, Katajainen, 1995
    http://hjemmesider.diku.dk/~jyrki/Paper/WADS95.pdf

    • En general, también vale la pena consultar On the Implementation of Minimum Redundancy Prefix Codes, de Moffat y Turpin.
      Charles Bloom lo recomendó enfáticamente y más tarde agregó una explicación.
      https://cbloomrants.blogspot.com/2010/08/08-12-10-lost-huffm...
    • En el estándar JPEG ITU T.81 (1992) este algoritmo se explica con un diagrama de flujo, así que parece que el conocimiento sobre Huffman basado en arreglos ya era algo conocido en cierta medida en los años 80.
    • Se menciona al final del artículo y se deja como ejercicio para el lector.
    • La frase “me pregunto si eso también aplica a algunos de ustedes” suena como una list comprehension.

  • Decir que “para no ser ambiguo, ningún code word debe ser prefijo de otro code word” no es estrictamente correcto.
    Los llamados códigos unívocamente decodificables no son ambiguos y son un superconjunto de los códigos de prefijo.
    Un ejemplo simple es un código obtenido invirtiendo un código de prefijo. En el ejemplo del artículo sería a 1, b 00, c 10.
    Aunque el código de a es prefijo del código de c, si se procesa la secuencia de códigos en orden inverso, todavía se puede decodificar sin ambigüedad. Sería interesante ver un código unívocamente decodificable que no sea ni de prefijo ni su versión inversa.

    • Si se compone un código de prefijo con un código de sufijo, se pueden crear códigos así sin que sean innecesariamente ineficientes.
      Si A 0, B 01, C 11, y luego a A 0, b BA 010, c BB 0101, d BC 0111, e C 11, queda {a=0,b=010,c=0101,d=0111,e=11}.
      Es claramente unívocamente decodificable, porque se puede decodificar unívocamente desde atrás, como 0->A, y luego volver a decodificar unívocamente desde adelante, como A->a.
      En términos de longitud es igual al código de prefijo óptimo {a=0,b=110,c=1110,d=1111,e=10}, así que es uno de varios códigos óptimos para la misma distribución de probabilidades.
      Al mismo tiempo, por a=0 y b=010, no es ni código de prefijo ni código de sufijo. De hecho, en general no es posible decodificar incrementalmente en ninguna dirección, y para distinguir cee...ee? de bee...ee?, o ?cc...cca de ?cc...ccb, puede requerirse mirar hacia adelante de forma infinita incluso para determinar un solo símbolo.
      No sé si al componer un código de prefijo óptimo independiente con un código de sufijo óptimo independiente siempre se conserva la optimalidad, pero en los casos más simples que se me ocurrieron, salvo los códigos degenerados 1:1, funcionó bien.
    • Es un problema más interesante de lo que parece. Para empezar, como respuesta adversarial se puede dar un ejemplo como a 101, b 1.
      Pero es un mal código, porque siempre conviene más usar a=1, b=0.
      La desigualdad de Kraft indica los conjuntos de longitudes de código que pueden hacerse unívocamente decodificables, y con codificación Huffman se pueden alcanzar todos esos conjuntos. Así que, si se está haciendo codificación de símbolos, no hay razón para usar códigos que no sean de prefijo, salvo que se cambie a otro método como ANS o codificación aritmética.
      Eso sí, no sé si existe un código unívocamente decodificable que tenga el mismo conjunto de longitudes que un código Huffman óptimo, pero que no sea ni código de prefijo ni su inverso, un código de sufijo.
      Si le dedicara tiempo, miraría https://en.wikipedia.org/wiki/Sardinas-Patterson_algorithm y trataría de encontrar un contraejemplo por fuerza bruta o de sacar una demostración a partir de cómo funciona el algoritmo.
    • Es un ejemplo raro, pero me pregunto qué tal a 1, b 101.
      No es libre de prefijos ni libre de sufijos, pero cada vez que aparece 0 corresponde a la aparición de b.
      Por supuesto, es evidentemente ineficiente, así que al final la pregunta es si existe un código óptimo que no sea libre de prefijos ni libre de sufijos.
      Buscando, vi que en https://blog.plover.com/CS/udcodes.html dan como ejemplo de código unívocamente decodificable a 0011, b 011, c 11, d 1110.
      La única relación de prefijo es que c es prefijo de d, así que está “casi” libre de prefijos. Si el mensaje empieza con 1, parecería que basta con encontrar el primer 0 y ver si la cantidad de 1 anteriores es impar o par, así que entiendo que sea unívocamente decodificable.
      Pero no recuerdo cómo mostrar para qué distribución de probabilidades es óptimo, porque tengo demasiado oxidados mis conocimientos de criptografía.
    • Es interesante, pero supongo que la razón por la que normalmente no se usa es que uno puede tener que leer una cadena de bits muy larga hasta que aparezca el bit que resuelve la ambigüedad.
      Por ejemplo, en un caso como 100000000000000001, para saber si el primer código es a o c, hay que leer todos los ceros hasta el punto en que terminan.

  • Me pregunto si, entre los tutoriales similares que van construyendo un programa en Haskell como este artículo, hay materiales que traten funciones más avanzadas como transformadores de mónadas o lentes.

    • Recomiendo el libro Haskell in Depth. Los transformadores de mónadas se tratan en el capítulo 6, y las lentes en los capítulos 3 y 14.
      También cubre otras funciones avanzadas como Template Haskell y concurrencia, y tiene un capítulo sobre cómo manejar bases de datos SQL en Haskell.
    • Vale la pena ver https://github.com/turion/rhine-koans.
      Es un tutorial de la biblioteca FRP Rhine, y tiene buenos comentarios y pruebas.

  • El curso de programación funcional basado en Scala de Coursera también tiene una tarea de codificación Huffman bastante similar, y cuenta con un calificador automático, así que es bueno para quien quiera resolverla por su cuenta
    https://www.coursera.org/learn/scala-functional-programming?...

  • La última vez que usé códigos Huffman fue para el macroprograma del procesador MICMAC, es decir, para ejecutar texto ensamblador con el mínimo de microciclos y microinstrucciones
    Empecé con un histograma de las macroinstrucciones ejecutadas y, si mal no recuerdo, primero escribí un intérprete en C para contar cuántas veces se ejecutaba cada instrucción
    Luego creé un programa de microcódigo de decodificación incremental que implementaba todas las macrooperaciones ISA necesarias. Creo que la ISA de macroinstrucciones que hice no estaba orientada a bytes, sino a nivel de bits
    En la práctica habría sido lento e incómodo, pero la ventaja de los códigos Huffman es que permiten ajustar la profundidad de los prefijos según la distribución de valores, de modo que no hace falta crear un código sesgado hacia un lado por culpa de un prefijo de 1 bit
    Además, el microprograma era un modelo de procesador canalizado no superescalar, así que también tenía que manejar predicción de saltos. Si se predecía mal un salto, se desperdiciaban ciclos con la canalización detenida mientras el salto correcto se propagaba hacia adelante

  • https://rosettacode.org/wiki/Huffman_coding

  • Como parece que se van a reunir programadores de Haskell, quiero preguntar: hoy en día, ¿qué tan rápido es Haskell si lo usa un programador que se preocupa por la optimización?
    En particular, me interesa el rendimiento en tareas que se benefician de SIMD y de cálculo numérico, como las operaciones con matrices

    • La velocidad de Haskell puede competir con la de los lenguajes de sistemas, pero hay que tener presente que su ventaja principal es la facilidad de abstracción
      Lo central es que resulta fácil ensamblar varias partes en un programa coherente y bien organizado. Eso importa para todo el programa, no solo para bucles ajustados
      Haskell tiene buen FFI, así que las partes que por naturaleza necesitan optimización imperativa pueden bajarse a un lenguaje sin recolección de basura. Si envuelves esas partes en una biblioteca con buenos tipos, puedes aprovechar ese rendimiento nativo desde cualquier código Haskell donde los tipos encajen
      En Meta hicimos eso al crear aplicaciones Haskell de alto rendimiento. Escribíamos programas Haskell bonitos, grandes y rápidos, pero metíamos componentes en C++ para algunas partes especializadas. El 99% del tiempo lo pasábamos componiendo del lado de Haskell una aplicación más útil
    • Para tareas cotidianas de backend, web y CLI, el rendimiento de Haskell me gusta. Pero cuando escribo código centrado en rendimiento, bajo a Rust
      Aun así, Haskell no es precisamente lento. Un ejemplo es un programita que cuenta la cantidad de bits en 1 en un archivo
      Si se compila con -msse4.2, usa correctamente la instrucción de hardware popcount y procesa un archivo de entrada de 1 GB en 0m0,090s. Redondeando a MB, usa 0 de heap
      Si se compila sin -msse4.2, tarda 0m0,293s
      No he probado cálculos matriciales directamente, pero como punto de partida revisaría repa, accelerate y massiv
      https://hackage.haskell.org/package/repa
      https://hackage.haskell.org/package/accelerate
      https://hackage.haskell.org/package/massiv
    • En ZuriHac conocí a Sam Derbyshire y me dijo que todo el trabajo de arquitectura difícil para el soporte SIMD ya está terminado
      https://gitlab.haskell.org/ghc/ghc/-/issues/7741
      Podría entrar en GHC 9.12. Eso sí, apunta solo a vectores de 128 bits y, salvo que otras personas contribuyan, parece que se centrará principalmente en operaciones de punto flotante
      El parche está aquí
      https://gitlab.haskell.org/ghc/ghc/-/merge_requests/12860
    • Siendo realistas, en cualquier lenguaje, incluido C, el código optimizado por el compilador no puede ser tan rápido como el código optimizado a mano de bibliotecas como BLAS
      A cierto nivel, la elección del lenguaje anfitrión no importa mucho. Si realmente te tomas en serio la velocidad, de todos modos terminarás delegando el cálculo afuera
      Es la misma razón por la que el código de IA, que probablemente está entre los mayores consumidores de recursos de cómputo del mundo, puede estar escrito en Python salvo por las bibliotecas de cálculo de bajo nivel
      Respondiendo directamente: el compilador GHC es muy bueno. El código de alto nivel funciona bastante bien y, en la mayoría de las aplicaciones reales, el cuello de botella de rendimiento no es un problema de operaciones de ancho simple contra SIMD, sino de arquitectura. La “asintoticidad arquitectónica” de Haskell es bastante favorable
      Creo que GHC ya tiene o está incorporando soporte SIMD, pero no me enfocaría en eso al evaluar el rendimiento
      No escribiría yo mismo un algoritmo de multiplicación de matrices en Haskell, pero si me tomara en serio la velocidad, tampoco lo escribiría yo mismo en Rust o C
      A menudo se ve el cálculo numérico como métrica de rendimiento, pero en la práctica casi nadie tiene ahí su cuello de botella y, si lo tiene, el lenguaje de alto nivel que use importa poco
    • Haskell realmente brilla cuando quieres escribir código declarativo de alto nivel
      El rendimiento de este estilo suele ser suficiente para trabajos de CLI o backends web. También hay herramientas para escribir código de bajo nivel bastante rápido, pero son algo toscas, así que si eso es lo único que quieres hacer probablemente no sea la mejor herramienta
      Dicho eso, cuando hay algunos hotspots concentrados que optimizar, funciona bastante bien
      Las herramientas de profiling de CPU son buenas, así que encontrar y optimizar hotspots de CPU es relativamente cómodo. En cambio, rastrear fugas de memoria raras, que pueden aparecer con más facilidad por la evaluación diferida, puede ser muy frustrante
      Si miras los resultados de benchmarks game, las implementaciones más rápidas en Haskell suelen ser entre 2 y 5 veces más lentas que las versiones más rápidas en C, y están escritas en un estilo muy imperativo
      https://benchmarksgame-team.pages.debian.net/benchmarksgame/...

  • Parece que hay un typo en la tabla de la sección “Creating prefix-free codes”. D debería ser 0010, no 0110

    • Por eso me rompí la cabeza un buen rato tratando de entender cómo 0110 podía no ser ambiguo, pero ahora ya lo entiendo

  • Me da curiosidad qué es lo que aparece en la camiseta de la mujer de la imagen
    Enlace directo: https://lazamar.github.io/images/data-compressor.svg