Código de Huffman

20 abril 2007

Hace poco intenté explicar cómo se utiliza el algoritmo de Huffman para codificar e incluso encriptar una cadena de caracteres.

Llegamos a un punto en el que tenemos un árbol de Huffman y tenemos que recorrerlo para obtener la codificación asociada a cada carácter.

Arbol binario algoritmo Huffman

Esto es precisamente lo que se nos pide en clase: realizar un algoritmo que recibe un árbol binario de Huffman y devuelve dos listas, una con los caracteres y otra con las cadenas que representan el código que se le asigna al carácter. Carácter y código en las listas están relacionadas por la posición que ocupan.

Mi solución en pseudo-código sería la siguiente:

alg codigoHuffman
var
	lcar: Lista de Cadena 	// Lista de caracteres
	lcod: Lista de Cadena 	// Lista de codigos asociados a los caracteres
	a: BinaryTree		// Arbol binario de Huffman
	aux: Cadena		// Cadena auxiliar para ir almacenando los codigos
prin
	recorridoArbolHuffman (a, aux, lcar, lcod) 	//Funcion recursiva
fin

proc recorridoArbolHuffman (a: BinaryTree, aux: Cadena, ent/sal lcar, lcod: Lista de Cadena)
var
	numcar: Entero		// Número de caracteres que tiene el árbol
alg
	si a.isLeaf():		// Caso base
		numcar:= numcar + 1
		lcar.add(numcar, a.getRoot())
		lcod.add(numcar, aux)
	| otras:
		recorridoArbolHuffman( a.Left(), aux.addCaracter("0"), lcar, lcod )
		aux.removeLast()	// Borramos el último elemento de la cadena auxiliar
		recorridoArbolHuffman( a.Right(), aux.addCaracter("1"), lcar, lcod )
		aux.removeLast()
	fsi
fin

Se trata del ejercicio 3 del boletín de árboles de EDA.

:wq

6 Responses to “Código de Huffman”

  1. isabel Says:

    un ejemplo de codigo de huffman en uso cotidiano

  2. isabel Says:

    un ejemplo de codigo de huffman en el uso cotidiano

  3. Manuel Says:

    Hola, Interesante.

    Tendrías mas información sobre la codificación de Huffman. Teoría y Aplicaciones?

    Saludos Cordiales.
    Manuel.


  4. Yo no, pero la wikipedia tiene mucha información al respecto:

    Codificación de Huffman

  5. Sole Says:

    Gracias por la información. También me interesa como MAnuel los fundamentos teóricos y las aplicaciones del código de huffman, si alguien consiguió esta info me la podría pasar??? Millones de gracias solepaolina@gmail.com


Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: