bzip2 es un programa de compresión de archivos gratuito y de código abierto que utiliza el algoritmo Burrows-Wheeler . Solo comprime archivos individuales y no es un archivador de archivos . Depende de utilidades externas independientes para tareas como el manejo de varios archivos, el cifrado y la división de archivos.
bzip2 fue lanzado inicialmente en 1996 por Julian Seward . Comprime la mayoría de los archivos de manera más efectiva que los algoritmos de compresión LZW y Deflate más antiguos , pero es más lento. bzip2 es particularmente eficiente para datos de texto y la descompresión es relativamente rápida. El algoritmo utiliza varias capas de técnicas de compresión, como la codificación por longitud de ejecución (RLE), la transformada de Burrows-Wheeler (BWT), la transformada de movimiento al frente (MTF) y la codificación de Huffman . bzip2 comprime datos en bloques entre 100 y 900 kB y utiliza la transformada de Burrows-Wheeler para convertir secuencias de caracteres que se repiten con frecuencia en cadenas de letras idénticas. Luego se aplican la transformada de movimiento al frente y la codificación de Huffman. El rendimiento de la compresión es asimétrico, y la descompresión es más rápida que la compresión.
El algoritmo ha pasado por varios mantenedores desde su lanzamiento inicial, siendo Micah Snyder el mantenedor desde junio de 2021. Ha habido algunas modificaciones en el algoritmo, como pbzip2, que utiliza subprocesos múltiples para mejorar la velocidad de compresión en computadoras con múltiples CPU y múltiples núcleos.
bzip2 es adecuado para su uso en aplicaciones de big data con marcos de computación en clúster como Hadoop y Apache Spark , ya que un bloque comprimido se puede descomprimir sin tener que procesar bloques anteriores.
Seward hizo el primer lanzamiento público de bzip2, la versión 0.15, en julio de 1996. La estabilidad y popularidad del compresor crecieron durante los siguientes años, y Seward lanzó la versión 1.0 a fines de 2000. [ no verificado en el cuerpo ] Después de una pausa de nueve años de actualizaciones para el proyecto desde 2010, el 4 de junio de 2019 Federico Mena aceptó el mantenimiento del proyecto bzip2. [4] Desde junio de 2021, el mantenedor es Micah Snyder. [5]
bzip2 utiliza varias capas de técnicas de compresión apiladas una sobre otra, que ocurren en el siguiente orden durante la compresión y en orden inverso durante la descompresión:
Cualquier secuencia de 4 a 255 símbolos duplicados consecutivos se reemplaza por los primeros 4 símbolos y una longitud de repetición entre 0 y 251. Por lo tanto, la secuencia AAAAAAABBBBCCCDse reemplaza por AAAA\3BBBB\0CCCD, donde \3y \0representan los valores de byte 3 y 0 respectivamente. Las series de símbolos siempre se transforman después de 4 símbolos consecutivos, incluso si la longitud de serie se establece en cero, para mantener la transformación reversible.
En el peor de los casos, puede provocar una expansión de 1,25 y, en el mejor de los casos, una reducción a <0,02. Si bien la especificación permite, en teoría, codificar tramos de longitud 256–259, el codificador de referencia no producirá ese resultado.
El autor de bzip2 ha declarado que el paso RLE fue un error histórico y que solo tenía como objetivo proteger la implementación original de BWT de casos patológicos. [6]
La transformada de Burrows-Wheeler es la ordenación por bloques reversible que se encuentra en el núcleo de bzip2. El bloque es completamente autónomo, con buffers de entrada y salida que permanecen del mismo tamaño; en bzip2, el límite operativo para esta etapa es de 900 kB. Para la ordenación por bloques, se crea una matriz (teórica), en la que la fila i contiene todo el buffer, rotado para comenzar desde el símbolo i -ésimo. Después de la rotación, las filas de la matriz se ordenan en orden alfabético (numérico). Se almacena un puntero de 24 bits que marca la posición de inicio para cuando el bloque no se transforma. En la práctica, no es necesario construir la matriz completa; en su lugar, la ordenación se realiza utilizando punteros para cada posición en el buffer. El buffer de salida es la última columna de la matriz; contiene todo el buffer, pero reordenado de modo que es probable que contenga grandes series de símbolos idénticos.
La transformación de mover al frente tampoco altera el tamaño del bloque procesado. Cada uno de los símbolos en uso en el documento se coloca en una matriz. Cuando se procesa un símbolo, se lo reemplaza por su ubicación (índice) en la matriz y ese símbolo se coloca al frente de la matriz. El efecto es que los símbolos que se repiten inmediatamente se reemplazan por símbolos cero (las series largas de cualquier símbolo arbitrario se convierten así en series de símbolos cero), mientras que otros símbolos se reasignan según su frecuencia local.
Muchos datos "naturales" contienen símbolos idénticos que se repiten dentro de un rango limitado (el texto es un buen ejemplo). Como la transformación MTF asigna valores bajos a los símbolos que reaparecen con frecuencia, esto da como resultado un flujo de datos que contiene muchos símbolos en el rango de números enteros bajos, muchos de ellos idénticos (diferentes símbolos de entrada recurrentes en realidad pueden asignarse al mismo símbolo de salida). Dichos datos se pueden codificar de manera muy eficiente mediante cualquier método de compresión heredado.
Las largas cadenas de ceros en la salida de la transformación de movimiento al frente (que provienen de símbolos repetidos en la salida de la BWT) se reemplazan por una secuencia de dos códigos especiales, RUNA y RUNB, que representan la longitud de la ejecución como un número binario. Los ceros reales nunca se codifican en la salida; un cero solitario se convierte en RUNA. (De hecho, este paso se realiza al mismo tiempo que MTF; siempre que MTF produzca cero, en su lugar aumenta un contador para luego codificar con RUNA y RUNB).
La secuencia 0, 0, 0, 0, 0, 1se representaría como RUNA, RUNB, 1; RUNA, RUNBrepresenta el valor 5 como se describe a continuación. El código de longitud de ejecución finaliza al llegar a otro símbolo normal. Este proceso RLE es más flexible que el paso RLE inicial, ya que puede codificar números enteros arbitrariamente largos (en la práctica, esto suele estar limitado por el tamaño del bloque, de modo que este paso no codifica una ejecución de más de900 000 bytes ). La longitud de ejecución se codifica de esta manera: se asignan valores de posición de 1 al primer bit, 2 al segundo, 4 al tercero, etc. en la secuencia, se multiplica cada valor de posición en un espacio RUNB por 2 y se suman todos los valores de posición resultantes (tanto para los valores RUNA como RUNB). Esto es similar a la numeración biyectiva de base 2. Por lo tanto, la secuencia RUNA, RUNBda como resultado el valor (1 + 2 × 2) = 5. Como un ejemplo más complicado:
CORRE, CORRE, CORRE, CORRE, CORRE (ABAAB) 1 2 4 8 16 1 4 4 8 32 = 49
Este proceso reemplaza los símbolos de longitud fija en el rango de 0 a 258 por códigos de longitud variable según la frecuencia de uso. Los códigos más utilizados terminan siendo más cortos (2 a 3 bits), mientras que los códigos poco comunes pueden tener una asignación de hasta 20 bits. Los códigos se seleccionan con cuidado para que ninguna secuencia de bits pueda confundirse con un código diferente.
El código de fin de flujo es particularmente interesante. Si se utilizan n bytes (símbolos) diferentes en los datos sin comprimir, entonces el código de Huffman constará de dos códigos RLE (RUNA y RUNB), n − 1 códigos de símbolo y un código de fin de flujo. Debido al resultado combinado de las codificaciones MTF y RLE en los dos pasos anteriores, nunca hay necesidad de hacer referencia explícita al primer símbolo en la tabla MTF (sería cero en el MTF ordinario), ahorrando así un símbolo para el marcador de fin de flujo (y explicando por qué solo se codifican n − 1 símbolos en el árbol de Huffman). En el caso extremo en el que solo se utiliza un símbolo en los datos sin comprimir, no habrá ningún código de símbolo en el árbol de Huffman, y el bloque completo constará de RUNA y RUNB (repitiendo implícitamente el byte único) y un marcador de fin de flujo con valor 2.
Se pueden utilizar varias tablas de Huffman de tamaño idéntico con un bloque si la ganancia de usarlas es mayor que el costo de incluir la tabla adicional. Pueden estar presentes al menos 2 y hasta 6 tablas, y la tabla más apropiada se vuelve a seleccionar antes de cada 50 símbolos procesados. Esto tiene la ventaja de tener una dinámica de Huffman muy sensible sin tener que suministrar continuamente nuevas tablas, como se requeriría en DEFLATE . La codificación por longitud de ejecución en el paso anterior está diseñada para ocuparse de los códigos que tienen una probabilidad inversa de uso mayor que el código de Huffman de código más corto en uso.
Si se utilizan varias tablas de Huffman, la selección de cada tabla (numeradas del 0 al 5) se realiza a partir de una lista mediante un bit terminado en cero que tiene una longitud de entre 1 y 6 bits. La selección se realiza en una lista MTF de las tablas. El uso de esta función da como resultado una expansión máxima de alrededor de 1,015, pero generalmente menor. Es probable que esta expansión se vea eclipsada en gran medida por la ventaja de seleccionar tablas de Huffman más apropiadas, y el caso común de continuar utilizando la misma tabla de Huffman se representa como un solo bit. En lugar de una codificación unaria, en realidad se trata de una forma extrema de un árbol de Huffman, donde cada código tiene la mitad de la probabilidad del código anterior.
Se requieren longitudes de bits del código Huffman para reconstruir cada una de las tablas Huffman canónicas utilizadas . Cada longitud de bit se almacena como una diferencia codificada con respecto a la longitud de bits del código anterior. Un bit cero (0) significa que la longitud de bits anterior debe duplicarse para el código actual, mientras que un bit uno (1) significa que se debe leer un bit adicional y la longitud de bits se debe incrementar o decrementar en función de ese valor. En el caso común, se utiliza un solo bit por símbolo por tabla y el peor de los casos (pasar de una longitud de 1 a una longitud de 20) requeriría aproximadamente 37 bits. Como resultado de la codificación MTF anterior, las longitudes de código comenzarían con 2-3 bits (códigos utilizados con mucha frecuencia) y aumentarían gradualmente, lo que significa que el formato delta es bastante eficiente y requiere alrededor de 300 bits (38 bytes) por tabla Huffman completa.
Se utiliza un mapa de bits para mostrar qué símbolos se utilizan dentro del bloque y deberían incluirse en los árboles de Huffman. Es probable que los datos binarios utilicen los 256 símbolos que se pueden representar mediante un byte, mientras que los datos textuales pueden utilizar solo un pequeño subconjunto de los valores disponibles, que quizás cubra el rango ASCII entre 32 y 126. El almacenamiento de 256 bits cero sería ineficiente si no se utilizaran en su mayor parte. Se utiliza un método disperso : los 256 símbolos se dividen en 16 rangos y solo si se utilizan símbolos dentro de ese bloque se incluye una matriz de 16 bits. La presencia de cada uno de estos 16 rangos se indica mediante una matriz de 16 bits adicional al frente. El mapa de bits total utiliza entre 32 y 272 bits de almacenamiento (4–34 bytes). En contraste, el algoritmo DEFLATE mostraría la ausencia de símbolos al codificar los símbolos como si tuvieran una longitud de bit cero con codificación de longitud de ejecución y codificación Huffman adicional.
No existe ninguna especificación formal para bzip2, aunque se ha realizado ingeniería inversa de una especificación informal a partir de la implementación de referencia. [7]
A modo de resumen, un .bz2flujo consta de un encabezado de 4 bytes, seguido de cero o más bloques comprimidos, seguidos inmediatamente por un marcador de fin de flujo que contiene un CRC de 32 bits para todo el flujo de texto sin formato procesado. Los bloques comprimidos están alineados por bits y no se produce ningún relleno.
.magic:16 = firma 'BZ'/número mágico.version:8 = 'h' para Bzip2 (codificación 'H'uffman'), '0' para Bzip1 (obsoleto).hundred_k_blocksize:8 = '1'..'9' tamaño de bloque 100 kB-900 kB (sin comprimir).compressed_magic:48 = 0x314159265359 (BCD (pi)).crc:32 = suma de comprobación para este bloque.randomised:1 = 0=>normal, 1=>aleatorio (obsoleto).origPtr:24 = puntero de inicio en BWT para después de destransformar.huffman_used_map:16 = mapa de bits, de rangos de 16 bytes, presente/no presente.huffman_used_bitmaps:0..256 = mapa de bits, de símbolos utilizados, presentes/no presentes (múltiplos de 16).huffman_groups:3 = 2..6 número de tablas Huffman diferentes en uso.selectors_used:15 = número de veces que se intercambian las tablas de Huffman (cada 50 símbolos)*.selector_list:1..6 = ejecuciones de bits terminadas en cero (0..62) de la tabla Huffman MTF (*selectors_used).start_huffman_length:5 = 0..20 longitud de bit inicial para deltas de Huffman*.delta_bit_length:1..40 = 0=>siguiente símbolo; 1=>modificar longitud { 1=>longitud de decremento; 0=>longitud de incremento } (*(símbolos+2)*grupos).contents:2..∞ = flujo de datos codificados por Huffman hasta el final del bloque (máximo 7372800 bits).eos_magic:48 = 0x177245385090 (raíz cuadrada BCD(pi)).crc:32 = suma de comprobación para toda la transmisión.padding:0..7 = alinear a todo el byteDebido a la compresión RLE de primera etapa (ver arriba), la longitud máxima de texto simple que puede contener un solo bloque bzip2 de 900 kB es de alrededor de 46 MB (45.899.236 bytes). Esto puede ocurrir si todo el texto simple consiste completamente en valores repetidos (el .bz2archivo resultante en este caso tiene una longitud de 46 bytes). Se puede lograr un archivo aún más pequeño de 40 bytes utilizando una entrada que contenga completamente valores de 251, una relación de compresión aparente de 1147480,9:1.
Un bloque comprimido en bzip2 se puede descomprimir sin tener que procesar bloques anteriores. Esto significa que los archivos bzip2 se pueden descomprimir en paralelo, lo que lo convierte en un buen formato para su uso en aplicaciones de big data con marcos de computación en clúster como Hadoop y Apache Spark . [8]
bzip2 comprime la mayoría de los archivos de manera más efectiva que los algoritmos de compresión más antiguos LZW ( .Z ) y Deflate ( .zip y .gz ), pero es considerablemente más lento. LZMA generalmente es más eficiente en términos de espacio que bzip2 a expensas de una velocidad de compresión aún más lenta, mientras que tiene una descompresión más rápida. [9]
bzip2 comprime datos en bloques de tamaño entre 100 y 900 kB y utiliza la transformada de Burrows-Wheeler para convertir secuencias de caracteres que se repiten con frecuencia en cadenas de letras idénticas. Luego aplica la transformada de movimiento al frente y la codificación de Huffman . El antecesor de bzip2, bzip, utilizaba codificación aritmética en lugar de Huffman. El cambio se realizó debido a una restricción de patente de software . [10] bzip3, [11] un compresor moderno que comparte ascendencia común y un conjunto de algoritmos con bzip2, volvió a la codificación aritmética.
El rendimiento de bzip2 es asimétrico, ya que la descompresión es relativamente rápida. Debido al largo tiempo requerido para la compresión, en 2003 se creó una versión modificada llamada pbzip2 que utilizaba subprocesos múltiples para codificar el archivo en múltiples fragmentos, lo que proporcionaba una aceleración casi lineal en computadoras con múltiples CPU y núcleos. [12] A mayo de 2010 [actualizar], esta funcionalidad no se había incorporado al proyecto principal.
Al igual que gzip , bzip2 es sólo un compresor de datos. No es un archivador como tar o ZIP; el formato de archivo bzip2 no permite almacenar el contenido de varios archivos en un único archivo comprimido, y el programa en sí no tiene funciones para múltiples archivos, cifrado o división de archivos. En la tradición UNIX , el archivado se puede realizar mediante un programa independiente que produce un archivo que luego se comprime con bzip2, y el descomprimido se puede realizar mediante bzip2 descomprimiendo el archivo comprimido y un programa independiente descomprimiéndolo. Algunos archivadores tienen soporte integrado para compresión y descompresión, de modo que no es necesario utilizar el programa bzip2 para comprimir o descomprimir el archivo. GnuPG también tiene soporte integrado para la compresión y descompresión bzip2.
La herramienta grepbasada en bzgreppermite buscar directamente en texto comprimido sin necesidad de descomprimir primero el contenido. [13]
.svg/1280px-Free_and_open-source_software_logo_(2009).svg.png){kind=logo}