bzip2

bzip2 es un formato de archivo y un programa de compresión de archivos . El programa utiliza el algoritmo Burrows-Wheeler para comprimir y descomprimir un único archivo utilizando el formato de archivo bzip2 . libbzip2 es una biblioteca de software de compresión de datos sin pérdida utilizada por el programa bzip2.

bzip2 no es un compresor de archivos y, por lo tanto, depende de utilidades externas separadas, como tarpara tareas como el manejo de múltiples archivos, y otras herramientas para el cifrado y la división de archivos comprimidos.

bzip2 fue lanzado inicialmente en 1996 (originalmente llamado bzip ^{[ 1 ] [ 5 ]} ) 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 codificación de longitud de ejecución (RLE), transformada de Burrows-Wheeler (BWT), transformada de movimiento al frente (MTF) y codificación Huffman . bzip2 comprime los 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 Huffman. El rendimiento de la compresión es asimétrico, siendo la descompresión más rápida que la compresión.

El algoritmo ha tenido varios responsables de mantenimiento desde su lanzamiento inicial, siendo Micah Snyder el responsable desde junio de 2021. Se han introducido algunas modificaciones en el algoritmo, como pbzip2 y lbzip2, que utilizan multihilo para mejorar la velocidad de compresión en ordenadores con múltiples CPU y 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 los bloques anteriores.

La utilidad bzip2recover incluida intenta recuperar las partes legibles de los datos bzip2 dañados. Funciona buscando bloques individuales y volcándolos en archivos separados. ^{[ 6 ]}

bzip2 utiliza varias capas de técnicas de compresión apiladas unas sobre otras, que se producen en el siguiente orden durante la compresión y en el orden inverso durante la descompresión:

1. Codificación de longitud de ejecución (RLE) de los datos iniciales.
2. Transformación de Burrows-Wheeler (BWT), o clasificación por bloques.
3. Transformación de movimiento al frente (MTF).
4. Codificación de longitud de ejecución (RLE) del resultado MTF.
5. Codificación Huffman .
6. Selección entre varias tablas de Huffman.
7. Codificación unaria en base 1 de la selección de la tabla de Huffman.
8. Codificación delta (Δ) de longitudes de bits del código Huffman.
9. Matriz de bits dispersos que muestra qué símbolos se utilizan.

Cualquier secuencia de entre 4 y 255 símbolos duplicados consecutivos se reemplaza por los primeros 4 símbolos y una longitud de repetición entre 0 y 251. De esta forma, la secuencia AAAAAAABBBBCCCDse reemplaza por AAAA\3BBBB\0CCCD, donde \3y \0representan los valores de byte 3 y 0, respectivamente. Las secuencias de símbolos siempre se transforman después de 4 símbolos consecutivos, incluso si la longitud de la secuencia se establece en cero, para que la transformación sea reversible.

En el peor de los casos, puede provocar una expansión de 1,25, y en el mejor, una reducción a <0,02. Si bien la especificación permite teóricamente codificar secuencias de longitud 256–259, el codificador de referencia no producirá tal 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. ^{[ 11 ]}

La transformada de Burrows-Wheeler es la ordenación por bloques reversible que constituye la base de bzip2. El bloque es completamente autónomo, con búferes de entrada y salida 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 búfer, rotado para comenzar desde el símbolo i . Tras la rotación, las filas de la matriz se ordenan alfabéticamente (o numéricamente). Se almacena un puntero de 24 bits que marca la posición inicial cuando el bloque no está transformado. 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 búfer. El búfer de salida es la última columna de la matriz; este contiene todo el búfer, pero reordenado de forma que es probable que contenga grandes secuencias de símbolos idénticos.

La transformación de desplazamiento al frente no altera el tamaño del bloque procesado. Cada uno de los símbolos utilizados en el documento se coloca en una matriz. Al procesar un símbolo, este se reemplaza por su posición (índice) en la matriz y se desplaza al principio de la misma. El efecto es que los símbolos que se repiten inmediatamente se reemplazan por ceros (las secuencias largas de cualquier símbolo se convierten así en secuencias de ceros), mientras que otros símbolos se reordenan según su frecuencia local.

Gran parte de los datos "naturales" contienen símbolos idénticos que se repiten dentro de un rango limitado (el texto es un buen ejemplo). Dado que la transformación MTF asigna valores bajos a los símbolos que se repiten con frecuencia, esto da como resultado un flujo de datos con muchos símbolos en el rango de enteros bajos, muchos de ellos idénticos (diferentes símbolos de entrada recurrentes pueden corresponder al mismo símbolo de salida). Dichos datos pueden codificarse de forma muy eficiente mediante cualquier método de compresión tradicional.

Las largas secuencias de ceros en la salida de la transformación de desplazamiento al frente (provenientes de símbolos repetidos en la salida de la transformada BWT) se reemplazan por una secuencia de dos códigos especiales, RUNA y RUNB, que representan la longitud de la secuencia como un número binario. Nunca se codifican ceros reales en la salida; un cero aislado se convierte en RUNA. (De hecho, este paso se realiza al mismo tiempo que la MTF; siempre que la MTF produciría un cero, en su lugar incrementa un contador para luego codificarlo 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 termina al alcanzar otro símbolo normal. Este proceso RLE es más flexible que el paso RLE inicial, ya que puede codificar 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 secuencia de más de900 000  bytes ). La longitud de ejecución se codifica de esta manera: se asignan valores posicionales de 1 al primer bit, 2 al segundo, 4 al tercero, etc., en la secuencia, se multiplica cada valor posicional en una posición RUNB por 2 y se suman todos los valores posicionales resultantes (tanto para los valores RUNA como para los RUNB). Esto es similar a la numeración biyectiva en base 2. Por lo tanto, la secuencia RUNA, RUNBda como resultado el valor (1 + 2 × 2) = 5. Como ejemplo más complejo:

RUNA RUNB RUNA RUNA RUNB (ABAAB) 1 2 4 8 16 1 4 4 8 32 = 49

Este proceso reemplaza los símbolos de longitud fija en el rango 0–258 con códigos de longitud variable según su frecuencia de uso. Los códigos más frecuentes resultan más cortos (2–3 bits), mientras que a los códigos menos frecuentes se les pueden asignar hasta 20 bits. Los códigos se seleccionan cuidadosamente para evitar confusiones entre secuencias de bits.

El código de fin de flujo es particularmente interesante. Si se utilizan n bytes (símbolos) diferentes en los datos sin comprimir, el código 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 es necesario hacer referencia explícita al primer símbolo en la tabla MTF (que sería cero en la MTF ordinaria), lo que ahorra un símbolo para el marcador de fin de flujo (y explica por qué solo se codifican n − 1 símbolos en el árbol Huffman). En el caso extremo en que solo se utiliza un símbolo en los datos sin comprimir, no habrá códigos de símbolo en el árbol Huffman, y todo el bloque constará de RUNA y RUNB (repitiendo implícitamente el mismo byte) y un marcador de fin de flujo con valor 2.

0: CORRE,

1: CORRER B,

2–257: valores de byte 0–255,

258: fin del flujo, finalizar el procesamiento (podría ser tan bajo como 2).

Se pueden usar varias tablas Huffman de tamaño idéntico con un bloque si la ventaja de usarlas supera el costo de incluir la tabla adicional. Se pueden usar entre 2 y 6 tablas, y la más apropiada se selecciona antes de procesar cada 50 símbolos. Esto ofrece la ventaja de una dinámica Huffman muy ágil sin necesidad de proporcionar continuamente nuevas tablas, como se requeriría en DEFLATE . La codificación de longitud variable en el paso anterior está diseñada para gestionar los códigos con una probabilidad inversa de uso mayor que la del código Huffman más corto en uso.

Si se utilizan varias tablas de Huffman, la selección de cada tabla (numerada del 0 al 5) se realiza a partir de una lista mediante una secuencia de bits terminada en cero de entre 1 y 6 bits de longitud. La selección se realiza en una lista MTF de las tablas. El uso de esta función resulta en una expansión máxima de alrededor de 1,015, pero generalmente menor. Es probable que esta expansión quede ampliamente eclipsada 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 la práctica 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 de 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 bit del código anterior. Un bit cero (0) significa que la longitud de bit 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 bit se incrementa o decrementa según ese valor. En el caso común, se utiliza un solo bit por símbolo por tabla y el peor caso —pasar de longitud 1 a longitud 20— requeriría aproximadamente 37 bits. Como resultado de la codificación MTF anterior, las longitudes de código comenzarían en 2-3 bits (códigos de uso muy frecuente) y aumentarían gradualmente, lo que significa que el formato delta es bastante eficiente, requiriendo alrededor de 300 bits (38 bytes) por tabla Huffman completa.

Se utiliza un mapa de bits para mostrar qué símbolos se usan dentro del bloque y deben incluirse en los árboles de Huffman. Es probable que los datos binarios utilicen los 256 símbolos representables por un byte, mientras que los datos textuales pueden usar solo un pequeño subconjunto de los valores disponibles, que quizás cubra el rango ASCII entre 32 y 126. Almacenar 256 bits cero sería ineficiente si en su mayoría no se usaran. Se utiliza un método disperso : los 256 símbolos se dividen en 16 rangos, y solo si se usan 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 bits adicional de 16 bits al principio. 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 codificándolos como si tuvieran una longitud de bits cero con codificación de longitud de ejecución y codificación Huffman adicional.

No existe una especificación formal para bzip2, aunque se ha obtenido una especificación informal mediante ingeniería inversa a partir de la implementación de referencia. ^{[ 12 ]}

En resumen, un .bz2flujo consta de una cabecera de 4 bytes, seguida de cero o más bloques comprimidos, e inmediatamente después un marcador de fin de flujo que contiene un CRC de 32 bits para todo el flujo de texto plano procesado. Los bloques comprimidos están alineados a nivel de bits y no se utiliza relleno.

.magic:16 = firma/número mágico 'BZ' .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 verificación para este bloque .randomizado:1 = 0=>normal, 1=>aleatorizado (obsoleto) .origPtr:24 = puntero inicial en BWT para después de la destransformación .huffman_used_map:16 = mapa de bits, de rangos de 16 bytes, presente/no presente .huffman_used_bitmaps:0..256 = mapa de bits de los 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 = secuencias de bits terminadas en cero (0..62) de la tabla Huffman MTF (*selectors_used) .start_huffman_length:5 = 0..20 longitud de bits inicial para deltas de Huffman *.delta_bit_length:1..40 = 0=>siguiente símbolo; 1=>alterar longitud { 1 => disminuye la longitud; 0 => aumenta la longitud } (*(símbolos + 2) * grupos) .contents:2..∞ = Flujo de datos codificado en Huffman hasta el final del bloque (máx. 7372800 bits) .eos_magic:48 = 0x177245385090 (BCD sqrt(pi)) .crc:32 = suma de verificación para todo el flujo .padding:0..7 = alinear al byte completo 

Debido a la compresión RLE de primera etapa (véase más arriba), la longitud máxima de texto plano que  puede contener un único bloque bzip2 de 900 kB es de aproximadamente 46  MB (45.899.236  bytes). Esto puede ocurrir si todo el texto plano consiste únicamente en valores repetidos (el .bz2archivo resultante en este caso tiene  una longitud de 46 bytes). Se puede obtener un archivo aún más pequeño, de 40  bytes, utilizando una entrada que contenga exclusivamente valores de 251, lo que resulta en una relación de compresión aparente de 1.147.480,9:1.

Un bloque comprimido en bzip2 se puede descomprimir sin necesidad de procesar los 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 . ^{[ 13 ]}

bzip2 comprime la mayoría de los archivos de forma más eficaz que los algoritmos de compresión más antiguos LZW ( .Z ) y Deflate ( .zip y .gz ), pero es considerablemente más lento. LZMA suele ser más eficiente en cuanto al espacio que bzip2, a costa de una velocidad de compresión aún menor, aunque ofrece una descompresión más rápida. ^{[ 14 ]}

bzip2 comprime datos en bloques de 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 mover al frente y la codificación Huffman . El predecesor 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 . ^{[ 15 ]} bzip3, ^{[ 16 ]} un compresor moderno que comparte un origen 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. Motivados por el largo tiempo requerido para la compresión, en 2003 se creó una versión modificada llamada pbzip2 que utilizaba multihilo 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. ^{[ 17 ]} A mayo de 2010 Esta funcionalidad no se ha incorporado al proyecto principal.

Al igual que gzip , bzip2 es solo un compresor de datos. No es un archivador como tar o ZIP; el formato de archivo bzip2 no admite almacenar el contenido de varios archivos en un solo 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 podía realizar mediante un programa independiente que creaba un archivo comprimido que luego se comprimía con bzip2, y la descompresión se podía realizar mediante bzip2 descomprimiendo el archivo comprimido y otro programa descomprimiéndolo. Algunos archivadores tienen soporte integrado para compresión y descompresión, por lo que no es necesario usar el programa bzip2 para comprimir o descomprimir el archivo. GnuPG también tiene soporte integrado para compresión y descompresión bzip2.

• Comparación de formatos de archivo
• Comparación de archivadores de archivos
• Lista de formatos de archivo
• Lista de compresores de archivos
• rzip

• El comando bzip2 - por el Proyecto de Información de Linux (LINFO)
• bzip2 para Windows
• MacBzip2 archivado el 6 de febrero de 2005 en Wayback Machine (para Mac OS clásico ; en Mac OS X , el bzip2 estándar está disponible en la línea de comandos).
• Comparación de características y pruebas de rendimiento para diferentes tipos de implementaciones paralelas de bzip2 disponibles.
• El compresor bzip original puede estar sujeto a patentes.