Huffman

Programa en ANSI C que permite codificar y decodificar archivos utilizando el algoritmo de Huffman, que codifica cada byte según su frecuencia relativa.
Genera además los siguientes archivos de texto que permiten ver en detalle cómo ha sido el proceso:

• huffman.tab
  contiene la lista de caracteres, su frecuencia relativa y la codificación resultante para cada uno.
• huffman.cod
  muestra en detalle el proceso de codificación.
• huffman.dec
  muestra en detalle el proceso de decodificación.

Descargar código fuente

/*
    huffman.c

    Permite codificar y volver a decodificar archivos.
*/

#include <stdio.h>
#include <stdlib.h>

typedef struct
{
    unsigned char byte;
    float frecuencia;
}    Frecuencia;

typedef struct nodoHuffman
{
    unsigned char byte;     /* Sólo se utiliza en los nodos hoja */
    float frecuencia;
    unsigned char bit;
    struct nodoHuffman *padre, *izq, *der;
}    nodoHuffman;

/* Archivos globales que guardan el detalle del proceso */
FILE *archTab;
FILE *archCod;
FILE *archDec;

/* 
    Crea y retorna un nodo hoja a partir de la estructura Frecuencia
    apuntada por frec
*/
nodoHuffman *crearHoja(Frecuencia *frec)
{
    nodoHuffman *nodo =(nodoHuffman *)malloc(sizeof(nodoHuffman));

    if(nodo)
    {
        nodo->byte = frec->byte;
        nodo->frecuencia = frec->frecuencia;
        nodo->izq = nodo->der = 0;
    }
    return nodo;
}

/*
    Crea y retorna un nodo padre a partir de los nodos hijos
    apuntados por izq y der
*/
nodoHuffman *crearPadre(nodoHuffman *izq, nodoHuffman *der)
{
    nodoHuffman *padre =(nodoHuffman *)malloc(sizeof(nodoHuffman));

    if(padre)
    {
        padre->frecuencia = izq->frecuencia + der->frecuencia;
        padre->izq = izq;
        padre->der = der;
        izq->padre = der->padre = padre;
        izq->bit = 0;
        der->bit = 1;
    }

    return padre;
}

/*
    Crea un arreglo de frecuencias de bytes del archivo arch
    de tamaño tamArch en el apuntador vecFrecuencia.
    Retorna la cantidad de bytes diferentes hallados,
    que es el tamaño resultante del vector vecFrecuencia.
*/
int establecerFrecuencias(FILE *arch, long tamArch,
                          Frecuencia **vecFrecuencia)
{
    long frec[256] = { 0L }; /* Arreglo de 256 contadores de
                                ocurrencias de bytes */
    Frecuencia *vecFrec;
    int i, j, byte, cantBytes;

    /* Reubica el puntero de lectura al comienzo */
    fseek(arch, 0L, SEEK_SET);

    /* Cuenta las ocurrencias de cada byte en el archivo */
    byte = fgetc(arch);
    while(!feof(arch))
    {
        frec[byte]++;  /* Usa el valor de cada byte como índice */
        byte = fgetc(arch);
    }

    /* Cuenta en cantBytes los bytes diferentes que han aparecido en
       el archivo */
    cantBytes = 0;
    for(i = 0; i < 256; i++)
        if(frec[i]) cantBytes++;

    /* Solicita memoria dinámica para un arreglo de estructuras
       Frecuencia de cantBytes de tamaño */
    *vecFrecuencia = vecFrec =
               (Frecuencia *)malloc(sizeof(Frecuencia) * cantBytes);

    /* Si no hay memoria para el vector de frecuencias retorna -1 */
    if(!vecFrec) return -1;

    /*
        Almacena en el arreglo de frecuencias los bytes diferentes
        que han aparecido en el texto y su frecuencia relativa.
        Los elementos conservan el orden original por byte, de menor
        a mayor.
    */
    j = 0;
    for(i = 0; j < cantBytes; i++)
    {
        if(frec[i])
        {
            vecFrec[j].byte = i;
            vecFrec[j++].frecuencia =(float)frec[i] / tamArch;
        }         
    }         

    /* Retorna la cantidad de bytes diferentes que se han hallado */
    return cantBytes;
}

/*
    Genera y retorna un arreglo dinámico de apuntadores a nodos hoja
    a partir del arreglo de frecuencias vecFrec de tamaño tam
*/
nodoHuffman **armarHojas(Frecuencia *vecFrec, int tam)
{
    nodoHuffman **vecHojas;
    Frecuencia *f;  /* Apuntador auxiliar para recorrer el arreglo
                       de frecuencias */
    int i;

    /* Solicita memoria para un arreglo de apuntadores a hojas */
    /* Si no hay memoria para el vector de apuntadores
       no hace nada más y retorna un apuntador nulo */
    if((vecHojas =
               (nodoHuffman **)malloc(sizeof(nodoHuffman*) * tam)))
    {
        /*
           Crea un nodo hoja por cada frecuencia.
           Si no hay memoria para alguna de las hojas retrocede
           hasta el principio del vector liberando una a una la
           memoria de las hojas ya creadas, libera la memoria del
           propio vector y retorna un apuntador nulo
        */
        for(f = vecFrec, i = 0; i < tam; i++, f++)
        {
            if(!(vecHojas[i] = crearHoja(f)))
            {
                while(i--) free(vecHojas[i]);
                free(vecHojas);
                return 0;
            }
        }
    }

    return vecHojas;
}

/*
    Crea un arbol de Huffman a partir del arreglo de apuntadores
    a hojas vecHojas de tamaño tam.
    Retorna el nodo raíz.
*/
nodoHuffman *armarArbol(nodoHuffman **vecHojas, int tam)
{
    nodoHuffman **aux;      /* Copia del arreglo vecHojas para
                               preservar su contenido */
    nodoHuffman *raiz;      /* Apuntará a la raiz del arbol
                               luego de construirlo */
    int minIzq, minDer;     /* Índices de las dos frecuencias
                               menores detectadas en cada pasada */
    int i, x;

    /* Solicita memoria para el arreglo auxiliar */
    aux =(nodoHuffman **)malloc(sizeof(nodoHuffman*) * tam);

    /* Copia el contenido de vecHojas en aux */
    for(i = 0; i < tam; i++)
        aux[i] = vecHojas[i];

    /* Procede a construir el árbol a partir de aux
       para dejar vecHojas intacto */

    /* Comienza suponiendo que las dos primeras son las menores
       frecuencias */
    minIzq = 0;
    minDer = 1;

    /* Mientras quede más de un nodo sin agrupar
       (o sea, mientras tam sea mayor que 1) */
    while(minDer < tam)
    {
        /* Se asegura de que la FRECUENCIA de la izquierda
           sea menor que la de la derecha */
        if(aux[minIzq]->frecuencia > aux[minDer]->frecuencia)
        {
            x = minIzq;
            minIzq = minDer;
            minDer = x;
        }

        /* Examina el resto de las frecuencias a partir de la
           tercera */
        for(i = 2; i < tam; i++)
        {
            /* Si la frecuencia en i es menor que la mayor de las
               mínimas, actualiza los índices */
            if(aux[i]->frecuencia < aux[minDer]->frecuencia)
            {
                minDer = i;
                /* Se asegura de que la FRECUENCIA de la izquierda
                   sea menor que la de la derecha */
                if(aux[minIzq]->frecuencia >aux[minDer]->frecuencia)
                {
                    x = minIzq;
                    minIzq = minDer;
                    minDer = x;
                }
            }
        }

        /* Se asegura de que el INDICE de la izquierda sea menor que
           el de la derecha para hacer el reemplazo de los nodos */
        if(minIzq > minDer)
        {
            x = minIzq;
            minIzq = minDer;
            minDer = x;
        }

        /* Reemplaza la frecuencia de la izquierda por un nuevo nodo
           padre de ambas frecuencias mínimas */
        aux[minIzq] = crearPadre(aux[minIzq], aux[minDer]);
        /* Descarta la frecuencia de la derecha reemplazándola por
           la última del arreglo, a la vez que lo acorta en uno */
        aux[minDer] = aux[--tam];

        /* Recomienza suponiendo otra vez que las dos primeras son
           las menores frecuencias */
        minIzq = 0;
        minDer = 1;
    }

    /* Ha quedado un único nodo en la posición 0, que es la raíz
       del árbol */
    raiz = aux[0];
    /* La raíz no tiene padre */
    raiz->padre = 0;

    /* Libera la memoria auxiliar */
    free(aux);

    return raiz;
}

/*    Libera recursivamente la memoria ocupada por el árbol */
void liberarArbol(nodoHuffman *raiz)
{
    if(!raiz) return;

    liberarArbol(raiz->izq);
    liberarArbol(raiz->der);

    free(raiz);
}

void mostrarByte(unsigned char b)
{
    unsigned char m = 0x80;
    char bit = 8;

    fprintf(archDec, " [");
    while(bit--)
    {
        fprintf(archDec, "%d",((b & m) >> bit));
        m >>= 1;
    }
    fprintf(archDec, "] ");
}

unsigned char decodificarByte(nodoHuffman *raiz, FILE *arch)
{
    static unsigned char mascara = 0; /* máscara para examinar el
                                        byte obtenido del archivo */
    static unsigned char leido;      /* byte obtenido del archivo */
    unsigned char byte;

    do
    {
        byte = raiz->byte;        /* byte del nodo visitado */

        if(!mascara)              /* Si no hay máscara */
        {
            mascara = 0x80;       /* se prepara para examinar el
                                     primer bit de la izquierda */
            leido = fgetc(arch);  /* e intenta leer un nuevo byte
                                     del archivo */
            if(feof(arch))        /* Si no hay más bytes en el
            {                        archivo retorna 0 */
                return 0;         /* con el flag de fin de archivo
            ]                        activado */
            mostrarByte(leido);
        }

        /*
            El próximo nodo visitado será el hijo derecho o
            izquierdo del actual según que el byte leído contenga
            1 ó 0 en el bit de máscara
        */
        raiz = leido & mascara? raiz->der: raiz->izq;

        if(raiz) fprintf(archDec, "%d", raiz->bit);

        if(raiz) mascara >>= 1; /* la máscara se desplaza para
                           examinar el siguiente bit a la derecha */
    } while(raiz);              /* Repite mientras haya un hijo */

    if(byte < 0x20 || byte > 0x7E)
        fprintf(archDec, "\t%02Xh\n", byte);
    else
        fprintf(archDec, "\t'%c'\n", byte);

    return byte; /* Retorna el último byte almacenado */
}

/*
    Hace una búsqueda binaria de la hoja que contiene a byte
    en el vector de hojas vecHojas de tamaño cantBytes.
    Retorna un apuntador a la hoja correspondiente
    o un apuntador nulo si no encuentra el byte.
*/
nodoHuffman *buscarHoja(nodoHuffman *vecHojas[], int cantBytes,
                        unsigned char byte)
{
    int i = 0;
    int j = cantBytes - 1;
    int m = 0;
    unsigned char medio;

    while(i <= j)
    {
        m =(i + j) / 2;
        medio = vecHojas[m]->byte;

        if(byte <= medio) j = m - 1;
        if(byte >= medio) i = m + 1;
    }

    return(i - j) == 2? vecHojas[m]: 0;
}

/*
    Retorna el código Huffman del byte contenido en el nodo apuntado
    por hoja.
    El código retornado presenta los bits INVERTIDOS de derecha a
    izquierda y la cantidad de bits a considerar desde la derecha
    queda en el entero apuntado por tam.
    Por ejemplo, si el código retornado es (bit a bit)
    0000000000001011 y tam es 6, entonces el código real a
    considerar es 110100.
*/
unsigned int codificarByte(nodoHuffman *hoja, int *tam)
{
    unsigned int cod = 0;
    int t = 0;

    while(hoja)
    {
     /* Desplaza todo el contenido actual de cod una posición a la
        izquierda y luego pone el bit del nodo como primer bit a la
        derecha. */
        if(hoja->padre)
        {
            cod =(cod << 1) | hoja->bit;
            t++;
        }
        hoja = hoja->padre;
    }

    *tam = t;
    return cod;
}

void mostrarCodigos(nodoHuffman *vecHojas[], int cantBytes)
{
    unsigned int cod;
    int tamCod;
    int i;

    archTab = fopen("huffman.tab", "wt");
    for(i = 0; i < cantBytes; i++)
    {
        cod = codificarByte(vecHojas[i], &tamCod);

        if(vecHojas[i]->byte < 0x20 || vecHojas[i]->byte > 0x7E)            {
            fprintf(archTab, "%02Xh\t%f\t", vecHojas[i]->byte,
                                        vecHojas[i]->frecuencia);
        }
        else
        {
            fprintf(archTab, "'%c'\t%f\t", vecHojas[i]->byte,
                                        vecHojas[i]->frecuencia);
        }
 
        while(tamCod--)
        {
            fprintf(archTab, "%d", cod & 0x01);
            cod >>= 1;
        }
        fprintf(archTab, "\n");
    }
    fclose(archTab);
}

int comprimir(char nomOrig[], char nomComp[])
{
    FILE *entrada, *salida;
    Frecuencia *vecFrec;
    nodoHuffman **vecHojas;
    nodoHuffman *raizHuffman;
    long tamArch;
    int cantBytes;

    unsigned int cod;
    int tamCod;

    unsigned char byteEntrada;
    unsigned char byteSalida;
    unsigned char posBit;

    /* Intenta abrir el archivo de entrada para lectura */
    if(!(entrada = fopen(nomOrig, "rb")))
        return 1;

    /* Intenta abrir el archivo de salida para escritura */
    if(!(salida = fopen(nomComp, "wb")))
    {
        fclose(entrada);
        return 2;
    }

    /* Establece en tamArch el tamaño del archivo de entrada */
    fseek(entrada, 0L, SEEK_END);
    tamArch = ftell(entrada);

    /* Guarda en cantBytes la cantidad de bytes diferentes y en
       vecFrec sus frecuencias */
    if((cantBytes = establecerFrecuencias(entrada, tamArch,
                                          &vecFrec)) < 0)
    {
        fclose(salida);
        fclose(entrada);
        return 3;
    }

    /* Guarda en vecHojas el arreglo de apuntadores a hojas */
    if(!(vecHojas = armarHojas(vecFrec, cantBytes)))
    {
        free(vecFrec);
        fclose(salida);
        fclose(entrada);
        return 4;
    }

    /* Guarda en raizHuffman la dirección de la raíz del árbol de
       codificación */
    if(!(raizHuffman = armarArbol(vecHojas, cantBytes)))
    {
        free(vecHojas);
        free(vecFrec);
        fclose(salida);
        fclose(entrada);
        return 5;
    }

    /* Escribe en el archivo de salida el tamaño del archivo
       original, la cantidad de bytes diferentes utilizados y el
       vector de frecuencias */
    fwrite(&tamArch, sizeof(long), 1, salida);
    fwrite(&cantBytes, sizeof(int), 1, salida);
    fwrite(vecFrec, sizeof(Frecuencia), cantBytes, salida);

    /* Reestablece el puntero del archivo de entrada al comienzo */
    fseek(entrada, 0L, SEEK_SET);

    archCod = fopen("huffman.cod", "wt");

    byteSalida = 0;
    posBit = 8;

    while(tamArch--)
    {
        byteEntrada = fgetc(entrada);
        cod = codificarByte(buscarHoja(vecHojas, cantBytes,
                                             byteEntrada), &tamCod);

        if(byteEntrada < 0x20 || byteEntrada > 0x7E)
        {
            fprintf(archCod, "%02Xh\t", byteEntrada);
        }
        else
        {
            fprintf(archCod, "'%c'\t", byteEntrada);
        }

        while(tamCod--)
        {
            posBit--;
            byteSalida |=((cod & 0x01) << posBit);

            fprintf(archCod, "%d", cod & 0x01);

            if(!posBit)
            {
                posBit = 8;
                fputc(byteSalida, salida);
                byteSalida = 0;
                fprintf(archCod, "/");
            }
            cod >>= 1;
        }
        fprintf(archCod, "\n");
    }

    fclose(archCod);
    if(posBit < 8) fputc(byteSalida, salida);
    fclose(salida);
    fclose(entrada);
    mostrarCodigos(vecHojas, cantBytes);
    free(vecHojas);
    liberarArbol(raizHuffman);

    return 0;
}

int descomprimir(char nomComp[], char nomOrig[])
{
    FILE *entrada, *salida;
    Frecuencia *vecFrec;
    nodoHuffman **vecHojas;
    nodoHuffman *raizHuffman;
    long tamArch;
    int cantBytes;

    unsigned char byteSalida;

    /* Intenta abrir el archivo de entrada para lectura */
    if(!(entrada = fopen(nomComp, "rb")))
        return 1;

    /* Intenta abrir el archivo de salida para escritura */
    if(!(salida = fopen(nomOrig, "wb")))
    {
        fclose(entrada);
        return 2;
    }

    /* Lee en tamArch el tamaño del archivo de entrada */
    fread(&tamArch, sizeof(long), 1, entrada);

    /* Lee en cantBytes la cantidad de bytes diferentes */
    fread(&cantBytes, sizeof(int), 1, entrada);

    /* Lee en vecFrec el vector de frecuencias */
    if(!(vecFrec =
              (Frecuencia *)malloc(sizeof(Frecuencia) * cantBytes)))
    {
        fclose(salida);
        fclose(entrada);
        return 3;
    }

    /* Lee en vecFrec el vector de frecuencias */
    fread(vecFrec, sizeof(Frecuencia), cantBytes, entrada);

    /* Guarda en vecHojas el arreglo de apuntadores a hojas */
    if(!(vecHojas = armarHojas(vecFrec, cantBytes)))
    {
        free(vecFrec);
        fclose(salida);
        fclose(entrada);
        return 4;
    }

    /* Guarda en raizHuffman la dirección de la raíz del árbol de
       codificación */
    if(!(raizHuffman = armarArbol(vecHojas, cantBytes)))
    {
        free(vecHojas);
        free(vecFrec);
        fclose(salida);
        fclose(entrada);
        return 5;
    }

    archDec = fopen("huffman.dec", "wt");
    while(tamArch--)
    {
        byteSalida = decodificarByte(raizHuffman, entrada);
        fputc(byteSalida, salida);
    }
    fclose(archDec);
    fclose(salida);
    fclose(entrada);

    mostrarCodigos(vecHojas, cantBytes);
    liberarArbol(raizHuffman);
    free(vecHojas);
    free(vecFrec);

    return 0;
}

int main()
{
    char nomEntrada[20];
    char nomSalida[20];
    char oper;
    int ret;

    do
    {
        printf("(C)odificar o (D)ecodificar? ");
        oper = getchar() | 0x20;
    } while(oper != 'c' && oper != 'd');

    printf("\nArchivo de entrada: ");
    scanf("%s", nomEntrada);

    printf("Archivo de salida:  ");
    scanf("%s", nomSalida);

    ret = oper == 'c'?
          comprimir(nomEntrada, nomSalida):
          descomprimir(nomEntrada, nomSalida);

    switch(ret)
    {
        case 0:
            puts("\nArchivo procesado con exito\n");
            break;
        case 1:
            puts("\nArchivo de entrada no se encuentra\n");
            break;
        case 2:
            puts("\nArchivo de salida no se puede abrir\n");
            break;
        case 3:
            puts("\nSin memoria para vector de frecuencias\n");
            break;
        case 4:
            puts("\nSin memoria para nodos hoja\n");
            break;
        case 5:
            puts("\nSin memoria para el arbol\n");
    }

    system("pause");

    return 0;
}