Introducción
El algoritmo de Huffman, también llamado código de Huffman, es un algoritmo utilizado para el cifrado de datos por medio de la frecuencia de aparición de caracteres y su clasificación en un árbol binario.
A través de la frecuencia de aparición de caracteres en determinada cadena, el algoritmo de Huffman calcula los pesos del conjunto de símbolos y los coloca en un árbol binario. El ordenamiento de los caracteres se balancea de forma que los caracteres más solicitados, son los que contienen menor cantidad de caracteres binarios.
Ejemplo del Algoritmo de Huffman
Para facilitar cómo funciona el algoritmo de Huffman vamos a proporcionar el siguiente ejemplo:
Se tiene una cadena de texto con los siguientes caracteres:
- FFCE FEEF EFED EFFF EDEF EEFE DEFE FFFF FDFF BFFC FDFF FEAE DCDE FFFF DBFF CFF
Nota: Éste texto en plano tiene una longitud 63, la cual es la cantidad de caracteres que se compone el árbol.
Conteo de caracteres
En primer lugar contamos la cantidad de caracteres de cada letra para ver la ocurrencia de cada caracter:
- Hay 32 F
- Hay 16 E
- Hay 8 D
- Hay 4 C
- Hay 2 B
- Hay 1 A
Algoritmo de Huffman – Creación del árbol binario
Como deseamos cubrir todos los caracteres con el menor número de código binario posible (es decir utilizando solo unos y ceros), procedemos a crear el árbol binario de acuerdo al algoritmo de Huffman:
- Los caracteres con mayor ocurrencia, tienen menor número binario.
- Se crea el árbol, partiendo por la longitud de la cadena de texto.
El árbol binario descrito para la cadena de texto ejemplo sería el mostrado a continuación:
Es decir, cada letra es un código instantáneo que se traduce como:
- F se traduce como 0
- E se traduce como 01
- D se traduce como 001
- C se traduce como 0001
- B se traduce como 00001
- A se traduce como 00000
Cifrado del texto
Una vez que armamos nuestro árbol binario y que tiene una correspondencia de caracteres, procedemos a codificar el texto, el cuál quedaría cifrado así:
00000101 001010 01001001 01000 01001010 0101001 00101001 0000 000100 00001000001 000100 0010000001 001000100101 0000 0010000100 000100
Decodificación del texto
Aplicamos la función inversa del algoritmo de Huffman, en donde los caracteres cifrados los regresamos a su texto plano original, utilizando una decodificación instantánea. Ésto es posible gracias al uso de un árbol binario con decodificación única, uno de los objetivos del algoritmo de Huffman:
- FFCE FEEF EFED EFFF EDEF EEFE DEFE FFFF FDFF BFFC FDFF FEAE DCDE FFFF DBFF CFF
Código en C para el Algoritmo de Huffman
A continuación vamos a mostrar un programa en lenguaje C que reciba como entrada la tabla correspondiente a la función de codificación instantánea para un algoritmo de Huffman.
Breve Descripción del Programa
El programa descrito en éste artículo es un programa sencillo y muy completo en su tipo, que consiste en un codificador-decodificador de texto que utiliza el algoritmo (o códigos) de Huffman a través de una función de decodificación.
Su función es convertir un texto a código o viceversa siempre y cuando la función de decodificación sea libre de prefijos, como sucede en el algoritmo de Huffman.
Algoritmo de Huffman en lenguaje C
A continuación mostramos el código de Huffman en lenguaje C:
Manual de Uso – Algoritmo de Huffman
Ejecución del programa: Desde la línea de comandos de Unix (MacOS) o Linux:
./huffman_bitcuco
Compilación del programa: Se utilizó el compilador gcc versión 4.9, implementado en MacOX de la siguiente forma:
gcc huffman_bitcuco.c –o huffman_bitcuco
Ambiente de trabajo
Al abrir el programa Algoritmo de Huffman se muestra la siguiente pantalla (menú de inicio):
Bienvenido al programa de decodificación para códigos instantáneos 1 Ingresar tabla de la función de codificación en forma manual 2 Ingresar tabla desde fichero 0 Salir Elija su opción:
Aquí el usuario tiene que ingresar una opción válida (1,2 o 0, 0 por defecto).
Función de Codificación
si se elige la opción 1 nos pide que ingresemos los valores de la función de codificación por teclado, el cual se ve de la siguiente forma:
Introduzca el número de caracteres a codificar (Ejemplo Alfabeto inglés 26): 26 Introduzca el caracter 1 por codificar: A Introduzca el código del caracter 1: 001
De modo que hay que ingresar cada uno de los caracteres de nuestro alfabeto con su codificación correspondiente.
Al terminar de ingresar la función de decodificación, nos manda el programa al menú completo.
Otra forma de ingresar la función de decodificación es através de la opción 2 del menú inicial, la cuál es a través de un archivo, al seleccionar ésta opción aparece la siguiente pantalla:
Introduzca el nombre de archivo con su extensión (ejemplo archivo1.txt): codigox.txt El diccionario leído es: (Nombre --> Clave) A --> 01 B --> 10 C --> 11
Como puede observarse, después de ingresar el nombre de archivo, la computadora lo lee y crea la función de decodificación, la cuál si es libre de prefijos muestra el mensaje:
Enhorabuena, el código leído sí es instantáneo (prefijos diferentes)
Por lo contrario si un prefijo depende de otro carácter muestra un mensaje de error y no guarda la función de decodificación.
Menu principal
El menú principal consta de 7 secciones como las que se muestran aquí: 1 Cambiar tabla de la función de codificación en forma manual 2 Cambiar tabla desde fichero 3 Decodificación de texto por teclado 4 Decodificación de texto por fichero 5 Codificación de texto por teclado 6 Codificación de texto por fichero 0 Salir Elija su opción:
La opción 1 nos permite ingresar nuevamente una función de codificación (en forma manual, como en la página anterior), la opción 2 nos permite leer de un fichero dicha función de codificación (en ambos casos al leer la función de codificación nos indica si ésta es un código instantáneo).
Función de Decodificación
En la opción 3 se ingresa un texto en código según la función de decodificación de forma manual:
Introduzca el texto a decodificar y al finalizar presione enter: 01100100 El texto decodificado es: ABAD
Si el código del texto es correcto lo decodifica, por lo contrario lo puede decodificar parcialmente o bien arrojar mensaje de error cuando el código no pertenezca a la función de decodificación ingresada; de cualquier modo si se decodificó total o parcialmente nos da la opción de guardar la decodificación en un archivo:
¿Desea guardar el texto decodificado (S/N)?: s Introduzca el nombre de archivo con su extensión (ejemplo archivo1.txt): abad.txt Archivo creado exitosamente: abad.txt
Lectura de ficheros
La opción 4 funciona similarmente a la 3, con la excepción que se carga el código desde un archivo y éste se decodifica en pantalla y si se desea se puede guardar en archivo.
La opción 5 codifica un texto a través de introducir un texto, en caso de no existir un caracter en la función de decodificación, arroja error y si existen algunos caracteres correctos, decodifica el texto parcialmente.
Si se quiere se puede guardar la decodificación en un archivo.
Introduzca el texto a codificar y al finalizar presione enter: ABAD El texto codificado es: 01100100
La opción 6 funciona similarmente a la 5, con la excepción que se carga el código desde un archivo y éste se decodifica en pantalla y si se desea se puede guardar en archivo.
Testing de la aplicación: Algoritmo de Huffman
A continuación hacemos algunas pruebas de la ejecución del software huffman_bitcuco.c.
Bienvenido al programa de decodificación para códigos instantáneos 1 Ingresar tabla de la función de codificación en forma manual 2 Ingresar tabla desde fichero 0 Salir Elija su opción: 1 Introduzca el número de caracteres a codificar (Ejemplo Alfabeto inglés 26): 3 Introduzca el caracter 1 por codificar: A Introduzca el código del caracter 1: 10 Introduzca el caracter 2 por codificar: B Introduzca el código del caracter 2: 01 Introduzca el caracter 3 por codificar: C Introduzca el código del caracter 3: 11 El diccionario elaborado es: (Nombre --> Clave) A --> 10 B --> 01 C --> 11 Enhorabuena, el código ingresado sí es instantáneo (prefijos diferentes) ¿Desea guardar el código (S/N)?: n 1 Cambiar tabla de la función de codificación en forma manual 2 Cambiar tabla desde fichero 3 Decodificación de texto por teclado 4 Decodificación de texto por fichero 5 Codificación de texto por teclado 6 Codificación de texto por fichero 0 Salir Elija su opción: 3 Introduzca el texto a decodificar y al finalizar presione enter: 11100111111001 El texto decodificado es: CABCCAB ¿Desea guardar el texto decodificado (S/N)?: n 1 Cambiar tabla de la función de codificación en forma manual 2 Cambiar tabla desde fichero 3 Decodificación de texto por teclado 4 Decodificación de texto por fichero 5 Codificación de texto por teclado 6 Codificación de texto por fichero 0 Salir Elija su opción: 2 Introduzca el nombre de archivo con su extensión (ejemplo archivo1.txt): char3bits.txt El diccionario leído es: (Nombre --> Clave) A --> 000 B --> 001 C --> 010 D --> 011 E --> 100 F --> 101 G --> 110 H --> 111 Enhorabuena, el código leído sí es instantáneo (prefijos diferentes) 1 Cambiar tabla de la función de codificación en forma manual 2 Cambiar tabla desde fichero 3 Decodificación de texto por teclado 4 Decodificación de texto por fichero 5 Codificación de texto por teclado 6 Codificación de texto por fichero 0 Salir Elija su opción: 5 Introduzca el texto a codificar y al finalizar presione enter: ACABADEHACE El texto codificado es: 000010000001000011100111000010100 ¿Desea guardar el texto codificado (S/N)?: n 1 Cambiar tabla de la función de codificación en forma manual 2 Cambiar tabla desde fichero 3 Decodificación de texto por teclado 4 Decodificación de texto por fichero 5 Codificación de texto por teclado 6 Codificación de texto por fichero 0 Salir Elija su opción: 1 Introduzca el número de caracteres a codificar (Ejemplo Alfabeto inglés 26): 2 Introduzca el caracter 1 por codificar: A Introduzca el código del caracter 1: 1 Introduzca el caracter 2 por codificar: B Introduzca el código del caracter 2: 10 El diccionario elaborado es: (Nombre --> Clave) A --> 1 B --> 10 Error, el código ingresado no es instantáneo 1 Ingresar tabla de la función de codificación en forma manual 2 Ingresar tabla desde fichero 0 Salir Elija su opción:0