Curso C++: Codificación de Huffman

Curso C++: Codificación de Huffman

La codificación de Huffman es un algoritmo utilizado en la compresión de datos para minimizar el tamaño de los archivos. En este post, presentamos una implementación de la codificación de Huffman en C++. A continuación, se explica el código y se detallan algunos aspectos importantes para mejorar su eficiencia y facilidad de uso.

Implementación del Código en C++

#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;

const int maxsize = 100;
const int null = 0;

struct huff_node
{
    char symbol;
    int freq;
    huff_node *parent;
    char childtype;
};

typedef huff_node *ptr;
ptr node[maxsize];

void create(int k);
void print(int k);
void twosmall(ptr &p, ptr &q, int numnode);

int main()
{
    int numsymbols;
    ptr p, q, r;

    cout << "Introduce el numero de simbolos: ";
    cin >> numsymbols;

    for (int i = 0; i < numsymbols; i++)
        create(i);

    for (int j = numsymbols; j < 2 * numsymbols - 1; j++)
    {
        r = new huff_node;
        node[j] = r;
        r->parent = nullptr;
        twosmall(p, q, j);
        p->parent = r;
        q->parent = r;
        p->childtype = 'L';
        q->childtype = 'R';
        r->symbol = ' ';
        r->freq = p->freq + q->freq;
    }

    cout << endl << "Simbolo *-------* Codigo: " << endl;
    for (int k = 0; k < numsymbols; k++)
        print(k);

    return 0;
}

void create(int k)
{
    ptr t = new huff_node;
    cout << "Introduce el simbolo numero " << k + 1 << ": ";
    cin >> t->symbol;
    cout << "Introduce su frecuencia: ";
    cin >> t->freq;
    t->parent = nullptr;
    node[k] = t;
}

void print(int k)
{
    ptr t = node[k];
    vector<char> code;

    while (t->parent != nullptr)
    {
        if (t->childtype == 'L')
            code.push_back('0');
        else
            code.push_back('1');
        t = t->parent;
    }

    cout << t->symbol << " - ";
    for (auto it = code.rbegin(); it != code.rend(); ++it)
        cout << *it;
    cout << endl;
}

void twosmall(ptr &p, ptr &q, int numnodes)
{
    int min1 = INT_MAX;
    int min2 = INT_MAX;
    p = nullptr;
    q = nullptr;

    for (int i = 0; i < numnodes; i++)
    {
        if (node[i]->parent == nullptr)
        {
            if (node[i]->freq < min1)
            {
                min2 = min1;
                min1 = node[i]->freq;
                q = p;
                p = node[i];
            }
            else if (node[i]->freq < min2)
            {
                min2 = node[i]->freq;
                q = node[i];
            }
        }
    }
}

Explicación del Código

  1. Definiciones y Estructuras: Se define la estructura huff_node para representar un nodo del árbol de Huffman. Cada nodo tiene un símbolo (symbol), una frecuencia (freq), un puntero a su padre (parent) y un indicador del tipo de hijo (childtype).

  2. Función create: Esta función permite crear los nodos iniciales con el símbolo y la frecuencia proporcionada por el usuario. Almacena estos nodos en el arreglo node.

  3. Algoritmo de Huffman: En el main, se construye el árbol de Huffman. Cada vez que se seleccionan los dos nodos con las frecuencias más bajas (función twosmall), se crea un nodo padre para combinarlos.

  4. Función twosmall: Busca los dos nodos con la frecuencia más baja que no tengan un padre asignado, lo cual es esencial para construir el árbol de Huffman.

  5. Función print: Muestra el código de Huffman de cada símbolo. Para cada nodo, recorre el árbol hacia arriba hasta la raíz para determinar su representación en binario.

Mejoras Realizadas

  • Actualización de Bibliotecas: Se reemplazó la biblioteca #include <iostream.h> por #include <iostream>, eliminando también el uso de #include <conio.h> que no es necesario.

  • Uso de nullptr: Se cambió null por nullptr para una mejor compatibilidad con C++ moderno.

  • Uso de vector para el Código: Se reemplazó el arreglo char code[10] por un vector<char>, lo cual hace que el código sea más seguro y flexible.

  • Constantes Adecuadas: Se reemplazó 9999 por INT_MAX para una mejor comprensión y para seguir las mejores prácticas de C++.

Conclusión

La codificación de Huffman es una técnica poderosa para la compresión de datos. Este ejemplo en C++ nos muestra cómo implementar el árbol de Huffman y generar los códigos para cada símbolo en función de su frecuencia. Aunque este es un ejemplo básico, proporciona una buena base para entender cómo funcionan los algoritmos de compresión.

Etiquetas: , , , , , , , , ,