PROYECTO #2

Hola mi nombre es Gustavo Adolfo Salas Coronado estoy en la clase de los jueves de v1-v3 y esta es mi investigacion.



Codigos de Huffman

Los códigos de Huffman son una técnica muy útil para comprimir ficheros.
El algoritmo voraz de Huffman utiliza una tabla de frecuencias de aparición de cada carácter para construir una forma óptima de representar los caracteres con códigos binarios.

Ejemplos:

Se tiene un fichero con 100.000 caracteres que se desea compactar. Las frecuencias de aparición de caracteres en el fichero son las siguientes:


Puede usarse un código de longitud fija (de 3 bits). El fichero requeriría 300.000 bits.


Puede hacerse mejor con un código de longitud variable, dando codificaciones cortas a los caracteres más frecuentes y más largas a los menos frecuentes.Este código ahorra algo más del 25% (requiere 224.000 bits en lugar de 300.000).


Se precisa un código libre de prefijos:
–Ninguna codificación puede ser prefijo de otra.
–De esta forma, la decodificación es inmediata pues no hay ambigüedades.
–Por ejemplo: „001011101‟ sólo puede ser „aabe‟.

El código se representa mediante un trie(árbol lexicográfico):
–árbol binario cuyas hojas son los caracteres codificados;
–el código de cada carácter es el camino desde la raíz hasta la hoja, donde ir al hijo izquierdo significa 0 e ir hacia el derecho significa 1.

Ejemplo: árboles de los dos códigos anteriores.



–Cada hoja está etiquetada con un carácter y su frecuencia.
–Cada nodo interno está etiquetado con la suma de los pesos de las hojas de su subárbol.
–Un código óptimo siempre está representado por un árbol lleno:cada nodo interno tiene dos hijos.
Si el alfabeto que se quiere codificar es C, entonces el árbol del código óptimo tiene |C| hojas y |C|-1 nodos internos.

• El algoritmo voraz de Huffman construye el árbol Ade un código óptimo de abajo hacia arriba.
• Utiliza una cola Q de árboles con prioridades (las frecuencias hacen de prioridades).
• Empieza con un conjunto de |C| hojas en Q y realiza una secuencia de |C|-1 “mezclas” hasta crear el árbol final.
• En cada paso, se “mezclan” los dos objetos (árboles) de Q que tienen menos frecuencia y el resultado es un nuevo objeto (árbol) cuya frecuencia es la suma de las frecuencias de los dos objetos mezclados.

Y aqui el algoritmo:

Inicio
{Pre: C es el conjunto de caracteres y f es el
vector de frecuencias}
funciónHuffman(C:conjunto;f:vectFrec)
devuelveárbol
variablesQ:colaPri; i,fx,fy,fz:entero;
z,x,y:árbol
principio
creaVacía(Q);
para todox en C hacer
inserta(Q,)
fpara;
parai:=1 hasta|C|-1 hacer
:=primero(Q); borra(Q);
:=primero(Q); borra(Q);
fz:=fx+fy;
z:=creaÁrbol(raíz=>fz,
hijoIzq=>x;
hijoDer=>y);
inserta(Q,)
fpara;
:=primero(Q); borra(Q)
devuelvez
fin
{nota: z es el árbol de un código libre de
prefijos óptimo para (C,f)}

Para el ejemplo anterior esta lo siguiente:




Esto es un problema np ya que muestra diferentes soluciones.


Bueno pues eso es todo mi investigacion la sake de un archivo pdf que lo podran encontrar en el siguiente link http://www.slideshare.net/mejiaff/varios-algoritmos-voraces-de-decisin-y-optimizacin.

Me despido gracias por visitar mi blog