Huffman Compressing Algorithm

Este documento explica el algoritmo de compresión de Huffman, sus conceptos básicos y los procesos involucrados tanto en la compresión como en la descompresión de archivos.

Campobit: Operaciones de Bajo Nivel y Aritmética de Bits

En muchos algoritmos de compresión (como el de Huffman) se requiere manipular datos a nivel de bits para optimizar el espacio. Un campobit es una estructura que nos permite almacenar una secuencia de bits en una variable numérica y realizar operaciones sobre ellos.

La operación básica que veremos es bits_agregar, que añade un bit (0 o 1) al final de nuestro campo de bits. Para entenderla, pensemos en el concepto de desplazamiento de bits: mover un bit a la izquierda o a la derecha. En este caso, usamos el desplazamiento para posicionar el nuevo bit en el lugar correcto.

Por ejemplo, supongamos que tenemos una estructura campobits con:

bits->bits  = 0001 1000 1000   (en binario)
bits->tamano = 12
      

Y queremos agregar un bit 1:

1. Incremento del tamaño: Se incrementa bits->tamano de 12 a 13, ya que se añade un bit más.
2. Cálculo de la máscara: Se calcula 0x1 << (bits->tamano - 1), lo que equivale a 0x1 << 12. Esto genera una máscara en binario:
   0001 0000 0000 0000
3. Actualización del campo de bits: Se utiliza la operación OR (|) para combinar el valor actual de bits->bits con la máscara, de forma que se agrega el bit 1 en la posición correcta sin alterar los otros bits:
   bits->bits = 0000 0001 1000 1000 OR = 0001 0000 0000 0000 ------------------------------ Resultado = 0001 0001 1000 1000

Si en lugar de un 1 se quisiera agregar un 0, no es necesario modificar bits->bits (ya que se asume que sus posiciones están en 0) y solo se incrementa bits->tamano.

/**
 * Función: bits_agregar
 *
 * Descripción:
 *   Esta función añade un bit (0 o 1) al final del campo de bits de la estructura 'campobits'.
 *   Se utiliza aritmética de bits para posicionar el nuevo bit en la ubicación correcta. El campo
 *   'tamano' de la estructura indica cuántos bits se han almacenado hasta el momento y se usa para
 *   calcular la posición en la que se debe agregar el nuevo bit.
 *
 * Parámetros:
 *   - campobits* bits: Puntero a la estructura que contiene:
 *         • bits->bits: El valor numérico que almacena los bits. Se asume que está inicializado a 0.
 *         • bits->tamano: La cantidad actual de bits que se han agregado.
 *   - int bit: Valor del bit a agregar (debe ser 0 o 1).
 *
 * Funcionamiento:
 *   1. **Verificación de seguridad:** Se confirma que el puntero 'bits' no sea nulo y que
 *      aún exista espacio para agregar otro bit, comparando 'bits->tamano' con el máximo número
 *      de bits que puede almacenar 'bits->bits'.
 *
 *   2. **Incremento del tamaño:** Se incrementa 'bits->tamano' en 1, ya que se está añadiendo un nuevo bit.
 *
 *   3. **Cálculo de la máscara y actualización:**
 *      - Si el bit a agregar es 1, se crea una máscara para posicionarlo correctamente. La máscara se
 *        calcula como:
 *
 *            0x1 << (bits->tamano - 1)
 *
 *        Esto desplaza el número 1 a la izquierda tantas posiciones como el número de bits ya agregados,
 *        ubicando el nuevo 1 en la posición adecuada.
 *
 *      - Se actualiza 'bits->bits' aplicando la operación OR (|) entre el valor actual y la máscara.
 *        Esto coloca el bit 1 en su posición sin alterar los otros bits.
 *
 *      - Si el bit es 0, no es necesario modificar 'bits->bits' ya que se asume que todas sus posiciones
 *        están inicialmente a 0; simplemente se incrementa 'bits->tamano'.
 *
 * Ejemplo detallado:
 *   Supongamos que tenemos una variable de tipo 'campobits' inicializada de la siguiente forma:
 *
 *       bits->bits  = 0001 1000 1000   (en binario)
 *       bits->tamano = 12
 *
 *   Y queremos agregar un bit 1:
 *
 *   a) **Incremento del tamaño:**  
 *      - Nuevo valor: bits->tamano pasa de 12 a 13.
 *
 *   b) **Cálculo de la máscara:**  
 *      - Se calcula: 0x1 << (13 - 1) = 0x1 << 12  
 *      - Esto coloca un 1 en la posición 12 (contando desde 0), lo que equivale a la representación:
 *
 *            0001 0000 0000 0000  (en binario)
 *
 *   c) **Actualización del campo de bits:**  
 *      - Se realiza la operación OR:
 *
 *            bits->bits  =  0000 0001 1000 1000
 *          | máscara     =  0001 0000 0000 0000
 *          -------------------------------------
 *            Resultado   =  0001 0001 1000 1000
 *
 * Nota:
 *   Se asume que 'bits->bits' está inicialmente en 0, por lo que agregar un bit 0 no requiere modificar
 *   su valor, solo se incrementa 'bits->tamano'.
 */
      

¿Qué es el algoritmo de Huffman?

El algoritmo de Huffman es un método de compresión sin pérdida que asigna códigos de longitud variable a los caracteres, de tal forma que los caracteres más frecuentes tienen códigos más cortos. Esto permite reducir el tamaño total del archivo comprimido.

Procesos en la compresión

La compresión con Huffman se realiza a través de varios pasos fundamentales:

1. Calcular Frecuencias

Se analiza el archivo de entrada para determinar la frecuencia de cada carácter. El proceso consiste en:

• Leer el archivo carácter por carácter.
• Contar las ocurrencias de cada uno y almacenarlas en un arreglo de tamaño 256 (para caracteres ASCII).

// Ejemplo de función en C para calcular frecuencias:
static int calcular_frecuencias(int* frecuencias, char* entrada) {
  // Inicializa el arreglo de frecuencias en 0.
  for (int i = 0; i < 256; i++) {
    frecuencias[i] = 0;
  }
  // Lee el archivo y cuenta ocurrencias...
}
      

2. Construir el Árbol de Huffman

Utilizando las frecuencias obtenidas:

• Se almacena cada par (carácter, frecuencia) en un nodo y se inserta en una cola de prioridad (heap), que ordena los nodos por frecuencia.
• Se extraen los dos nodos con menor frecuencia, se crea un nodo padre cuya frecuencia es la suma de los dos, y se reinserta el nodo resultante en la cola.
• Este proceso se repite hasta obtener un único nodo, que representa la raíz del árbol de Huffman.

// Ejemplo de uso del heap para construir el árbol:
static Arbol crear_huffman(int* frecuencias) {
  PQ pq = pq_create();
  // Insertar cada carácter con su frecuencia en el heap...
  // Combinar nodos hasta obtener el árbol completo.
}
      

3. Codificar y Escribir el Árbol

Una vez construido el árbol, el siguiente paso es:

• Recorrer el árbol en preorden para generar los códigos para cada carácter (0 para izquierda, 1 para derecha).
• Escribir la estructura del árbol en el archivo comprimido. Esto permite su reconstrucción durante la descompresión.
• Leer nuevamente el archivo de entrada y, utilizando una tabla de códigos (mapa de caracteres a secuencias de bits), escribir la representación codificada en el archivo de salida.

// Ejemplo de función para codificar:
static int codificar(Arbol T, char* entrada, char* salida) {
  // Escribir el árbol de Huffman en el archivo...
  // Recorrer el archivo y escribir el código correspondiente a cada carácter.
}
      

4. Crear Tabla de Códigos y Gestión del Campo de Bits

Para generar la tabla de códigos se recorre el árbol de Huffman. En cada llamada recursiva se agrega un bit (0 para el subárbol izquierdo y 1 para el derecho) al campobits acumulado. Se pueden utilizar dos enfoques:

• Copias Locales: Se crea una copia del campobits actual para cada rama. Esto permite que cada llamada recursiva tenga su propio estado, evitando modificar la variable original.

  
  campobits copia = actual;
  bits_agregar(&copia, 0);
  crear_tabla(nodo->izq, tabla, copia);
            

• Modificación In Situ con bits_remove_last: Se modifica el mismo objeto y, al regresar de la recursión, se quita el último bit para restaurar el estado.

  
  bits_agregar(&actual, 0);
  crear_tabla(nodo->izq, tabla, actual);
  bits_remove_last(&actual);
            

¿Qué hace bits_remove_last?

Esta función elimina el último bit del campobits decrementando el contador de tamano y limpiando el bit correspondiente mediante una máscara. Esto es especialmente útil en recorridos recursivos donde se necesita retroceder el estado del código.

/**
 * Función: bits_remove_last
 *
 * Descripción:
 *   Elimina el último bit añadido al campo de bits, reduciendo 'tamano' en uno
 *   y limpiando esa posición en 'bits->bits' mediante una máscara.
 *
 * Funcionamiento:
 *   1. Se decrementa 'bits->tamano' en 1.
 *   2. Se crea una máscara: ~(0x1 << bits->tamano) para poner a 0 el bit eliminado.
 *   3. Se actualiza 'bits->bits' aplicando la operación AND con la máscara.
 */
static int bits_remove_last(campobits* bits) {
    if (!bits || bits->tamano <= 0){
        return -1; // Error: No bits to remove
    }
    int last_bit = (bits->bits >> (bits->tamano - 1)) & 0x1;
    bits->tamano--;
    bits->bits &= ~(0x1 << bits->tamano);
    return last_bit;
}
      

Comparación:

• Copias locales: Permiten mantener cada estado independientemente, reduciendo el riesgo de errores durante el retroceso y simplificando el código recursivo.
• Modificación in situ + bits_remove_last: Evita copiar la estructura en cada llamada, pero requiere una gestión cuidadosa del estado para eliminar el bit agregado al volver de la recursión.

Resumen: Usar copias locales resulta en un código más seguro y fácil de mantener, minimizando errores en entornos recursivos. Aunque esto implica un mayor uso de memoria, el impacto es limitado: en el peor de los casos, el uso máximo será el tamaño del campobit multiplicado por la profundidad del árbol. Incluso con n nodos, esta profundidad rara vez supera los 100 niveles debido a la distribución balanceada del árbol de Huffman. Por otro lado, modificar in situ con bits_remove_last puede ahorrar memoria pero incrementa la complejidad y el riesgo de errores. La elección depende del balance entre legibilidad, seguridad y eficiencia, siendo el enfoque con copias una opción más robusta y mantenible en la práctica.

Procesos en la descompresión

La descompresión utiliza el archivo comprimido y el árbol previamente almacenado para restaurar el contenido original. El proceso involucra:

1. Lectura y Reconstrucción del Árbol

Se lee el árbol que fue escrito en el archivo comprimido:

• Se utiliza un método de lectura en preorden para reconstruir el árbol.
• Se detecta si un nodo es hoja (representado con un bit 1 y el carácter) o interno (bit 0).

// Ejemplo de función para leer el árbol:
static Arbol leer_arbol(BitStream bs) {
  // Reconstruir el árbol a partir de los bits leídos.
}
      

2. Decodificar el Archivo

Con el árbol reconstruido, se procede a decodificar la secuencia de bits:

• Se empieza desde la raíz del árbol y se lee bit a bit para navegar por él.
• Al llegar a una hoja se obtiene el carácter correspondiente, que se escribe en el archivo de salida.
• Este proceso se repite hasta que se procesen todos los bits restantes del archivo.

// Ejemplo de función para decodificar:
static void decodificar(BitStream in, BitStream out, Arbol arbol) {
  // Procesar el stream de bits y escribir el contenido decodificado.
}
      

Resumen

El algoritmo de Huffman, implementado en C, se fundamenta en:

• La identificación de la frecuencia de cada carácter.
• El uso de un heap para construir el árbol de Huffman de forma eficiente.
• La generación de una tabla de códigos para la compresión y la posterior reconstrucción para la descompresión.

Estos pasos aseguran que se logre una compresión sin pérdida, aprovechando la frecuencia de aparición de cada carácter para reducir el espacio necesario para almacenarlos.