« Detectadas sustancias tóxicas en varios alimentos de la Unión Europea

Portada

23 septiembre 2006

Algoritmo de Huffman

El algoritmo de Huffman se usa para la compresión o encriptación de datos mediante el estudio de la frecuencia de aparición de caracteres. Fue desarrollado por el norteamericano David Albert Huffman en 1952 mientras hacía el doctorado en el MIT. El método fue publicado en una revista como A Method for the Construction of Minimum-Redundancy Codes (el artículo original). El algoritmo funciona a partir de un conjunto dado de símbolos con sus respectivos pesos. Los pesos son la frecuencia de aparición en una cadena. Por ejemplo en la cadena Genciencia el peso del símbolo i es 2, ya que aparece en dos ocasiones. La salida del algoritmo es el mismo conjunto de símbolos de entrada codificado mediante un código binario con un tamaño menor. La descripción matemática del algoritmo de Huffman es la siguiente:

Entrada

Conjunto de Símbolos:

Pesos asociados:

Donde n es la cantidad de símbolos diferentes que existe en la cadena de entrada. Así pues los pesos asociados a los símbolos pertenecientes al conjunto A se encuentran en un rango comprendido entre 1 y n (entendiendo que la entrada no va a ser una cadena vacía), es decir:

Rango de pesos

Salida

Conjunto de código binarios:

Meta

Conseguir que el peso de C sea menor que el de A:

El algoritmo se basa en el uso de un árbol binario dónde las hojas representan los símbolos del conjunto de entrada. Para conseguir el código de Huffman asociado a cada símbolo únicamente hay que seguir las aristas que unen la raíz con la hoja determinada. Vamos a comprimir la cadena de ejemplo: pablito clavo un clavito.

Primero calculamos los pesos de los símbolos (¡ojo!, los espacios en blanco también cuentan) y los disponemos siguiente una ordenación ascendente por frecuencia

p(1)->b(1)->u(1)->n(1)->i(2)->t(2)->c(2)->v(2)->’ ’(3)->a(3)->l(3)->o(3)

En el paso anterior obtenemos n árboles. Ahora fusionamos los dos primeros árboles sumando sus frecuencias y volviendo a ordenar

Seguimos agrupando pares de árboles hasta obtener solamente uno. La raíz del árbol resultante debe de ser la suma de los pesos

Ahora a partir de nuestro árbol obtendremos la codificación de Huffman para nuestra cadena. La regla que hay que seguir es la siguiente: Cuando nos encontremos en un nodo las ramas a la izquierda valen ceros y a la derecha valen unos. Para nuestra cadena las correspondencias quedarían de la siguiente manera:

Traducimos la cadena de entrada con nuestras correspondencias y agrupamos en grupos de 8 bits (bytes) la cadena binaria resultante

En la cadena resultante se ha reducido la cantidad de bytes respecto a la cadena original que tenía 24 bytes. Cabe decir que también hay que almacenar información de la codificación, pues para descomprimir los datos hay que conocer las correspondencias ya que es relativo. Por esta razón para ficheros de poco tamaño la compresión no es muy grande, aunque esta afirmación es muy relativa, ya que el porcentaje de compresión depende de la entrada.

Más noticias sobre: Matemáticas, Programación
Comentarios (9) | Trackback

Comentarios

Perdona que te corrija :)

Algo no me encaja. ¿Cómo traduzco (por ejemplo) el primer 11000111?

Posibilidades:

aa--aaa
po
ac-oa

etcetera

Algo está mal en tu explicación del algoritmo

#1 | Escrito por Zifra | 24 sep 2006 00:14:01

Buenas Zifra. En el último párrafo puse que hay que almacenar las correspondencias para la descodificación, y posiblemente almacene la longitudes de separacion de la cadena binaria resultante (yo la he puesto agrupada en 8 para poder ver mejor la cantidad de bytes).

Un saludo!

#2 | Escrito por Alfonso Jiménez | 24 sep 2006 16:38:24

Algo está mal en tu explicación. Zifra tiene razón.

Revísalo.

#3 | Niiko | 25 sep 2006 00:18:55

Algoritmo de Huffman

#4 | Escrito por meneame.net | 25 sep 2006 02:08:24

Creo que se te han olvidado tener en cuenta los ceros iniciales del lado izquierdo del arbol:

' ' - 000
a - 001
l - 010
o - 011

#5 | Miry | 25 sep 2006 02:45:51

El problema estaba en el último paso. Gracias Miry por el reporte.

Un saludo!

#6 | Escrito por Alfonso Jiménez | 25 sep 2006 14:32:54

"y posiblemente almacene la longitudes de separacion de la cadena binaria resultante"

"Posiblemente" no es un argumento para una explicación :-)

De hecho, no la almacena. Simplemente tu explicación está mal.

El ejemplo está ahora bien, porque se cumple la norma obligatoria para poder decodificar. Pero sigues sin explicar cuál es esa norma y porqué se obtiene.

Disculpa la pesadez

#7 | Escrito por Zifra | 30 sep 2006 10:59:17

Buenas Zifra. Con decir "tu explicación está mal" no ayudas en nada. Yo la verdad es que lo veo claro. Se usan 0's y 1's para poder "moverse" por el árbol, tal como se indica 0:izquierda y 1:derecha.

Un saludo!

#8 | Escrito por Alfonso Jiménez | 30 sep 2006 13:53:38

por favor quiciera que me ayudaran a hacer un programa para la compresión de señales electrocardiograficas,por medio de la tecnica de codificación de huffman, soy estudiante de ing. biomedica, les estaria muy agradecido con su ayuda

#9 | Luis Alejandro Díaz | 24 nov 2006 06:26:01

¡Añade tu comentario!