Explicación detallada del algoritmo de compresión lz4

lz4 es actualmente el algoritmo de compresión más eficiente en general. Se centra más en la velocidad de compresión y descompresión, pero la relación de compresión no es la primera. En los sistemas operativos actuales de Android y Apple, la tecnología de compresión de memoria utiliza el algoritmo lz4 para comprimir la memoria del teléfono móvil a tiempo para generar más espacio de memoria. Básicamente, se intercambia tiempo por espacio.

El algoritmo de compresión lz4 es realmente muy simple. Tome un ejemplo de compresión.

Los dos corchetes representan los duplicados detectados durante la compresión, (5, 4) representa cinco bytes hacia adelante, la longitud de. el contenido coincidente es 4, es decir, "bcde" es una repetición. Por supuesto, también se puede decir que "cde" es un duplicado, pero de acuerdo con el orden de escaneo del flujo de entrada implementado por el algoritmo, obtenemos la primera coincidencia y la de mayor longitud como coincidencia.

Los datos comprimidos tienen el siguiente formato

También puede haber coincidencias continuas en otros casos:

Los literales se refieren al flujo de bytes que no se repite y aparece por primera vez, es decir, la parte incompresible

Match se refiere a elementos duplicados y la parte comprimible

Token registra la longitud literal y la longitud de la coincidencia. Como parámetro de memcpy durante la descompresión

Se puede imaginar que si hay más o más duplicados, la tasa de compresión será mayor. En el ejemplo anterior, "bcde" está representado por (5, 4) después de la compresión, es decir, se comprime de 4 bytes a 3 bytes. Entre ellos, el desplazamiento es de 2 bytes y la longitud de coincidencia es de 1 byte, lo que puede ahorrar 1 byte.

El proceso general es que el proceso de compresión utiliza al menos 4 bytes como ventana de escaneo para encontrar coincidencias, y escanea moviendo 1 byte cada vez. Si se encuentran duplicados, se comprimirán.

Dado que el desplazamiento se expresa en 2 bytes, sólo se pueden encontrar coincidencias a una distancia de 2^16 (64 kb). Para comprimir una página del núcleo de 4 Kb, sólo se necesitan 12 bits.

El tamaño del paso de escaneo de 1 byte se puede ajustar, lo que corresponde al mecanismo LZ4_compress_fast. Cambiar el tamaño del paso puede aumentar la velocidad de compresión y descompresión y reducir la tasa de compresión.

Echemos un vistazo a la implementación lz4 de Apple

Después de comprender la compresión, la descompresión es realmente muy simple

Según el flujo de datos antes de la descompresión, elimine la longitud en el token, los literales se copian directamente a la salida, es decir, memcpy(src, dst, length)

Cuando encuentre una coincidencia, simplemente copie los literales copiados de adelante hacia atrás