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).

Several identically sized Huffman tables can be used with a block if the gain from using them is greater than the cost of including the extra table. At least 2 and up to 6 tables can be present, with the most appropriate table being reselected before every 50 symbols processed. This has the advantage of having very responsive Huffman dynamics without having to continuously supply new tables, as would be required in DEFLATE. Run-length encoding in the previous step is designed to take care of codes that have an inverse probability of use higher than the shortest code Huffman code in use.

If multiple Huffman tables are in use, the selection of each table (numbered 0 to 5) is done from a list by a zero-terminated bit run between 1 and 6 bits in length. The selection is into a MTF list of the tables. Using this feature results in a maximal expansion of around 1.015, but generally less. This expansion is likely to be greatly over-shadowed by the advantage of selecting more appropriate Huffman tables, and the common-case of continuing to use the same Huffman table is represented as a single bit. Rather than unary encoding, effectively this is an extreme form of a Huffman tree, where each code has half the probability of the previous code.

Huffman-code bit lengths are required to reconstruct each of the used canonical Huffman tables. Each bit length is stored as an encoded difference against the previous-code bit length. A zero bit (0) means that the previous bit length should be duplicated for the current code, whilst a one bit (1) means that a further bit should be read and the bit length incremented or decremented based on that value. In the common case a single bit is used per symbol per table and the worst case—going from length 1 to length 20—would require approximately 37 bits. As a result of the earlier MTF encoding, code lengths would start at 2–3 bits long (very frequently used codes) and gradually increase, meaning that the delta format is fairly efficient, requiring around 300 bits (38 bytes) per full Huffman table.

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.