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

codigos de huffman

matematicas discretas
by

ivan moctezuma

on 21 April 2010

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of codigos de huffman

codigos de huffman Es un método general de codificación y compresión diseñado para minimizar el número medio de bits necesarios para transmitir un símbolo cuando se debe transmitir varias copias independientes y estadísticamente equivalentes de dicho símbolo. Este método determina cómo los distintos valores del símbolo deben representarse como cadenas binarias.

Supongamos que tenemos que enviar el símbolo X que puede tomar valores {x1,...xn} con probabilidad {p1,...,pn}. La idea es reservar palabras cortas para los valores más frecuentes de X. Este método no requiere usar ningún tipo de separador entre los valores.

Ejemplo: x1 (0.5) x2 (0.3) x3 (0.15) x4 (0.05)

Si se usan 00, 01, 10 y 11 necesitaremos siempre 2 bits para el valor de X.
Si se usan las palabras 0,10,110,111 necesitaremos como término medio 1.7 bits (menos de 2).
El código del ejemplo es de longitud variable, pero no se requiere usar ningún tipo de separador entre los valores.

x3 x1 x4 x3 x3 x2 = 110011111011010 Sólo puede decodificarse correctamente.
La razón es que siempre puede reconocer el final de una palabra porque ninguna otra palabra es el principio de otra dada. Un código con esta propiedad se denomina código prefijo. El código Huffman es el código prefijo que requiere el mínimo número medio de bits por símbolo.
Para derivar el código Huffman se hacen las siguientes operaciones:

Escoger los dos símbolos xi, xj con probabilidad más pequeña.
Se las reemplaza por yi0 e yi1.
Se borra xi y xj de la lista y se añade yi con probabilidad pi+pj.
Volver al paso 1 hasta terminar con todos los símbolos.




El código queda definido por el camino desde C a cada nodo. La convención para escribir el código de Huffman final es:
En 1952, David Huffman propuso un método estadístico que permitía asignar un código binario a los diversos símbolos a comprimir (píxeles o caracteres, por ejemplo). La longitud de cada código no es idéntica para todos los símbolos: se asignan códigos cortos a los símbolos utilizados con más frecuencia (los que aparecen más a menudo), mientras que los símbolos menos frecuentes reciben códigos binarios más largos. La expresión Código de Longitud Variable (VLC) se utiliza para indicar este tipo de código porque ningún código es el prefijo de otro. De este modo, la sucesión final de códigos con longitudes variables será en promedio más pequeña que la obtenida con códigos de longitudes constantes.

El codificador Huffman crea una estructura arbórea ordenada con todos los símbolos y la frecuencia con que aparecen. Las ramas se construyen en forma recursiva comenzando con los símbolos menos frecuentes.
La construcción del árbol se realiza ordenando en primer lugar los símbolos según la frecuencia de aparición. Los dos símbolos con menor frecuencia de aparición se eliminan sucesivamente de la lista y se conectan a un nodo cuyo peso es igual a la suma de la frecuencia de los dos símbolos. El símbolo con menor peso es asignado a la rama 1, el otro a la rama 0 y así sucesivamente, considerando cada nodo formado como un símbolo nuevo, hasta que se obtiene un nodo principal llamado raíz.
El código de cada símbolo corresponde a la sucesión de códigos en el camino, comenzando desde este carácter hasta la raíz. De esta manera, cuanto más dentro del árbol esté el símbolo, más largo será el código.

Analicemos la siguiente oración: "COMMENT_CA_MARCHE". Las siguientes son las frecuencias de aparición de las letras:


M A C E _ H O N T R
3 2 2 2 2 1 1 1 1 1
Éste es el árbol correspondiente:








Los códigos correspondientes a cada carácter son tales que los códigos para los caracteres más frecuentes son cortos y los correspondientes a los símbolos menos frecuentes son largos:


M A C E _ H O N T R
00 100 110 010 011 1110 1111 1010 10110 10111

Las compresiones basadas en este tipo de código producen buenas proporciones de compresión, en particular, para las imágenes monocromáticas (faxes, por ejemplo). Se utiliza especialmente en las recomendaciones T4 y T5 utilizadas en ITU-T


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.

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

Código 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.

Código Huffman 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.

Algoritmo de Huffman de plantilla

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.

Código de 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.

Full transcript