Bzip2

Bzip2 busca maximizar la compresión sin perder datos, haciendo que el almacenamiento y la transmisión de información sean más eficientes, en particular con archivos de texto.

Descripción del Algoritmo

bzip2 es un algoritmo de compresión sin pérdida basado en una combinación de técnicas de manipulación de datos, diseñado principalmente para comprimir archivos de texto y datos generales. Su flujo de compresión se estructura en varias etapas, cada una diseñada para transformar los datos de forma que se reduzca su redundancia y se obtenga una compresión eficaz.

Bzip2 emplea una técnica de compresión por pila que implica varias capas una encima de otra y luego para descomprimir se sigue el orden inverso. Inicialmente, realiza una codificación Run-Length Encoding (RLE) sobre los datos iniciales, aplica el algoritmo Burrows-Wheeler (también conocido como ordenación por bloques), realiza una transformación aplicando el algoritmo Move-to-Front (MTF), al resultado de esta transformación se aplica nuevamente RLE, luego aplica la codificación de Huffman antes de seleccionar entre diferentes tablas y usar una codificación unaria en base 1 de la tabla seleccionada, posteriormente la codificación delta de las longitudes de bits del código y la matriz de bits dispersa, que muestra los símbolos utilizados.

A continuación se explica con mayor detalle las etapas del flujo y su relevancia en el algoritmo:

Run-Length Encoding inicial: La primera etapa de Bzip2 aplica RLE, un método que simplifica series consecutivas de valores repetidos (por ejemplo, caracteres idénticos) al codificar la longitud de cada serie. Esto ayuda a reducir secuencias repetitivas y prepara los datos para las transformaciones posteriores.
Transformación de Burrows-Wheeler (BWT): El corazón de Bzip2 es la Transformación de Burrows-Wheeler, que reorganiza los datos en una serie de permutaciones donde los caracteres repetidos tienden a agruparse. La BWT no comprime por sí sola, pero reordena los datos de modo que otras técnicas de compresión (como RLE y Huffman) sean más efectivas. La transformación genera una cadena de texto que puede comprimirse mejor debido a la presencia de patrones repetitivos.
Transformación Move-to-Front (MTF): Tras la BWT, Bzip2 aplica la transformación Move-to-Front, que convierte símbolos repetidos consecutivos en valores pequeños, lo que permite que la siguiente codificación de longitud de ejecución capture patrones de repetición eficientemente.
Codificación de Longitud de Ejecución del Resultado MTF: Se aplica nuevamente una RLE al resultado de la MTF para comprimir las secuencias repetitivas de números pequeños generadas. Esta etapa ayuda a simplificar los datos y mejora la eficacia de la codificación de Huffman.
Codificación de Huffman: La etapa final de compresión en Bzip2 utiliza la codificación de Huffman, generando tablas en paralelo. El método de compresión que asigna códigos cortos a símbolos frecuentes y códigos largos a los menos frecuentes. La aplicación de esta codificación binaria produce un archivo comprimido de tamaño reducido.
Selección de Múltiples Tablas de Huffman y Codificación unaria en base 1: Se evalúan diferentes tablas de Huffman y selecciona la más eficaz, es decir, la tabla que da lugar al archivo más pequeño. Seleccionada la tabla, se aplica codificación unaria en base 1 para indicar cuál de las tablas fue utilizada. También se aplica una codificación delta a las longitudes de los códigos de Huffman, seguida de una representación en bit para indicar qué símbolos están en uso. Esto maximiza la compresión de cada bloque y reduce el tamaño global del archivo.

Ventajas y Características

Alta Compresión y Eficiencia: Como se mencionó, Bzip2 utiliza una combinación de técnicas, lo que permite una compresión eficiente, especialmente en datos textuales con patrones repetitivos. La BWT reorganiza los datos para agrupar caracteres similares, lo cual mejora la capacidad de compresión subsecuente mediante MTF y codificación Huffman. Esto lo hace ideal para archivos de texto y datos que contengan redundancia localizada, logrando ratios de compresión notoriamente mejores que otros métodos como gzip para ciertos tipos de archivos.
Compresión Basada en Bloques: Bzip2 procesa los datos en bloques de tamaño configurable, usualmente es de 100 a 900 KB, por defecto es de 900 KB, lo cual permite manejar archivos grandes sin cargar todo el contenido en memoria. Esta estructura basada en bloques también ayuda a la descompresión, ya que permite acceder a segmentos específicos de datos, lo que es útil en archivos divididos o al recuperar partes específicas de datos dañados.
Control de Integridad: Bzip2 incluye sumas de verificación en cada bloque comprimido, lo que permite verificar la integridad de los datos durante la descompresión. Esto asegura que los archivos descomprimidos coincidan con los originales, ofreciendo una capa adicional de seguridad en aplicaciones donde la exactitud de los datos es crucial.

Bzip2 es popular para archivos de texto, archivos log y otros datos que contienen patrones de repetición. Es ampliamente usado en entornos Unix y Linux para comprimir grandes volúmenes de datos en sistemas de archivos y backups. En transferencia de datos a través de redes, Bzip2 es ventajoso cuando se prioriza el tamaño del archivo sobre la velocidad de compresión, ya que reduce significativamente el ancho de banda necesario. También es común en herramientas de archivado como tar, facilitando la compresión y descompresión de múltiples archivos de forma conjunta.

Ejemplos de uso e Implementación

Como ejemplo se utiliza la siguiente linea de texto "abracadabra: alabar a alabarda" A continuación, se muestra parte de la implementación del código de forma simplificada para las pasos de compresión, estos son BWT, MTF, RLE y Huffman:

Transformación de Burrows-Wheeler (BWT)

def burrows_wheeler_transform(s): 
    s = s + "$"  # Añadir un marcador de final
    table = sorted(s[i:] + s[:i] for i in range(len(s)))
    last_column = [row[-1] for row in table]
    return ''.join(last_column)

Este código realiza la BWT agregando un símbolo de fin ($) para marcar el final del texto. Luego genera todas las rotaciones posibles y ordena las rotaciones lexicográficamente, tomando la última columna de la tabla resultante.

Para el ejemplo se obtiene lo siguiente:

$abracadabra:\:alabar\:a\:alabarda$ $\Rightarrow$ $r:aaa\:\:drlld\$rc\:\:bbaaaaaraaaabba$

Transformación Move-to-Front (MTF)

def move_to_front_encode(bwt_result):
    symbols = list(set(bwt_result))
    symbols.sort()
    result = []
    for char in bwt_result:
        index = symbols.index(char)
        result.append(index)
        symbols.pop(index)
        symbols.insert(0, char)
    return result

La función de MTF convierte cada símbolo a su posición en una lista de caracteres, moviendo el símbolo usado al frente tras cada acceso. Esto ayuda a que símbolos repetidos se representen por índices pequeños, lo cual es beneficioso para la siguiente etapa de RLE.

Aplicando a la salida anterior:

$r:aaa\:\:drlld\$rc\:\:bbaaaaaraaaabba$ $\Rightarrow$ $[8, 3, 4, 0, 0, 3, 7, 4, 8, 0, 2, 6, 3, 8, 5, 0, 8, 0, 7, 0, 0, 0, 0, 4, 1, 0, 0, 0, 2, 0, 1]$

Run-Length Encoding (RLE)

def run_length_encode(data):
    encoding = []
    i = 0
    while i < len(data):
        count = 1
        while i + 1 < len(data) and data[i] == data[i + 1]:
            count += 1
            i += 1
        encoding.append((data[i], count))
        i += 1
    return encoding

RLE comprime secuencias de caracteres repetidos al almacenarlas como pares (carácter, conteo), lo cual reduce la redundancia en cadenas con secuencias de símbolos repetidos.

Siguiendo con el ejemplo: $[8, 3, 4, 0, 0, 3, 7, 4, 8, 0, 2, 6, 3, 8, 5, 0, 8, 0, 7, 0, 0, 0, 0, 4, 1, 0, 0, 0, 2, 0, 1]$ $\Rightarrow$

$[(8, 1)$$,(3, 1)$,$(4, 1)$,$(0, 2)$,$(3, 1)$,$(7, 1)$,$(4, 1)$,$(8, 1)$,$(0, 1)$,$(2, 1)$,$(6, 1)$,$(3, 1)$,$(8, 1)$,$(5, 1)$,$(0, 1)$,$(8, 1)$,$(0, 1)$,$(7, 1)$,$(0, 4)$, $(4, 1)$, $(1, 1)$, $(0, 3)$, $(2, 1)$, $(0, 1)$, $(1, 1)]$

Codificación de Huffman

La codificación de Huffman requiere la construcción de un árbol binario basado en las frecuencias de los símbolos. A continuación, un ejemplo de construcción del árbol:

import heapq
from collections import defaultdict

def huffman_tree(data):
    freq = defaultdict(int)
    for symbol in data:
        freq[symbol] += 1

    heap = [[weight, [symbol, ""]] for symbol, weight in freq.items()]
    heapq.heapify(heap)

    while len(heap) > 1:
        lo = heapq.heappop(heap)
        hi = heapq.heappop(heap)
        for pair in lo[1:]:
            pair[1] = '0' + pair[1]
        for pair in hi[1:]:
            pair[1] = '1' + pair[1]
        heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])

    return sorted(heapq.heappop(heap)[1:], key=lambda p: (len(p[-1]), p))

Este fragmento de código genera un árbol de Huffman a partir de los símbolos y sus frecuencias en los datos. Luego, cada símbolo se representa con un código binario, donde los símbolos más frecuentes tienen códigos más cortos.

Concluyendo el ejemplo:

$[(8, 1),$ $(3, 1),$ $(4, 1),$ $(0, 2),$ $(3, 1),$ $(7, 1)$, $(4, 1),$ $(8, 1),$ $(0, 1),$ $(2, 1),$ $(6, 1),$ $(3, 1),$ $(8, 1),$ $(5, 1),$ $(0, 1),$ $(8, 1),$ $(0, 1),$ $(7, 1),$ $(0, 4),$ $(4, 1),$ $(1, 1),$ $(0, 3),$ $(2, 1),$ $(0, 1),$ $(1, 1)]$ $\Rightarrow$

$[[0, '0'],$ $[8, '110'],$ $[1, '1000'],$ $[2, '1001'],$ $[3, '1110'],$ $[4, '1111'],$ $[7, '1011'],$ $[5, '10100'],$ $[6, '10101']]$

Para revisar implementación oficial de Bzip2 véase el repositorio oficial aquí: Bzip2

Referencias

Bzip2
Manual Bzip2
Salomon, D., & Motta, G. (2010). Data Compression: The Complete Reference (4th ed.). Springer.
Sayood, K. (2017). Introduction to Data Compression (5th ed.). Morgan Kaufmann.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
Burrows, M., & Wheeler, D. J. (1994). A Block-Sorting Lossless Data Compression Algorithm. Digital Equipment Corporation.