Algoritmo de Huffman

23 marzo 2007

Se trata de un algoritmo que se usa para compresión o encriptación de datos desarrollado por David A. Huffman en 1952.

Se basa en el concepto de asignar códigos de distinta longitud de bits a cada uno de los caracteres de un fichero. Si se asignan códigos más cortos a los caracteres que aparecen más a menudo se consigue una compresión de ficheros.

El algoritmo consiste en la creación de un árbol binario que tiene cada uno de los símbolos por hoja, y construido de tal forma que siguiéndolo desde la raíz a cada una de sus hojas se obtiene el código Huffman asociado.

  1. Se crean varios árboles, uno por cada uno de los símbolos del alfabeto, consistiendo cada uno de los árboles en un nodo sin hijos, y etiquetado cada uno con su símbolo asociado y su frecuencia de aparición.
  2. Se toman los dos árboles de menor frecuencia, y se unen creando un nuevo árbol. La etiqueta de la raíz será la suma de las frecuencias de las raíces de los dos árboles que se unen, y cada uno de estos árboles será un hijo del nuevo árbol. También se etiquetan las dos ramas del nuevo árbol: con un 0 la de la izquierda, y con un 1 la de la derecha.
  3. Se repite el paso 2 hasta que sólo quede un árbol.

Con este árbol se puede conocer el código asociado a un símbolo, así como obtener el símbolo asociado a un determinado código. Lo normal es pasar la asociación de código y símbolos a una tabla para trabajar con ella y desechar el árbol.

Como ejemplo vamos a aplicarlo a la cadena “tres_tristes_tigres”. Hay que tener en cuenta los espacios en blanco para codificar la cadena completa.

Primero. Asignamos la frecuencia de aparición (absoluta o relativa) a cada carácter de la cadena.

t (4) r (3) e (3) s (4) _ (2) i (2) g (1)

Segundo. Ordenamos de menor a mayor los caracteres según su frecuencia. Si se repiten las frecuencias no importa.

g (1) _ (2) i (2) r (3) e (3) t (4) s (4)

Tercero. Creamos un árbol con un único nodo por cada carácter (con su respectiva frecuencia).
Cuarto. Cogemos los 2 arboles con menos frecuencia y los unimos compartiendo un nuevo nodo raíz que contiene la suma de las frecuencias. Además etiquetamos la arista del nodo derecho con un 1 y del nodo izquierdo con un 0.
Quinto. Repetimos el paso anterior hasta que sólo quede un árbol.

Arbol binario algoritmo Huffman

Ahora recorremos las ramas desde las hojas hasta el nodo raíz apuntando las etiquetas de cada rama. El código de cada hoja será el inverso de cada una de las secuencias obtenidas. En el ejemplo, para el carácter “r” recorremos desde su hoja hasta la raíz obteniendo la secuencia 110 por lo que el código de Huffman asociado al carácter “r” es el inverso 011.

Para el resto de los caracteres tenemos la siguiente asociación:

s 10
t 11
e 001
r 011
i 010
_ 0001
g 0000

Vemos que los caracteres que más se repiten tienen códigos más cortos para que sea efectiva la compresión.

Fuente: Wikipedia y apuntes de Estructuras de Datos y Algoritmos del LSI.

:wq

12 Responses to “Algoritmo de Huffman”

  1. alidhaey Says:

    Una práctica?


  2. No, un ejercicio de clase de EDA. No conocía hasta entonces este algoritmo. El grado de compresión es muy pequeño.

    Ahora tengo que hacer un algoritmo que recorra el árbol de huffman y asigne su correspondiente código a cada símbolo.

  3. alidhaey Says:

    Me imagino entonces, que pronto saldrá la practica de la asignatura (o al menos antes la publicaban cuando llegaba semana santa/feria).


  4. Este año han sustituido la práctica del curso por un sistema de calificación por grupos en prácticas. Se divide el grupo de prácticas en subgrupos y al azar se pide a varios miembros del grupo que implementen algunos métodos de una clase en la pizarra. Mientras tus compañeros tienen que defender tu implementación hay otro subgrupo que tiene que decir posibles mejoras.

    Está curioso, a mi me pilló de imprevisto porque no pude asistir a la primera práctica y creo que te esfuerzas más que haciendo la práctica final.

  5. alidhaey Says:

    En su momento, la practica habitual, si querias sacarla, tenias que esforzarte bastente, que no era nada malo.

    PD: Si que me interesa la lista esa de ‘utilitarios’ que esta haciendo tu compañero, cuando la tenga lista que me la mande a la direccion de correo del comentario.


  6. […] 20th, 2007 Hace poco intenté explicar cómo se utiliza el algoritmo de Huffman para codificar e incluso encriptar una cadena de […]


  7. Creo que el algoritmo que pones para generar el codigo a partir del arbol binario recorre dos veces los nodos, ya que la condicion de salida es a==null y eso hace descender por los nodos left y rigth del ultimo nodo de cada rama, la condicion de salida seria (a.left==null and a.rigth==null), eso cortara el proceso recursivo justo en los ultimos nodos de la rama.

    Aqui esta funcionando ya:
    http://mmengineer.blogspot.com/2007/11/algoritmo-de-compresion-huffman-php.html
    Un saludo.

  8. ary Says:

    hola oye me podrias explicar un poco mejor a lo que se relaciona el algoritmo de huffman, lo que le entiendo es que sirve para comprimir “archivos” por asi decirlo pero aun no logro entender es como se obtiene el codigo por que he encontrado en otros sitios que los árboles se van fucionando para hacer un nuevo árbol y que asi se va consiguiendo el código espero tu respuesta pronto porfa lo necesito es urgente gracias

  9. sad Says:

    muy malo , demasiado general adonde se quiere llegar cero implementacion y definicion , muy liviano el contenido

  10. Christian Tobler Says:

    Antonio muchas gracias por el artículo, la verdad está muy entendible y me ayudó para resolver ejercicios de práctico de arquitectura de sistemas.
    Saludos desde Uruguay, Christian.

  11. Wilfredo Fernandez Says:

    Gracias por el articulo, a mi me a servido para comprender de que se trata y como funciona el arbol de Hufmann… me llama la atencion lo del comportamiento humano…

  12. maria Says:

    mira puedes ayuda explicado este algoritmo q tiene muy bn


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: