LZ0 - Compresor LZ asimétrico con decodificador de cero malloc

Show HN: LZ0 -An asymmetric LZ compressor with ultra minimal, 0-alloc decoder

LZ0 es un compresor de datos experimental que prioriza la simplicidad del decodificador. Mientras que la mayoría de los algoritmos equilibran el esfuerzo entre compresión y descompresión, LZ0 traslada toda la complejidad al codificador para que el decodificador sea ultra minimalista: sin asignación dinámica de memoria, con un estado mínimo y capaz de procesar cientos de megabytes por segundo. Está pensado para blobs binarios pequeños y medianos, y ofrece implementaciones en C, ensamblador x86-64, ARM64 y RISC-V, ideal para entornos con recursos limitados como bootloaders, microcontroladores o kernels. Su encoder combina hash chains, suffix arrays SA-IS y un parser DP disperso para lograr ratios comparables a ZX0 en segundos en lugar de minutos.

Mover la complejidad del decodificador al codificador: LZ0 gasta más esfuerzo al comprimir para que descomprimir sea ultra simple y sin malloc.
  1. nellacross

    Me encantaría ver una comparación más profunda con LZ4. Un decodificador estilo LZ4 puede hacerse mínimo, y se puede usar LZ4HC para lograr mejor densidad sin sacrificar velocidad de descompresión.

  2. aidenn0

    Sería bueno ver benchmarks contra lz4hc -9, ya que es el competidor más cercano en términos de velocidad tanto de compresión como de descompresión.

  3. seb3773

    Construí LZ0, un compresor LZ asimétrico orientado a entornos donde los recursos de descompresión están muy limitados (bootloaders, microcontroladores, carga de assets embebidos) o donde la simplicidad del decodificador es lo más importante.

    Siempre he admirado micro-decodificadores como ZX0 de Einar Saukas: cero asignación dinámica, sin RAM de scratch, y lo suficientemente pequeño como para caber en un puñado de instrucciones. El problema con los parsers óptimos tradicionales es que a menudo escalan en O(N^2), tomando decenas de segundos o minutos una vez que los archivos superan unos cientos de kilobytes. Escribí LZ0 para mantener esa misma huella de decodificador mientras comprime archivos de varios megabytes en milisegundos.

    Dónde se ubica (Ratio vs. Velocidad): - Densidad de compresión: supera a LZ4/Snappy, manteniéndose dentro del 1–3% de zlib/Deflate y ZX0 exhaustivo. - Velocidad de descompresión: 200–350 MB/s para C portable, 250–700 MB/s para ASM compacto, y 520–1,330 MB/s para ASM vectorial. Eso es hasta 10x más rápido que Deflate mientras requiere cero memoria heap o tablas de estado. - Rendimiento de compresión: ~1.3–1.6 s en entradas típicas de 1 MB.

    Cómо el codificador evita la pared O(N^2) (pipeline H2C8): - Búsqueda de coincidencias multinivel: cadenas de hash de doble nivel para coincidencias locales emparejadas con un arreglo de sufijos SA-IS O(N) para coincidencias profundas y de largo alcance. - Parsing DP disperso: en lugar de evaluar cada arista en el grafo, agrupa los costos de bits de Elias gamma en mesetas matemáticas para omitir búsquedas redundantes.

    El repositorio incluye tres implementaciones de decodificador con 0 asignaciones: 1. C portable (`lz0dec_min.c`): ~75 líneas de C freestanding con z […]

Más de este día

2026-11-21