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 la tabla de Huffman.
- Codificación delta (Δ) de longitudes de bits de código Huffman.
- Matriz de bits dispersa que muestra qué símbolos se utilizan.
Edición de 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 por AAAA\3BBBB\0CCCD, donde \3 y \0 representan los 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 causar una expansión de 1,25, y en en el mejor de los casos, una reducción a < 0,02. Si bien la especificación teóricamente permite que se codifiquen ejecuciones de longitud 256-259, el codificador de referencia no producirá tal salida.
El autor de bzip2 ha declarado que el paso RLE fue un error histórico y solo fue intencionado para proteger la implementación original de BWT de casos patológicos.
Burrows – Wheeler transformEdit
Este es el tipo de bloque reversible que está en el núcleo de bzip2. El bloque es completamente autónomo, y los búferes de entrada y salida siguen siendo 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 (nocional), 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; esto contiene todo el búfer, pero reordenado para que sea probable que contenga grandes series de símbolos idénticos.
Move-to-front transformEdit
De nuevo, 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 según su frecuencia local.
Gran cantidad de datos «naturales» contiene 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 enteros bajos, muchos de ellos son idénticos (diferentes símbolos de entrada recurrentes pueden mapear en realidad al 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 de MTF resultEdit
Largas cadenas 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 produzca cero, en su lugar aumenta 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 de 900000 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
Huffman codingEdit
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 es necesario hacer referencia explícita al primer símbolo en la tabla MTF (sería cero en la MTF ordinaria), por lo que se guarda 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 todo el bloque estará formado por RUNA y RUNB (repitiendo implícitamente el byte único) y un final de -marcador de flujo con valor 2.
0: RUNA, 1: RUNB, 2–257: valores de byte 0-255, 258: final de flujo, procesamiento de finalización (podría ser tan bajo como 2).
Varias tablas de HuffmanEditar
Se pueden usar 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, volviendo a seleccionar la tabla más adecuada antes de cada 50 símbolos procesados. Esto tiene la ventaja de tener una dinámica 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 HuffmanEditar
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, esta es efectivamente una forma extrema de árbol de Huffman, donde cada código tiene la mitad de probabilidad que el código anterior.
Codificación deltaEdit
Las longitudes de bits del código Huffman son necesarios 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 .
Sparse bit arrayEdit
Se utiliza un mapa de bits para mostrar qué símbolos se utilizan 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 la mayoría no se usaran. 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 delantera.
El mapa de bits total usa entre 32 y 272 bits de almacenamiento (4–34 bytes). Por el contrario, 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.