lossless-compression - perdida - ejemplos de compresion de imagenes

Diferencia: LZ77 vs. LZ4 vs. LZ4HC(algoritmos de compresión)?

Question

Entiendo los algoritmos LZ77 y LZ78. Leí sobre LZ4 here y here y encontré un código para ello .

Esos enlaces describen el formato de bloque LZ4. Pero sería genial si alguien pudiera explicar (o dirigirme a una explicación de recursos):

• ¿En qué se diferencia LZ4 de LZ77?
• ¿En qué se diferencia LZ4HC de LZ4?
• ¿Qué idea hace que el algoritmo LZ4HC sea tan rápido?

Answer 1

LZ4 está diseñado para comprimir rápidamente, a cientos de MB / s por núcleo. Es un ajuste para aplicaciones en las que desea una compresión que es muy barata: por ejemplo, está tratando de hacer que la red o el formato en disco sea más compacto, pero no puede permitirse gastar una gran cantidad de tiempo de CPU en compresión. Es en una familia con, por ejemplo, snappy y LZO .

El punto de comparación natural es el algoritmo DEFLATE de zlib, que utiliza la codificación LZ77 y Huffman y se usa en gzip, los formatos .ZIP y .PNG, y muchos otros lugares para contar.

Estos compresores rápidos difieren porque:

1. Utilizan el código de detección de repetición que es más rápido (a menudo una hashtable simple sin detección de colisiones), pero no busca la mejor opción (lo que llevaría tiempo pero resultaría en una compresión más alta) y no puede encontrar algunas cortas partidos.
2. Solo intentan comprimir las repeticiones en la entrada, no intentan aprovechar algunos bytes que son más comunes que otros.
3. Relacionadas estrechamente con 2, generan bytes de salida a la vez, no bits; permitir códigos de fracción de un byte permitiría a veces más compresión, pero requeriría más operaciones de la CPU (potencialmente desplazamiento de bits y enmascaramiento y bifurcación) para codificar y descodificar.
4. Se han realizado muchos trabajos prácticos para hacer que sus implementaciones sean rápidas en las CPU modernas.

En comparación, DEFLATE obtiene una mejor compresión, pero comprime y descomprime más lentamente, y los algoritmos de alta compresión como LZMA , bzip2 , LZHAM o brotli tienden a llevar incluso más tiempo (aunque Brotli en su configuración más rápida puede competir con zlib ). Existe una gran variación entre los algoritmos de alta compresión, pero en general, tienden a capturar redundancias en distancias más largas, aprovechan más el contexto para determinar qué bytes son probables y usan formas más compactas pero más lentas para expresar sus resultados en bits.

LZ4HC es una variante de "alta compresión" de LZ4 que, creo, cambia el punto 1 anterior: el compresor encuentra más de una coincidencia entre los datos actuales y pasados ​​y busca la mejor coincidencia para garantizar que la salida sea pequeña. Esto mejora la relación de compresión pero reduce la velocidad de compresión en comparación con LZ4. Sin embargo, la velocidad de descompresión no está dañada, por lo que si comprime una vez y se descomprime muchas veces y en su mayoría desea descompresión extremadamente barata, LZ4HC tendría sentido.

Tenga en cuenta que incluso un compresor rápido puede no permitir que un núcleo sature una gran cantidad de ancho de banda, como el que proporcionan los SSD o los enlaces rápidos en centros de datos. Hay compresores aún más rápidos con relaciones más bajas, que a veces se usan para empaquetar datos temporalmente en la RAM . WKdm y Density son dos de estos compresores; un rasgo que comparten es actuar en palabras de entrada de máquina de 4 bytes a la vez en lugar de bytes individuales. A veces, el hardware especializado puede lograr una compresión muy rápida, como en los chips Exynos de Samsung o la tecnología QuickAssist de Intel .

Si está interesado en comprimir más de LZ4 pero con menos tiempo de CPU que desinflado, el autor de LZ4 (Yann Collet) escribió una biblioteca llamada Zstd ; en su lanzamiento estable, Facebook publicó sobre cómo lo usan . Utiliza máquinas de estados finitos , no códigos de Huffman, para la codificación de entropía; No soy un experto en esto, pero al menos el algoritmo se describe en detalle en una RFC . Los modos más rápidos de zstd ahora se acercan a LZ4 en relación y velocidad. Apple escribió lzfse sobre principios similares. Hace unos años, Google publicó una biblioteca llamada gipfeli , a pesar de que no parecía tener mucha tracción. También hay proyectos que apuntan a una compresión más rápida en el formato Zlib, como SLZ y parches a zlib de CloudFlare e Intel .

En comparación con los compresores más rápidos, esos empaquetadores "medios" agregan una forma de codificación de entropía , es decir, aprovechan la forma en que algunos bytes son más comunes que otros y (en efecto) ponen menos bits en la salida para el byte más común valores.

Si su principal preocupación es la latencia en lugar del tiempo total de CPU y está comprimiendo un flujo largo, hay herramientas para hacer la compresión en paralelo, como pigz y la opción de subprocesamiento -T a la herramienta de línea de comandos zstd. (Hay various packers experimentales también, pero existen más para ampliar los límites de velocidad o densidad, en lugar de usarlos hoy en día).

Entonces, en general, tiene un espectro bastante bueno de compresores alternativos para diferentes aplicaciones: LZ4 (o incluso compresores de memoria más débiles) para la compresión en tiempo real, DEFLATE como el antiguo estándar para la compresión equilibrada y Zstd como una alternativa más reciente desarrollada activamente, y brotli y Otros para alta compresión. A medida que pasa de LZ4 a DEFLATE a brotli, se hace más esfuerzo para predecir y codificar datos y obtener más compresión a costa de cierta velocidad.

Además, los algoritmos como brotli y zstd generalmente pueden superar a gzip: comprimir mejor a una velocidad determinada o obtener la misma compresión más rápido, pero esto no es en realidad porque zlib hizo algo incorrecto . Más bien, zlib se lanzó en 1995 y tomó buenas decisiones para el hardware de la época: por ejemplo, su ventana de historial de 32KB tenía sentido cuando la RAM cost más de 3.000 veces lo que hace hoy. Las CPU de hoy también dividen el saldo de las operaciones que son baratas / costosas, por ejemplo, las ramas difíciles de predecir son un problema mayor hoy en día y hacer mucha aritmética es relativamente más barato.