rzip es un programa informático de compresión de datos a gran escala diseñado en torno a la coincidencia de cadenas inicial al estilo LZ77 en una ventana de diccionario de 900 MB, seguido por la transformación de Burrows-Wheeler basada en bzip2 y la codificación de entropía ( Huffman ) en fragmentos de salida de 900 kB.
rzip funciona en dos etapas. La primera etapa encuentra y codifica grandes fragmentos 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.
Hoy en día es bastante común tener que comprimir archivos que contienen redundancias de larga distancia. Por ejemplo, al comprimir un conjunto de directorios personales, 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 largas 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 tasa de compresión mucho menor que la que puede lograr rzip.
La interfaz intermedia entre las dos etapas está formada por un flujo de datos alineado por bytes del que hay dos comandos, un literal ("add") con longitud y datos:
tipo:8 = 0 => literal/agrega rango de conteo de bytes cuenta: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 => coincidir/copiar rango de conteo de bytes cuenta:16 = 31..65535 offset:32 = desplazamiento a la posición desde la que se copiará
Los literales o las longitudes de coincidencia/copia de más de 65 535 bytes se dividen en varias instrucciones. El final de la secuencia se indica con un comando literal/agregado de longitud cero (tipo=0,conteo=0) y seguido inmediatamente por una suma de comprobación CRC de 32 bits .
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 contenedores de hashes se llenan, los hashes anteriores ("etiquetas") se descartan en función de la duplicación. [ Aclaración necesaria ] Las etiquetas se descartan de 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.
La diferencia clave entre rzip y otros algoritmos de compresión conocidos es su capacidad para aprovechar la redundancia de distancias muy largas. El conocido algoritmo deflate utilizado en gzip utiliza un búfer de historial máximo de 32 KiB. El algoritmo de ordenación de bloques de la transformada de Burrows-Wheeler utilizado en bzip2 está limitado a 900 KiB de historial. El búfer de historial en rzip puede tener hasta 900 MiB de longitud, varios órdenes de magnitud más grande que gzip o bzip2. Rzip es a menudo 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, de modo que bzip2 tiene que hacer menos trabajo. Se han producido comparaciones simples (aunque demasiado pequeñas para que sea un punto de referencia autorizado). [1] [2]
Rzip no es adecuado para todos los propósitos. Las dos mayores desventajas de rzip son que no se puede segmentar (por lo que no puede leer desde la entrada estándar ni escribir en la salida estándar) y que utiliza una gran cantidad de memoria: una ejecución de compresión típica en un archivo grande puede utilizar cientos de megabytes de RAM . Si hay mucha RAM disponible y se requiere una relación de compresión muy alta, se debe utilizar rzip, pero si no se cumplen estas condiciones, se deben utilizar métodos de compresión alternativos como gzip y bzip2, que consumen menos memoria, en lugar de rzip. Hay al menos un parche para habilitar la segmentación. [3]
rzip fue escrito originalmente por Andrew Tridgell como parte de su investigación de doctorado.
lrzip (Long Range ZIP) es una versión mejorada de rzip. Su formato de archivo ( .lrz) es incompatible con el de rzip. Tiene las siguientes mejoras:
La distribución lrzip viene con un par de programas para usarlo con tar y .lrztarlrzuntar
rzip64 es una extensión de rzip para archivos muy grandes que puede utilizar varios núcleos de CPU en paralelo. Existen resultados de pruebas comparativas. [5] Sin embargo, lo más importante es la capacidad de rzip64 de interrumpirse en cualquier momento. De este modo, una tarea de compresión en ejecución (que puede tardar 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.
REP es una implementación alternativa del algoritmo rzip de Bulat Ziganshin que se utiliza en su archivador FreeArc como preprocesador para los algoritmos de compresión LZMA/Tornado. En FreeArc, REP encuentra coincidencias a gran distancia y luego LZMA comprime los datos restantes. Por ejemplo, en una computadora con 2 GB de RAM, REP encuentra coincidencias que tengan 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. Por lo tanto, al trabajar juntos, brindan la mejor compresión posible con un presupuesto de RAM de 2 GB.
REP, que está optimizado para la descompresión de flujos y el trabajo colaborativo con LZMA, tiene algunas diferencias con respecto a la implementación original de RZIP. En primer lugar, de forma predeterminada, solo encuentra coincidencias de más de 512 bytes, ya que las pruebas comparativas demostraron que esta es la configuración óptima para la compresión general de REP+LZMA. En segundo lugar, utiliza un diccionario deslizante que ocupa aproximadamente la mitad de la RAM, por lo que la descompresión no necesita volver a leer los datos del archivo descomprimido. La ventaja de REP es su hash rotativo multiplicativo que es rápido de calcular y tiene una distribución casi ideal.
Una longitud de coincidencia mínima mayor (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 (SuperREP) es una implementación de la idea de Tridgell de un compresor LZ que no almacena su diccionario en la RAM, sino que utiliza hashes SHA1 de los bloques procesados para comparar sus contenidos. Permite al programa comprimir 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 las coincidencias futuras (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 memoria pequeña. [ cita requerida ] En un experimento, un archivo de 22 GB comprimido con una longitud de coincidencia mínima de 512 bytes y un diccionario completo de 22 GB requirieron solo 2 GB de RAM para la descompresión. [ cita requerida ]