Ir al contenido principal

Tarea#3 - Codificación Huffman python

Que tal para esta entrada se nos encargo implementar el código Huffman en "x" lenguaje yo escogí python. A continuación una breve explicación y

Un poco de teoria:

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 carácter 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".
El algoritmo de construcción del árbol puede resumirse así:
  1. Crear un nodo hoja para cada símbolo, asociando un peso según su frecuencia de aparición e insertarlo en la lista ordenada ascendentemente.
  2. Mientras haya mas de un nodo en la lista:
    1. Eliminar los dos nodos con menor probabilidad de la lista
    2. Crear un nuevo nodo interno que enlace a los nodos anteriores, asignándole como peso la suma de los pesos de los nodos hijos.
    3. Insertar el nuevo nodo en la lista, (en el lugar que le corresponda según el peso).
  3. El nodo que quede es el nodo raíz del árbol.






Imagen y texto tomados de: http://es.wikipedia.org/wiki/Codificaci%C3%B3n_Huffman

Implementación

Como podemos observar en la imagen, se tiene una lista con las letras únicas del mensaje y sus repeticiones en el mensaje y siempre están ordenada de menor a mayor.

Es importante recalcar que cuando se unen dos nodos(siempre son los dos mas chicos) ellos crean un nuevo nodo llamado dos y con valor 0||1. El valor depende de la posición en la lista en la que están ordenados. y este nuevo nodo se agrega a la lista y repetiremos los mismos pasos hasta que el nuevo  nodo ya no tenga con quien unirse.


Una vez que estén unidos, tenemos que obtener sus códigos... el cual es el valor binario que se forma desde el nodo inicio hasta el nodo final e ir guardando el valor de la arista por donde pasa.


Una ves teniendo los códigos de las letras, únicamente tenemos que recorrer la cadena original, e ir reemplazando por los códigos obtenidos anteriormente.

Para descomprimir se hace los mismo que comprimir pera al revés, empiezas con el nodo final y el objetivo es llegar a un nodo tipo string, siempre guiándote por la cadena binaria.


Captura de pantalla




El mejor de los casos...

...es cuando tengas un mensaje de tamaño "n" pero la mayoría de las letras son iguales. Esto porque el árbol no hace tanta iteraciones para llegar a entontrar el código de la palabra que mas se repite.


El peor de los casos...

Es cuando el mensaje cuenta con una longitud "x" pero la mayoría de sus letras son muy diferentes y no se repiten tanto. Esto porque tiene que recorrer muchos nodos antes de llegar al nodo inicial.




Comentarios

  1. El análisis en el reporte debería ser más estadístico; ahora es más bien a base de ejemplos. Van 7+6 pts.

    ResponderEliminar

Publicar un comentario

Entradas populares de este blog

Pequeño Juego con LEDS y Dip Switch

Siguiendo con los mini-proyectos, lo que quería hacer originalmente era un tipo "candado" con push-button y LEDs, el objetivo seria, meter la combinacion de botones correcta y los LEDS encendería por un motivo practico, en forma de serpiente. El objetivo no cambio, pero por falta de "material" lo hice con un dip switch de X entradas(depende de que tan grande quieras la combinación). CONOCIMIENTOS(max. 7 estrellas): Electronica:     ★ ★ Programación: ★ ★ Juego de Combinación + LEDs El programa es un poco mas complicado que el mini-proyecto pasado , pero aun asi es basico. Guardamos las salidas de los LEDs en un arreglo, despues con los valores recibidos y comparados de los dip switch jugamos con los LEDś. Hardware Requerido (1) Arduino Uno (6) LED (8) Resistencias 330 Ω (1) Dip Switch Circuito Usamos las salidas del ARduino 2-7 para los LEDS Usamos la salida A5, A4 para el dip switch Para hacer prender los LEDS tienes que encontrar la

Tarea #5 - Codigo Hamming - Python

Codigo hamming Liga al repo Teoria segun wikipedia Antes de los códigos Hamming se utilizaron ciertos códigos detectores de error, como lo fueron el código linteing, pero ninguno llegó a ser tan eficaz como los de Hamming. A continuación se describen algunos de estos códigos. Paridad   La   paridad   consiste en añadir un bit, denominado   bit de paridad , que indique si el número de los bits de valor 1 en los datos precedentes es par o impar. Si un solo bit cambiara por error en la transmisión, el mensaje cambiará de paridad y el error se puede detectar (nótese que el bit donde se produzca el error puede ser el mismo bit de paridad). La convención más común es que un valor de paridad   1   indica que hay un número impar de unos en los datos, y un valor de paridad de   0   indica que hay un número par de unos en los datos. info. completa y un vídeo que me ayudo mucho para esta tarea: (TIENEN QUE VERLO - OBLIGATORIO) http://www.youtube.com/watch?v=xiDPFm9PeLU Impleme

Potenciometro + pushboton + led

Bueno, estos días he estado practicando con los ejemplos de la pagina de Arduino , algunos que me llamaron la atención los voy a compartir, por supuesto con modificaciones. Nivel de conocimientos: Electronica:        ★   Programació n :    ★    Potenciometro + push-boton = LEDintensidad El mini-proyecto es controlar la intensidad de un LED mediante un potenciometro el cual combinado con push-botton para prenderlo o apagarlo. Hardware Requerido (1) Arduino UNO (1) Potenciometro (1) Push-boton (1) LED (1) Resistencia 330 Ω Circuito Conectamos el LED al PIN 9 del Arduino Conectamos el PUSH_BOTON al PIN ANOLOGICO 0 (A0) Conectamos el POTENCIOMETRO al PIN ANOLOGICO 1 (A1) El funcionamiento del circuito es basico, mientras tengas pulsado el Push-Boton el LED se mantendrá encendido y con el pontenciometro controlas la intensidad del LED. Código Video