Después de ver el drama de HBO "Silicon Valley", siempre me han interesado los algoritmos de compresión. Richard Hendricks y su algoritmo de compresión middle out son, por supuesto, falsos, pero después de Google Hard, descubrí que existe ese tipo de genio de algoritmos de compresión en la vida real.
Yann Collet inventó el algoritmo de compresión LZ4 en 2011. Por supuesto, el algoritmo LZ4 no es tan impresionante como el middle out, pero es conocido por su velocidad de compresión invencible y su velocidad de descompresión más rápida cuando se puede garantizar cierta tasa de compresión.
No entraré en detalles aquí sobre la evaluación de su velocidad de compresión; si te interesa, puedes leer este artículo comparativo:El inicio de sesión del hipervínculo es visible.
También adjunto la dirección de github de LZ4:El inicio de sesión del hipervínculo es visible.
Este artículo se centra en explicar el principio del algoritmo de compresión LZ4. Un gran dios escribió una explicación del algoritmo LZ4 antes:El inicio de sesión del hipervínculo es visible.Pero cuando estudiaba antes, sentí que este artículo no era muy amigable para principiantes, así que empecé otro artículo para principiantes como yo.
Si lo resumes en una sola frase, LZ4 es un LZ77 que almacena un diccionario con una tabla hash de tamaño 16k y simplifica la recuperación.
LZ4 es un algoritmo de compresión sin pérdidas que ofrece una velocidad de compresión de > 500 MB/s por núcleo, que puede escalarse con CPUs multinúcleo. Dispone de decodificadores extremadamente rápidos con velocidades de varios GB/s por núcleo, que a menudo alcanzan los límites de velocidad de RAM en sistemas multinúcleo.
La velocidad puede ajustarse dinámicamente, seleccionando un factor de "aceleración" que cambia la relación de compresión por una velocidad más rápida. Por otro lado, también se proporciona una derivada de alta compresión LZ4_HC para aumentar la compresión a costa del tiempo de CPU. Todas las versiones tienen la misma velocidad de descompresión.
¿Entonces, qué es LZ77?
Compresión y principio de LZ77
LZ77 es un algoritmo que aplica un diccionario para la compresión. En términos sencillos, permite que el programa observe (mira el diccionario) si los datos que se ven actualmente están duplicados con los anteriores, y si es así, guardamos la distancia (desplazamiento) y la longitud de los campos duplicados para reemplazar los campos duplicados y comprimir los datos.
referenciaEl inicio de sesión del hipervínculo es visible.
Para una cadena de letras A A B C B B A B B C, cuando se lee la segunda A, el programa guarda (1,1) (1 dígito del anterior, longitud 1), y de forma similar, cuando se lee la segunda B, el programa guarda (2,1) (distancia 2, longitud 1).
Pero si la cadena es más larga y el programa registra los datos en el diccionario todo el tiempo, la búsqueda de campos duplicados se vuelve extremadamente lenta, porque en el peor de los casos el programa recorre todo el diccionario con cada nueva letra leída. LZ77 utiliza un método de ventana deslizante para resolver este problema.
De forma similar al punto de partida de TCP usando una ventana deslizante, una ventana deslizante puede reducir el área de caché para evitar procesar demasiados datos almacenados en caché al mismo tiempo. En LZ77, el diccionario no aumenta constantemente, sino que descarta los primeros caracteres añadidos cuando este supera el tamaño máximo especificado, para asegurar que el tamaño del diccionario siempre se mantenga en el tamaño máximo especificado.
Supongamos que la longitud del diccionario es 3
| Diccionario |
| A | A B C B B A B C
Producción (0,0,A)
| A A | B C B B A B C
Producción(1,1)
| A A B | C B B A B C
Producción (0,0,B)
A | A B C | B B A B C
Salida (0,0,C)
A A | B C B | B A B C
Producción(2,1)
La otra parte de la ventana deslizante es la caché a buscar (el búfer de anticipación no tiene traducción oficial). La caché a buscar es la parte sin comprimir de la longitud más cercana al diccionario. El algoritmo LZ77 coincidirá con la cadena más larga de esta parte del carácter que sea igual a la del diccionario. El ejemplo anterior puede considerarse como un buffer de anticipación de 1.
Supongamos que la longitud del diccionario es 5 y el tamaño de caché a buscar es 3
| Diccionario | Amortiguador de anticipación |
A | A B C B B | A B C |
Salida(5,3)
La cadena más larga que coincide es ABC
Proceso completo de compresión:
Supongamos que la longitud del diccionario es 5 y el tamaño de caché a buscar es 3
| Diccionario | Amortiguador de anticipación |
| A A B | C B B A B C
Producción (0,0,A)
| A | A B C | B B A B C
Producción(1,1)
| A A | B C B | B A B C
Producción (0,0,B)
| A A B | C B B | A B C
Salida (0,0,C)
| A A B C | B B A | B C
Producción(2,1)
| A A B C B | B A B | C
Producción(1,1)
A | A B C B B | A B C |
Salida(5,3)
A A B C | B B A B C | 。。。 |
No es necesario guardar el diccionario en el archivo de salida del compresor, porque el programa de descompresión restaura el diccionario al emparejar las unidades de salida.
Proceso de descompresión
Una de las grandes ventajas del algoritmo LZ77 es que es muy rápido para descomprimir.
Si la primera unidad emparejada es (0,0,A), entonces A es la salida.
La segunda unidad coincidente es (1,1), que copia el bit anterior de la cadena de salida y produce A si la longitud de copia es 1.
。。。
Si la última unidad coincidente es (5,3), entonces revisa 5 bits en la cadena de salida de copia, y si la longitud de copia es 3, entonces se obtienen A, B, C.
La parte más lenta de la compresión del algoritmo LZ77 es encontrar el carácter coincidente más largo en la caché para buscar en el diccionario. Si el diccionario y la caché a buscar son demasiado cortos, las probabilidades de encontrar una coincidencia son escasas. Por lo tanto, LZ4 ha cambiado el algoritmo de emparejamiento para LZ77.
Primero, el diccionario del algoritmo LZ4 es una tabla hash. La clave en el diccionario es una cadena de 4 bytes, cada clave corresponde a una sola ranura, y el valor en la ranura es la posición de esa cadena.
En lugar de buscar en la caché, LZ4 lee cuatro bytes a la vez desde el archivo de entrada y luego busca la ranura correspondiente a la cadena en la tabla hash, que en adelante se denominará cadena actual.
Si has llegado a los últimos 12 caracteres, ponlos directamente en el archivo de salida.
Si no hay valor asignado en la ranura, significa que los cuatro bytes aparecen por primera vez, se suman esos cuatro bytes y posiciones a la tabla hash, y continúan buscando.
Si hay una asignación en la ranura, significa que hemos encontrado un valor coincidente.
Si el valor en la ranura más el tamaño de la ventana deslizante < la posición del carácter actual, entonces la posición de coincidencia supera el tamaño del bloque, y el programa actualiza el valor en la ranura hash a la posición de la cadena actual.
LZ4 comprobará si ha habido un conflicto de hash. Si los 4 bytes en la ranura no son iguales a la cadena actual, debe haber un conflicto de hash. El propio xxhash del autor también es conocido por su eficacia, pero los conflictos son inevitables. En caso de conflicto, el programa también actualiza el valor en la ranura hash a la posición actual de la cadena
Finalmente, podemos confirmar que la coincidencia es válida, y el programa seguirá comprobando si los caracteres siguientes en la cadena coincidente son los mismos. Finalmente, copia todos los caracteres desde el final de la coincidencia válida anterior al inicio de esta coincidencia válida en el archivo comprimido, y añade la secuencia de coincidencia de esta coincidencia válida.
Collet llama a las unidades coincidentes que se generan por secuencias LZ4, y estas conforman el archivo comprimido LZ4. Los detalles son los siguientes:
El token tiene una longitud de 1 byte, siendo las primeras 4 palabras la longitud literal y las últimas 4 palabras la longitud de coincidencia. Como se mencionó antes, todos los caracteres desde el final de la coincidencia válida anterior hasta el inicio de esta coincidencia válida se copiarán a un archivo comprimido; estos archivos sin comprimir son literales y su longitud es la longitud literal.
Literalmente seguido de desviación. Como en LZ77, desviación y longitud de coincidencia se refieren a la longitud de la cadena actual respecto a su coincidencia, y la longitud de coincidencia se refiere a la longitud de la longitud de coincidencia de la cadena actual con la misma cadena en el diccionario. En la descompresión, hay que recorrerlo para encontrar la cadena a copiar y la longitud a copiar. La magnitud de la desviación es fija.
En la figura, literal length+ y coincidencia longitud+ son que, si las palabras literales o coincidentes de 4 palabras en la ficha no son suficientes, seguirán aumentando en las posiciones correspondientes. 4 palabras pueden representar de 0 a 15, y si hay más, se añade un byte, es decir, se suman 255 al tamaño hasta que el byte sea menor de 255. En la longitud correspondiente, 0 representa 4 bytes.
Los últimos 12 bytes terminan literalmente porque se copiaron directamente.
Veamos el código (Python es más abstracto)
Resumen Dicho todo esto, todavía no he resumido por qué el LZ4 es tan rápido. Primero comparemos la búsqueda en el diccionario entre LZ77 y LZ4. El LZ77 nativo busca diccionarios buscando la mayor coincidencia en la caché a buscar y en el diccionario. Este es un problema de encontrar la mayor cadena idéntica en dos cadenas. Si no usamos programación dinámica, en el peor de los casos tenemos que considerar todas las subcadenas de una cadena y luego emparejarlas en otra cadena. Si ×usamos programación dinámica, usaremos una tabla para mantener la coincidencia más larga en la dinámica, lo que solo nos permitirá completar la coincidencia en el caso de O(m*n). Y eso solo para un par de cachés de búsqueda y diccionarios. En el peor de los casos, si no hay coincidencias, entonces LZ77 tendrá que contar (la longitud de todo el archivo - la longitud de la caché a buscar) como muchos de estos problemas de coincidencia. LZ4 en realidad utiliza un nivel mayor de programación dinámica: almacena 4 bytes y sus posiciones en una tabla hash, y luego empareja 4 bytes nuevos de datos cada vez solo para comprobar si los valores en la tabla hash son válidos. Después de encontrar un valor de coincidencia válido, si miras los datos de seguimiento de los dos conjuntos de valores de coincidencia, también puedes encontrar su coincidencia más larga. Como cada clave de la tabla hash de LZ4 corresponde solo a 1 ranura, el trabajo de encontrar, añadir y modificar la tabla hash solo requiere O(1). Si se encuentran más coincidencias tras la emparejamiento, se necesitan más comparaciones de grupos, pero en el tiempo total, estas comparaciones reemplazarán el tiempo adicional para consultar la tabla hash, por lo que el tiempo total del algoritmo LZ4 es solo O(n). ¡Tengo que admirar la belleza del algoritmo de Collet! Para hacer el algoritmo aún más rápido, Collet establece el tamaño predeterminado de la tabla hash en 16k, que se recomienda no superar los 32k, para poder integrarse en la caché L1 de casi todas las CPUs (Intel). Todo el mundo sabe que la velocidad y la relación de memoria de la caché L1 de la CPU son muy diferentes, así que no es sorprendente que LZ4 esté volando rápido, sin mencionar que la ecuación hash usada en la tabla hash de LZ4 sigue siendo la xxhash más rápida. Por supuesto, un diseño así tiene sus inconvenientes. Cuanto más pequeña es la tabla hash, menos claves tiene. Esto significa que ocurrirán más conflictos de hash, lo cual es inevitable. Y más colisiones de hash significan menos coincidencias. Y una tabla hash más pequeña también significa una ventana deslizante más pequeña, lo que significa que se descartarán más coincidencias porque están demasiado lejos. Menos coincidencias representan una relación de compresión menor, por lo que el LZ4 tiene una relación de compresión menos prominente. Looking Ahead LZ4 ofrece una amplia gama de escenarios de aplicación. Del mismo modo que se usó la salida central en VR en Silicon Valley, LZ4 puede aumentar la utilización del ancho de banda al traer menos E/S a costa de una latencia muy baja debido a su velocidad de compresión muy rápida. También hay una pequeña conjetura: si hay una CPU con una caché mayor en nivel 1, ¿puede el LZ4 aumentar la relación de compresión sin comprometer la velocidad?
Texto original en:El inicio de sesión del hipervínculo es visible. |
Publicado en 3/1/2022 13:54:23
|
|
|
|
