Código de Huffman
| ||||||
Códigos de Huffman,códigos utilizados para representar los caracteres mediante cadenas de bits de longitud variable como alternativa al código ASCII u otros códigos de longitud fija
Idea
La idea básica de los códigos de Huffman se basa en utilizar cadenas cortas de bits para los caracteres de uso frecuente y utilizar cadenas de bits de mayor tamaño para los caracteres que tienen una frecuencia menor de uso.
Definición
Un código de Huffman se define fácilmente mediante un árbol con raíz, como se observa en la figura de la plantilla.
Usos
Mediante la utilización del código de Huffman dado en la figura que se observa en la plantilla de este artículo, procederemos a explicar como codificar y decodificar palabras utilizando esta técnica.
Codificación
Codifiquemos la palabra STAR (Estrella). Para codificar la letra S primero tomamos a la derecha de la raíz, por lo que escribimos un cero (0), ahora tenemos que tomar la rama izquierda por lo que tendríamos que escribir un uno (01), seguimos por la rama izquierda codificando otro uno (011) y finalmente llegamos al vértice que contiene la letra S en la rama derecha de ese nodo por lo que escribimos un cero (0110) por lo que la codificación de la letra S será 0110. Procedemos con el mismo algoritmo para el resto de las letras obteniendo los siguientes códigos para cada una de ellas : T = 0111; A=1; R=010 por lo que la palabra STAR quedaría codificada como 011001111010
Decodificación
Decodifiquemos la cadena 01010111 escrita según el código huffman de la figura anterior.
El primer número (cero) nos indica que debemos movernos a la rama derecha del árbol, a continuación aparece un uno por lo que debemos movernos a la rama izquierda y luego aparece un cero por lo que nos movemos por la rama derecha llegando al nodo que representa la letra R, el siguiente numero es un uno que nos lleva por la rama izquierda directo al nodo que representa la letra A, le sigue un cero indicando que nos moveremos a la derecha, luego el uno que continua nos indica tomar la rama de la izaquierda, el siguiente uno nos mantiene moviéndonos por la rama izquierda y el ultimo uno nos lleva al nodo que representa a la letra T por lo que la palabra que se busca es RAT (rata)
Fuentes
- Johnsonbaugh, Richard. Matemáticas Discretas. Volumen II,cuarta edición.Editorial Felix Varela, La Habana, 2006. Pág 380.
- MSc. Ávila Cruz,José Ramón.Investigación Código de Huffman.JC Puerto Padre V
