bzip2 es un programa de compresión de archivos de código abierto y gratuito que utiliza el algoritmo de Burrows-Wheeler . Solo comprime archivos individuales y no es un archivador de archivos . Está desarrollado por Julian Seward y mantenido por Federico Mena . Seward hizo el primer lanzamiento público de bzip2, 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. [3]
Autor (es) original (es) | Julian Seward |
---|---|
Desarrollador (es) | Federico Mena |
Versión inicial | 18 de julio de 1996 [1] |
Lanzamiento estable | 1.0.8 / 13 de julio de 2019 |
Repositorio | https://gitlab.com/federicomenaquintero/bzip2 https://sourceware.org/git/bzip2.git |
Sistema operativo | Multiplataforma [ ¿cuál? ] |
Tipo | Compresión de datos |
Licencia | Licencia similar a BSD [2] |
Sitio web | sourceware |
Extensión de nombre de archivo | .bz2 |
---|---|
Tipo de medio de Internet | application/x-bzip2 |
Código de tipo | Bzp2 |
Identificador de tipo uniforme (UTI) | public.archive.bzip2 |
número mágico | BZh |
Desarrollado por | Julian Seward |
Tipo de formato | Compresión de datos |
¿ Formato abierto ? | sí |
Eficiencia de compresión
bzip2 comprime la mayoría de los archivos de forma más eficaz que los algoritmos de compresión LZW ( .Z ) y Deflate ( .zip y .gz ) anteriores, pero es considerablemente más lento. LZMA generalmente ocupa más espacio que bzip2 a expensas de una velocidad de compresión aún más lenta, mientras que tiene una descompresión mucho más rápida. [4]
bzip2 comprime datos en bloques de tamaño entre 100 y 900 kB y usa la transformación de Burrows-Wheeler para convertir secuencias de caracteres que se repiten con frecuencia en cadenas de letras idénticas. Luego aplica la transformación de movimiento al frente y la codificación de Huffman . El antepasado 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 . [5]
El rendimiento de bzip2 es asimétrico, ya que la descompresión es relativamente rápida. Motivado por el gran tiempo de CPU requerido para la compresión, se creó una versión modificada en 2003 llamada pbzip2 que admitía múltiples subprocesos , lo que brindaba mejoras de velocidad casi lineales en computadoras con múltiples CPU y múltiples núcleos. [6] En mayo de 2010[actualizar], esta funcionalidad no se ha incorporado al proyecto principal.
Como gzip, bzip2 es solo un compresor de datos. No es un archivador como tar o ZIP; el programa en sí no tiene funciones para múltiples archivos, cifrado o división de archivos, pero, en la tradición de UNIX , se basa en cambio en utilidades externas separadas como tar y GnuPG para estas tareas.
La herramienta grep
-basada bzgrep
permite buscar directamente a través de texto comprimido sin necesidad de descomprimir el contenido primero. [7]
Pila de compresión
Bzip2 utiliza varias capas de técnicas de compresión apiladas una encima de la otra, que ocurren en el siguiente orden durante la compresión y en orden inverso durante la descompresión:
- Codificación de longitud de ejecución (RLE) de los datos iniciales.
- Transformada de Burrows-Wheeler (BWT) o clasificación de bloques.
- Transformación de movimiento al frente (MTF).
- Codificación de longitud de ejecución (RLE) del resultado de MTF.
- Codificación de Huffman .
- Selección entre varias tablas de Huffman.
- Codificación unaria en base 1 de la selección de tablas de Huffman.
- Codificación delta (Δ) de longitudes de bits de código Huffman.
- Sparse matriz de bits que muestra que se utilizan símbolos.
Codificación de longitud de ejecución inicial
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 AAAAAAABBBBCCCD
se reemplaza con AAAA\3BBBB\0CCCD
, donde \3
y \0
representan valores de bytes 3 y 0 respectivamente. Las series de símbolos siempre se transforman después de 4 símbolos consecutivos, incluso si la longitud de la 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 teóricamente permite codificar corridas de longitud 256-259, el codificador de referencia no producirá tal salida.
El autor de bzip2 ha declarado que el paso de RLE fue un error histórico y solo tenía la intención de proteger la implementación original de BWT de casos patológicos. [8]
Transformada de Burrows-Wheeler
Este es el tipo de bloque reversible que se encuentra en el núcleo de bzip2. El bloque es completamente autónomo, y los búferes de entrada y salida 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 la totalidad del búfer, girada para comenzar desde el símbolo i -ésimo. Después de la rotación, las filas de la matriz se clasifican en orden alfabético (numérico). Se almacena un puntero de 24 bits que marca la posición inicial para cuando el bloque no se transforma. En la práctica, no es necesario construir la matriz completa; más bien, 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; contiene todo el búfer, pero reordenado para que sea probable que contenga grandes series de símbolos idénticos.
Transformación de movimiento al frente
Nuevamente, esta transformación no 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 reemplaza por su ubicación (índice) en la matriz y ese símbolo se baraja al frente de la matriz. El efecto es que los símbolos que se repiten inmediatamente se reemplazan por cero símbolos (las series largas de cualquier símbolo arbitrario se convierten en series de cero símbolos), mientras que otros símbolos se reasignan de acuerdo con 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 son idénticos (diferentes símbolos de entrada recurrentes pueden en realidad mapearse con el mismo símbolo de salida). Dichos datos se pueden codificar de manera muy eficiente mediante cualquier método de compresión heredado.
Codificación de longitud de ejecución del resultado MTF
Las cadenas largas de ceros en la salida de la transformación de movimiento al frente (que provienen de símbolos repetidos en la salida del BWT) se reemplazan por una secuencia de dos códigos especiales, RUNA y RUNB, que representan la longitud de 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 produciría cero, en su lugar aumentaría un contador para luego codificar con RUNA y RUNB).
La secuencia 0, 0, 0, 0, 0, 1
se representaría como RUNA, RUNB, 1
; RUNA, RUNB
representa el valor 5 como se describe a continuación. El código 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 enteros arbitrariamente largos (en la práctica, esto suele estar limitado por el tamaño del bloque, por lo que este paso no codifica una ejecución de más de900 000 bytes ). La longitud de la ejecución se codifica de esta manera: asignando valores posicionales de 1 al primer bit, 2 al segundo, 4 al tercero, etc.en la secuencia, multiplique cada valor posicional en un lugar RUNB por 2 y sume todos los valores posicionales resultantes (para valores RUNA y RUNB por igual) juntos. Esto es similar a la numeración biyectiva de base 2 . Por lo tanto, la secuencia RUNA, RUNB
da como resultado el valor (1 + 2 × 2) = 5. Como ejemplo más complicado:
RUNA RUNB RUNA RUNA RUNB (ABAAB) 1 2 4 8 16 1 4 4 8 32 = 49
Codificación Huffman
Este proceso reemplaza los símbolos de longitud fija en el rango 0-258 con códigos de longitud variable basados en la frecuencia de uso. Los códigos utilizados con más frecuencia terminan siendo más cortos (2–3 bits), mientras que los códigos raros se pueden asignar hasta 20 bits. Los códigos se seleccionan cuidadosamente 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 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 la MTF ordinaria), ahorrando así un símbolo para el final. marcador de flujo (y explicando por qué solo n - 1 símbolos están codificados 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 final de -marcador de flujo con valor 2.
- 0: RUNA,
- 1: EJECUTAR,
- 2–257: valores de bytes 0–255,
- 258: fin de flujo, procesamiento final (podría ser tan bajo como 2).
Varias tablas de Huffman
Se pueden usar varias tablas 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, volviendo a seleccionar la tabla más adecuada antes de cada 50 símbolos procesados. Esto tiene la ventaja de tener una dinámica de Huffman muy receptiva sin tener que suministrar continuamente nuevas tablas, como se requeriría en DEFLATE . La codificación de 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 más corto de Huffman en uso.
Codificación unaria de la selección de tablas de Huffman
Si se utilizan varias tablas de Huffman, la selección de cada tabla (numerada de 0 a 5) se realiza a partir de una lista mediante una ejecución de bits terminados en cero de entre 1 y 6 bits de longitud. La selección está 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 menos. Es probable que esta expansión se vea ensombrecida en gran medida por la ventaja de seleccionar tablas de Huffman más apropiadas, y el caso común de continuar usando la misma tabla de Huffman se representa como un solo bit. En lugar de codificación unaria, efectivamente se trata de una forma extrema de un árbol de Huffman, donde cada código tiene la mitad de probabilidad que el código anterior.
Codificación delta
Se requieren longitudes de bits de código Huffman para reconstruir cada una de las tablas de 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 del bit anterior debe duplicarse para el código actual, mientras que un bit (1) significa que debe leerse un bit adicional y la longitud del bit debe incrementarse o disminuirse en función de ese valor.
En el caso común, se usa un solo bit por símbolo por tabla y el peor de los casos, pasar de la longitud 1 a la longitud 20, requeriría aproximadamente 37 bits. Como resultado de la codificación MTF anterior, las longitudes de código comenzarían en 2 a 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. .
Matriz de bits dispersos
Se usa 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 usen los 256 símbolos representables por un byte, mientras que los datos textuales solo pueden usar un pequeño subconjunto de valores disponibles, quizás cubriendo el rango ASCII entre 32 y 126. Almacenar 256 bits cero sería ineficaz si no se usaran en su mayoría. Se usa 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 adicional de 16 bits en la parte frontal.
El mapa de bits total utiliza entre 32 y 272 bits de almacenamiento (4–34 bytes). Por el contrario, el algoritmo DEFLATE mostraría la ausencia de símbolos codificando los símbolos con una longitud de bit cero con codificación de longitud de ejecución y codificación Huffman adicional.
Formato de archivo
No existe una 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. [9]
Como descripción general, un .bz2
flujo consta de un encabezado de 4 bytes, seguido de cero o más bloques comprimidos, seguido inmediatamente por un marcador de fin de flujo que contiene un CRC de 32 bits para el flujo completo de texto sin formato procesado. Los bloques comprimidos están alineados en bits y no se produce ningún relleno.
.magic: 16 = firma / número mágico de '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).magic_comprimido: 48 = 0x314159265359 (BCD (pi)).crc: 32 = suma de comprobación para este bloque.aleatorizado: 1 = 0 => normal, 1 => aleatorizado (obsoleto).origPtr: 24 = puntero de inicio en BWT para después de untransform.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, presente / no presente (múltiplos de 16).huffman_groups: 3 = 2..6 número de diferentes tablas de Huffman 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 de Huffman con 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 => alterar la longitud {1 => disminución de la longitud; 0 => longitud de incremento} (* (símbolos + 2) * grupos).contenido: 2..∞ = Flujo de datos codificados por Huffman hasta el final del bloque (máx. 7372800 bit).eos_magic: 48 = 0x177245385090 (BCD sqrt (pi)).crc: 32 = suma de comprobación para todo el flujo.padding: 0..7 = alinear a byte completo
Debido a la compresión RLE de la primera etapa (ver arriba), la longitud máxima de texto sin formato 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 sin formato consta en su totalidad de valores repetidos (el .bz2
archivo resultante en este caso tiene una longitud de 46 bytes). Se puede lograr un archivo aún más pequeño de 40 bytes usando una entrada que contenga valores enteros de 251, una relación de compresión aparente de 1147480.9: 1.
Los bloques comprimidos en bzip2 se pueden descomprimir de forma independiente, 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 usar en aplicaciones de big data con marcos de computación en clúster como Hadoop y Apache Spark . [10]
Implementaciones
Además de la implementación de referencia original de Julian Seward , los siguientes programas admiten el formato bzip2.
- 7-Zip : Escrito por Igor Pavlov en C ++ , la suite 7-Zip contiene un codificador / decodificador bzip2 con licencia gratuita. 7-Zip viene con soporte de subprocesos múltiples.
- micro-bzip2 : Una versión de Rob Landley diseñada para un tamaño de código compilado reducido y disponible bajo GNU LGPL .
- PBZIP2 : Implementación basada en pthreads paralelos en C ++ por Jeff Gilchrist (y versión de Windows ).
- bzip2smp : una modificación
libbzip2
que tiene la paralelización SMP "pirateada" por Konstantin Isakov. - smpbzip2 : Otro intento en bzip2 paralelo, por Niels Werensteijn.
- pyflate : Un decodificador bzip2 y DEFLATE ( gzip ) independiente puro de Python de Paul Sladen. Probablemente útil para la investigación y la creación de prototipos, disponible bajo BSD / GPL / LGPL , o cualquier otra licencia compatible con DFSG .
- bz2 : módulo de Python 3 para admitir la compresión bzip2 (biblioteca estándar de Python).
- BZip de Arnaud Bouchez : Implementación usando la biblioteca C o código ensamblador i386 optimizado.
- lbzip2 : filtro bzip2 / bunzip2 (compresor / descompresor bzip2) basado en pthreads en paralelo para entrada / salida de acceso secuencial, por László Érsek.
- mpibzip2 : Una implementación habilitada para MPI que comprime / descomprime en paralelo, por Jeff Gilchrist, disponible bajo una licencia estilo BSD.
- Apache Commons Compress El proyecto Apache Commons Compress contiene implementaciones Java del compresor y descompresor Bzip2.
- jbzip2 : una implementación Java de bzip2 disponible bajo la licencia MIT
- DotNetZip : incluye una implementación en C # de bzip2, derivada de la implementación de Java en Apache Commons Compress. Incluye una biblioteca codificadora / decodificadora .NET bzip2 multiproceso y una herramienta de línea de comandos bzip2 en código administrado.
- DotNetCompression : una implementación de transmisión de bzip2 en C # administrado que se ajusta a la API de System.IO.Compression e incluye ensamblados para .NET Framework , .NET Compact Framework , Xamarin . iOS , Xamarin . Android , Xamarin . Mac , Windows Phone , Xbox 360 , Silverlight , Mono y como biblioteca de clases portátil.
Ver también
- Comparación de formatos de archivo
- Comparación de archivadores de archivos
- Lista de formatos de archivo
- Lista de archivadores de archivos
- Lista de comandos de Unix
- rzip
Referencias
- ^ bzip2 / README , 18 de julio de 1996 (versión 0.15)
- ^ "bzip2: Inicio" . Julian Seward . Consultado el 21 de julio de 2019 .
¿Por qué querría usarlo? [..] Porque es de código abierto (licencia estilo BSD) y, hasta donde yo sé, libre de patentes.
- ^ "Artículos con etiqueta" bzip2 " " " . People.gnome.org .
- ^ "7-zip frente a bzip2 frente a gzip" . Archivado desde el original el 24 de abril de 2016 . Consultado el 12 de febrero de 2019 .
- ^ "La página de inicio de bzip2" . Archivado desde el original el 4 de julio de 1998 . Consultado el 5 de marzo de 2009 . - sección "¿Cómo se relaciona con su oferta anterior (bzip-0.21)?"
- ^ "Compressionratings.com" . ww1.compressionratings.com .
- ^ "comando bzgrep en Linux con ejemplos" . GeeksforGeeks . 4 de enero de 2019.
- ^ "bzip2 y libbzip2, versión 1.0.8" . sourceware.org .
- ^ "Especificación del formato BZIP2" (PDF) .
- ^ "[HADOOP-4012] Proporciona soporte de división para archivos comprimidos bzip2 - ASF JIRA" . Fundación de software Apache . 2009 . Consultado el 14 de octubre de 2015 .
enlaces externos
- El comando bzip2 - por The Linux Information Project (LINFO)
- bzip2 para Windows
- Bzip2 gráfico para Windows (WBZip2)
- MacBzip2 (para Mac OS clásico ; en Mac OS X , el bzip2 estándar está disponible en la línea de comandos)
- Comparación de funciones y puntos de referencia para diferentes tipos de implementaciones bzip2 paralelas disponibles
- 4 implementaciones paralelas de bzip2 Archivado el 18 de octubre de 2006 en Wayback Machine en el blog de noticias de compresión de datos
- El compresor bzip original - puede estar restringido por patentes