Huffman Compression

Campobit: operaciones de bajo nivel y aritmética de bits

En muchos algoritmos de compresión, como Huffman, no alcanza con guardar caracteres completos. Para aprovechar mejor el espacio hay que escribir códigos de longitud variable, y eso obliga a manipular datos a nivel de bits.

Un campobit es una estructura que permite almacenar una secuencia de bits dentro de una variable numérica junto con un contador de tamaño. La operación básica es bits_agregar, que añade un bit nuevo al final del campo.

Agregar un bit con desplazamiento y OR

Supongamos que la estructura contiene 12 bits y queremos agregar un 1. Primero se incrementa el tamaño y luego se crea una máscara desplazando el valor 1 hasta la posición correcta.

bits->bits   = 0000 0001 1000 1000
bits->tamano = 12

mask         = 0001 0000 0000 0000

bits->bits   = 0000 0001 1000 1000
OR mask      = 0001 0000 0000 0000
-----------------------------------
resultado    = 0001 0001 1000 1000

Si el bit a agregar es 0, normalmente no hace falta modificar el valor numérico porque las posiciones nuevas se asumen en cero; solo se actualiza tamano.

static int bits_agregar(campobits* bits, int bit) {
    if (!bits || bits->tamano >= (int)(sizeof(bits->bits) * 8)) {
        return -1;
    }

    bits->tamano++;

    if (bit == 1) {
        bits->bits |= (0x1 << (bits->tamano - 1));
    }

    return 0;
}

Qué es el algoritmo de Huffman

Huffman es un método de compresión sin pérdida que asigna códigos de longitud variable: los símbolos más frecuentes reciben códigos más cortos y los menos frecuentes reciben códigos más largos.

La idea central es construir un árbol binario donde cada hoja representa un símbolo. El camino desde la raíz hasta una hoja determina su código: por ejemplo, izquierda puede representar 0 y derecha 1.

Procesos en la compresión

1. Calcular frecuencias

Se lee el archivo de entrada y se cuenta cuántas veces aparece cada carácter. Para texto basado en bytes, se puede usar un arreglo de 256 posiciones.

static int calcular_frecuencias(int* frecuencias, char* entrada) {
    for (int i = 0; i < 256; i++) {
        frecuencias[i] = 0;
    }

    /* Leer el archivo y contar ocurrencias... */
    return 0;
}

2. Construir el árbol de Huffman

Cada símbolo con frecuencia positiva se inserta en una cola de prioridad. Luego se extraen los dos nodos con menor frecuencia, se combinan en un padre y se reinserta el resultado. El proceso termina cuando queda un único nodo: la raíz.

static Arbol crear_huffman(int* frecuencias) {
    PQ pq = pq_create();

    /* Insertar símbolos con frecuencia positiva... */
    /* Combinar los dos menores hasta obtener la raíz... */

    return raiz;
}

3. Crear la tabla de códigos

Se recorre el árbol de forma recursiva. Cada vez que se baja a la izquierda se agrega un 0; cada vez que se baja a la derecha se agrega un 1. Al llegar a una hoja, el campobit acumulado es el código del carácter.

Hay dos enfoques comunes:

• Copias locales: cada rama recibe su propia copia del campo de bits. Es más simple y seguro.
• Modificación in situ: se modifica el mismo objeto y se elimina el último bit al volver de la recursión. Ahorra copias, pero exige más cuidado.

4. Codificar el archivo

Una vez generada la tabla, el archivo se lee nuevamente. Cada carácter se reemplaza por su secuencia de bits y se escribe en el flujo comprimido junto con la información necesaria para reconstruir el árbol.

Eliminar el último bit

Si se usa modificación in situ, una función como bits_remove_last permite retroceder un paso en el camino del árbol.

static int bits_remove_last(campobits* bits) {
    if (!bits || bits->tamano <= 0) {
        return -1;
    }

    int last_bit = (bits->bits >> (bits->tamano - 1)) & 0x1;
    bits->tamano--;
    bits->bits &= ~(0x1 << bits->tamano);

    return last_bit;
}

Procesos en la descompresión

1. Reconstruir el árbol

El descompresor lee la representación del árbol guardada en el archivo comprimido. Normalmente se usa un recorrido preorden para distinguir nodos internos y hojas.

static Arbol leer_arbol(BitStream bs) {
    /* Reconstruir el árbol a partir de los bits leídos. */
}

2. Decodificar el flujo de bits

Con el árbol reconstruido, se leen bits uno por uno. Un 0 mueve el cursor a la izquierda y un 1 a la derecha. Al llegar a una hoja se escribe el carácter y se vuelve a la raíz.

static void decodificar(BitStream in, BitStream out, Arbol arbol) {
    /* Recorrer el árbol con cada bit y escribir caracteres. */
}