Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

huffman

matematicas discretas
by

augusto jesus cruz sarmiento

on 16 April 2010

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of huffman

codigo de huffman
En ciencias de la computación y teoría de la información, la codificación Huffman es un algoritmo usado para compresión de datos. El término se refiere al uso de una tabla de códigos de longitud variable para codificar un determinado símbolo (como puede ser un caracter en un archivo), donde la tabla ha sido rellenada de una manera específica basándose en la probabilidad estimada de aparición de cada posible valor de dicho símbolo. Fue desarrollado por David A. Huffman mientras era estudiante de doctorado en el MIT, y publicado en "A Method for the Construction of Minimum-Redundancy Codes".




HISTORIA
En 1951, a David Huffman y sus compañeros de clase de la asignatura “Teoría de la Información” se les permitió optar entre la realización de un examen final o la presentación de un trabajo. El profesor Robert. M. Fano asignó las condiciones del trabajo bajo la premisa de encontrar el código binario más eficiente. Huffman, ante la imposibilidad de demostrar qué código era más eficiente, se rindió y empezó a estudiar para el examen final. Mientras estaba en este proceso vino a su mente la idea de usar árboles binarios de frecuencia ordenada y rápidamente probó que éste era el método más eficiente.

Con este estudio, Huffman superó a su profesor, quien había trabajado con el inventor de la teoría de la información Claude Shannon con el fin de desarrollar un código similar. Huffman solucionó la mayor parte de los errores en el algoritmo de codificación Shannon-Fano. La solución se basaba en el proceso de construir el árbol de abajo a arriba en vez de al contrario.


TECNICA BASICA
La técnica utilizada es el propio algoritmo de Huffman. Consiste en la creación de un árbol binario en el que se etiquetan los nodos hoja con los caracteres, junto a sus frecuencias, y de forma consecutiva se van uniendo cada pareja de nodos que menos frecuencia sumen, pasando a crear un nuevo nodo intermedio etiquetado con dicha suma. Se procede a realizar esta acción hasta que no quedan nodos hoja por unir a ningún nodo superior , y se ha formado el árbol binario PROPIRDADES PRINSIPALES
Las probabilidades usadas pueden ser genéricas para el dominio de la aplicación, que están basadas en el caso promedio, o pueden ser las frecuencias reales encontradas en el texto que se está comprimiendo. (Esta variación requiere que la tabla de frecuencias u otra estructura utilizada para la codificación deben ser almacenadas con el texto comprimido; las implementaciones emplean varios mecanismos para almacenar tablas de manera eficiente).

La codificación Huffman es óptima cuando la probabilidad de cada símbolo de entrada es una potencia negativa de dos. Los códigos prefijos tienden a ser ligeramente ineficientes en alfabetos pequeños, donde las probabilidades normalmente se encuentran entre esos puntos óptimos.
VARIASIONES
Existen muchas variaciones del código de Huffman, algunos que utilizan Huffman como algoritmo, y otros que encuentra el código prefijo óptimo. Tenga en cuenta que en este último caso el método no es necesariamente similar al de Huffmans y no tiene por qué terminar en tiempo polinómico CODIGO HUFFMAN N -ARIO
El algoritmo n-ario de Huffman usa el alfabeto {0,1,….,n-1} para codificar el mensaje y construir un árbol n-ario. Este enfoque fue considerado por Huffman en su enfoque originario
CODIGO UFMAN ADAPTABLE
La variación llamada código de huffman adaptable calcula dinámicamente la probabilidad de la frecuencia de la cadena de origen basada en antiguas apariciones. Está relacionado con la familia de algoritmos LZ.

CODIGO HUFFMAN DE PLATILLA
La mayoría de las veces, el tamaño de las implementaciones del código de Huffman están representadas por probabilidades numéricas, pero el algoritmo no lo exige; se requiere solo una manera de ordenar el tamaño y añadirle. El algoritmo de plantilla de Huffman permite utilizar cualquier tipo de tamaño (costos, frecuencias, los pares del tamaño, tamaños no numéricos) y uno de los muchos que combina métodos (no solo la adición). Tales algoritmos pueden resolver problemas de minimización, como la minimización de Max[ Wi + C (i)], un problema que se aplicó por primera vez en el diseño de circuitos.


CODIGO HUFFMAN DE TAMAÑO LIMITADO

El Codigo de Huffman de tamaño de limitado es una variante donde el objetivo es lograr que el camino de coste mínimo con la restricción de que la longitud de cada palabra sea menor que una constante. El algoritmo de package-merge lo soluciona con un algoritmo voraz, muy similar al usado por el algoritmo de Huffman. Su complejidad es del orden de O (nL), siendo L el tamaño de la palabra más larga. No se conoce algoritmo para resolver este problema en tiempo lineal, a diferencia de los problemas convencionales de Huffman
CODIGO DE HUFMAN CON COSTES DESIGUALES
En el problema estándar de la codificación Huffman, se asume que cada símbolo del alfabeto con el que se construye cada palabra del código tiene igual costo de transmisión: una palabra del código cuya longitud sea N dígitos siempre tendrá un costo de N, sin importar cuántos de esos dígitos sean ceros, cuántos unos, etc. Cuando se trabaja bajo esta suposición, minimizar el costo total del mensaje y minimizar el número total de dígitos es lo mismo.


ALGORITMO DE HUFFMAN
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.

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.
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.
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.

Para obtener el código asociado a un símbolo se debe proceder del siguiente modo:

Comenzar con un código vacío
Iniciar el recorrido del árbol en la hoja asociada al símbolo
Comenzar un recorrido del árbol hacia arriba
Cada vez que se suba un nivel, añadir al código la etiqueta de la rama que se ha recorrido
Tras llegar a la raíz, invertir el código
El resultado es el código Huffman deseado
Para obtener un símbolo a partir de un código se debe hacer así:

Comenzar el recorrido del árbol en la raíz de éste
Extraer el primer símbolo del código a descodificar
Descender por la rama etiquetada con ese símbolo
Volver al paso 2 hasta que se llegue a una hoja, que será el símbolo asociado al código
En la práctica, casi siempre se utiliza el árbol para obtener todos los códigos de una sola vez; luego se guardan en tablas y se descarta el árbol.


Full transcript