LZ4 (algoritmo de compresión)

LZ4 es un algoritmo de compresión de datos sin pérdidas , optimizado para una compresión y descompresión rápidas. Pertenece a la familia LZ77 de esquemas de compresión orientados a bytes.

El algoritmo LZ4 ofrece un buen equilibrio entre velocidad y relación de compresión. Por lo general, tiene una relación de compresión menor (es decir, peor) que el algoritmo LZO , que a su vez es peor que algoritmos como DEFLATE . Sin embargo, la velocidad de compresión de LZ4 es similar a la de LZO y varias veces más rápida que la de DEFLATE, mientras que la velocidad de descompresión es significativamente más rápida que la de LZO. ^{[ 3 ]}

LZ4 solo utiliza una etapa de coincidencia de diccionario (LZ77) y, a diferencia de otros algoritmos de compresión comunes, no la combina con una etapa de codificación de entropía (por ejemplo, codificación Huffman en DEFLATE). ^{[ 4 ] [ 5 ]}

El algoritmo LZ4 representa los datos como una serie de secuencias. Cada secuencia comienza con un token de un byte que se divide en dos campos de 4 bits. El primer campo representa el número de bytes literales que se copiarán a la salida. El segundo campo representa el número de bytes que se copiarán del búfer de salida ya decodificado (donde 0 representa la longitud mínima de coincidencia de 4 bytes). Un valor de 15 en cualquiera de los campos de bits indica que la longitud es mayor y que hay un byte de datos adicional que se agregará a la longitud. Un valor de 255 en estos bytes adicionales indica que se agregará otro byte más. Por lo tanto, las longitudes arbitrarias se representan mediante una serie de bytes adicionales que contienen el valor 255. La cadena de literales viene después del token y cualquier byte adicional necesario para indicar la longitud de la cadena. A esto le sigue un desplazamiento que indica hasta qué punto del búfer de salida se debe comenzar a copiar. Los bytes adicionales (si los hay) de la longitud de coincidencia vienen al final de la secuencia. ^{[ 6 ] [ 7 ]}

La compresión puede realizarse de forma continua o por bloques. Se pueden lograr índices de compresión más altos dedicando mayor esfuerzo a encontrar las mejores coincidencias. Esto se traduce en un menor volumen de salida y una descompresión más rápida.

LZ4 tiene dos formatos de trama. El formato anterior era muy restrictivo y dependía de una señal externa de fin de archivo, lo que resultó ser un problema en el initramfs de Linux y requirió una solución alternativa para manejar el relleno con ceros. ^{[ 8 ]} El nuevo formato es mucho más flexible y tiene su propio marcador de fin de trama. Su diseño se asemeja al del formato de trama Zstd . ^{[ 9 ]}

La implementación de referencia en C de Yann Collet tiene licencia BSD. Existen puertos y enlaces en varios lenguajes, incluidos Java , C# , Rust y Python . ^{[ 10 ]} El sistema Apache Hadoop utiliza este algoritmo para una compresión rápida. LZ4 también se implementó de forma nativa en el kernel de Linux 3.11. ^{[ 11 ]} Las implementaciones de FreeBSD, Illumos, ZFS en Linux y ZFS-OSX del sistema de archivos ZFS admiten el algoritmo LZ4 para la compresión sobre la marcha. ^{[ 12 ] [ 13 ] [ 14 ] [ 15 ]} Linux admite LZ4 para SquashFS desde la versión 3.19-rc1. ^{[ 16 ]} LZ4 también es compatible con la nueva utilidad de línea de comandos zstd de Yann Collet, así como con una bifurcación de 7-Zip llamada 7-Zip-zstd. ^{[ 17 ]}

• Sitio web oficial