rzip es un programa informático de compresión de datos a gran escala diseñado en torno a la coincidencia inicial de cadenas de estilo LZ77 en una ventana de diccionario de 900 MB, seguida de la transformada Burrows-Wheeler basada en bzip2 y la codificación de entropía ( Huffman ) en fragmentos de salida de 900 kB.
Autor (es) original (es) | Andrew Tridgell |
---|---|
Lanzamiento estable | 2.1 / 14 de febrero de 2006 |
Escrito en | C |
Sistema operativo | Tipo Unix |
Tamaño | 46K (código fuente tarball, comprimido en gzip) |
Sitio web | rzip |
Algoritmo de compresión
rzip opera en dos etapas. La primera etapa encuentra y codifica grandes porciones de datos duplicados en distancias potencialmente muy largas (900 MB) en el archivo de entrada. La segunda etapa utiliza un algoritmo de compresión estándar ( bzip2 ) para comprimir la salida de la primera etapa.
Es bastante común en estos días tener que comprimir archivos que contienen redundancias de larga distancia. Por ejemplo, al comprimir un conjunto de directorios de inicio, varios usuarios pueden tener copias del mismo archivo o de archivos bastante similares. También es común tener un solo archivo que contiene grandes fragmentos duplicados a grandes distancias, como archivos PDF que contienen copias repetidas de la misma imagen. La mayoría de los programas de compresión no podrán aprovechar esta redundancia y, por lo tanto, podrían lograr una relación de compresión mucho menor que la que puede lograr rzip.
La interfaz intermedia entre las dos etapas está hecha de un flujo de datos alineado por bytes del cual hay dos comandos, un literal ("agregar") con longitud y datos:
tipo: 8 = 0 => literal / agregar rango de bytes de conteo recuento: 16 = 1..65535 datos: 8..∞ = datos literales a insertar (n bytes completos)
y una coincidencia ("copia") con parámetros de longitud y desplazamiento:
tipo: 8 = 1 => igualar / copiar rango de bytes de recuento recuento: 16 = 31..65535 desplazamiento: 32 = desplazamiento a la posición desde la que se va a copiar
Las longitudes de literal o coincidencia / copia de más de 65.535 bytes se dividen en varias instrucciones. El final del flujo se indica con un comando literal / agregar (tipo = 0, recuento = 0) de longitud cero e inmediatamente seguido por una suma de comprobación CRC de 32 bits .
Implementación de referencia
Se utiliza un algoritmo de suma de comprobación continua basado en el de rsync para localizar posibles coincidencias en un conjunto de datos tan grande. A medida que los depósitos de hash se llenan, los hash anteriores ("etiquetas") se descartan basándose en dos veces. [ aclaración necesaria ] Las etiquetas se descartan de tal manera que proporcionen una cobertura bastante buena , con una granularidad de coincidencia que disminuye gradualmente a medida que aumenta la distancia. Esta implementación no busca longitudes de coincidencia de menos de 31 bytes consecutivos.
Ventajas
La diferencia clave entre rzip y otros algoritmos de compresión conocidos es su capacidad para aprovechar la redundancia de muy larga distancia. El conocido algoritmo de desinflado utilizado en gzip utiliza un búfer de historial máximo de 32 KiB. El algoritmo de clasificación de bloques de transformación de Burrows-Wheeler utilizado en bzip2 está limitado a 900 KiB de historia. El búfer de historial en rzip puede tener una longitud de hasta 900 MiB, varios órdenes de magnitud más grande que gzip o bzip2. Rzip suele ser mucho más rápido que bzip2, a pesar de utilizar la biblioteca bzip2 como back-end. Esto se debe a que rzip alimenta a bzip2 con datos reducidos, por lo que bzip2 tiene que hacer menos trabajo. Se han realizado comparaciones simples (aunque demasiado pequeñas para que sea un punto de referencia autorizado). [1] [2]
Desventajas
rzip no es adecuado para todos los propósitos. Las dos mayores desventajas de rzip son que no se puede canalizar (por lo que no puede leer desde la entrada estándar o escribir en la salida estándar) y que usa una gran cantidad de memoria: una ejecución de compresión típica en un archivo grande podría usar cientos de megabytes de RAM . Si hay mucha RAM de sobra y se requiere una relación de compresión muy alta, se debe usar rzip, pero si no se cumplen estas condiciones, se deben usar métodos de compresión alternativos como gzip y bzip2, que requieren menos memoria. en lugar de rzip. Hay al menos un parche para habilitar la canalización. [3]
Historia
rzip fue escrito originalmente por Andrew Tridgell como parte de su investigación de doctorado.
Implementaciones alternativas
lrzip
Autor (es) original (es) | Con Kolivas, Peter Hyman y Andrew Tridgell |
---|---|
Versión inicial | Enero de 2008 |
Lanzamiento estable | 0.631 / 20 de octubre de 2016 |
Escrito en | C, C ++ (libzpaq) |
Sistema operativo | Tipo Unix |
Tamaño | 246K (código fuente tarball, comprimido en gzip) |
Sitio web | github |
lrzip (ZIP de largo alcance) es una versión mejorada de rzip. Su formato de archivo es incompatible con rzip. Tiene las siguientes mejoras:
- Compresión LZMA , LZO , DEFLATE , Bzip2 y ZPAQ (a diferencia de Bzip2 solamente)
- Sin límite de diccionario, ni siquiera limitado por la RAM disponible
- Capacidad para probar la compresibilidad de los datos antes de comprimirlos, evitando que la computadora pierda tiempo al intentar comprimir datos incompresibles
- Capacidad de canalizarse desde entrada estándar / salida estándar (con una pérdida en la relación de compresión)
- Posibilidad de deshabilitar la compresión de última etapa para su uso con otro compresor
- Encriptación AES-128 opcional [4]
rzip64
rzip64 es una extensión de rzip para archivos muy grandes que pueden utilizar múltiples núcleos de CPU en paralelo. Hay resultados de referencia. [5] Sin embargo, lo más importante es la capacidad de rzip64 de interrumpirse en cualquier momento. Por lo tanto, una tarea de compresión en ejecución (que puede llevar fácilmente varias horas para archivos grandes) sobrevive incluso a un reinicio de mantenimiento del sistema sin perder el trabajo ya completado y puede reanudarse más tarde. El formato de archivo de rzip64 es idéntico al rzip original.
REPS
REP es una implementación alternativa del algoritmo rzip de Bulat Ziganshin utilizado en su archivador FreeArc como preprocesador para los algoritmos de compresión LZMA / Tornado. En FreeArc, REP encuentra coincidencias de gran distancia y luego LZMA comprime los datos restantes. Por ejemplo, en una computadora con 2 GB de RAM, REP busca coincidencias de al menos 512 bytes de longitud a distancias de hasta 1 GB, y luego LZMA encuentra las coincidencias restantes a distancias de hasta 128 MB. Entonces, trabajando juntos, brindan la mejor compresión posible con un presupuesto de RAM de 2 GB.
Al estar optimizado para la descompresión de transmisiones y el trabajo colaborativo con LZMA, REP tiene algunas diferencias con la implementación de RZIP original. Primero, de forma predeterminada, solo encuentra coincidencias que tienen más de 512 bytes de longitud, ya que la evaluación comparativa demostró que esta es la configuración óptima para la compresión general REP + LZMA. En segundo lugar, utiliza un diccionario deslizante que tiene aproximadamente 1/2 RAM de longitud, por lo que la descompresión no necesita volver a leer los datos del archivo descomprimido. La ventaja de REP es su hash rodante multiplicativo que es rápido de calcular y tiene una distribución casi ideal.
La longitud mínima de coincidencia más grande (512 bytes en comparación con 32 bytes en rzip) permitió optimizaciones de velocidad adicionales, de modo que REP proporciona una compresión muy rápida (aproximadamente 200 MB / s en Intel i3-2100).
SREP
SREP (SuperREP) es una implementación de la idea de Tridgell del compresor LZ que no almacena su diccionario en RAM, sino que usa hash SHA1 de bloques procesados para comparar su contenido. Permite que el programa comprima archivos que son aproximadamente 10 veces más grandes que la RAM disponible. La descompresión se realiza leyendo datos de la parte descomprimida del archivo o almacenando en la memoria futuras coincidencias (algoritmo de compresión Future-LZ). Por supuesto, la compresión Future-LZ requiere 2 pasadas sobre el archivo de entrada, pero la descompresión necesita una pequeña memoria. [ cita requerida ] En un experimento, el archivo de 22 GB comprimido con una longitud mínima de coincidencia de 512 bytes y el diccionario completo de 22 GB requirieron solo 2 GB de RAM para la descompresión. [ cita requerida ]
Ver también
Referencias
- ^ Elegir el código postal correcto
- ^ "rzip" .
- ^ "Nicolas Rachinsky: Enlaces" .
- ^ Kolivas, Kon. "lrzip README" . GitHub . Consultado el 27 de enero de 2017 .
- ^ "GHSi - Benchmarking rzip64" .
enlaces externos
- rzip
- lrzip : una mejora de rzip que permite que la reducción de bzip2 de la segunda etapa sea reemplazada por LZMA , LZO o ninguna segunda etapa (sin procesar, compresión solo de diccionario). El autor es Con Kolivas, quien afirma que 'lrzip' significa 'Long Range ZIP'.
- rzip64 : una mejora paralela de 'rzip' con el modo de parada y arranque de Kay Gorontzi.
- REP : implementación de RZIP mejorada optimizada para su uso junto con LZMA
- SREP : el primer compresor LZ que usa menos RAM que el tamaño del diccionario
- DataCompression.info - LZ77 / LZSS y derivados