Algoritmo de Huffman

En esta entrada lo que se buscó fue la implementación del algoritmo de Huffman que básicamente consiste en comprimir cadenas.

Algoritmo de Huffman:
Dejo un video donde nos explican sencillamente como se hace éste algoritmo


Implementación:
Para su implementación se desarrollo en python y lo buscado fue que el programa te generara una cadena aleatoria, esta cadena es guardada en binaria, a la cadena creada aplicamos el algoritmo de huffman, y esta es guardada en binario, teniendo éstos dos nos servirá para hacer una pequeña demostración de lo obtenido.

Generar Cadena, obtenemos las veces las veces que se repiten y Ordenamos la lista

Obtenemos las llaves por así decirlo (uniones o enlaces) que se tienen de los nodos

Comprimimos la cadena original y generamos el archivo binario

Descomprimimos la cadena comprimida para obtener la original

Generamos gráfo de nuestra llaves, la cual se empleo la librería networkx, donde me base de éste código

Main

Experimento

Las salidas que podemos ver en mi experimento fue la longitud del tamaño de la cadena original comparando con la cadena binaria y su llave.

Obteniendo como resultado, que si se tiene una diferencia de la longitud de las cadenas siendo mucho más pequeña cuando se aplica el algoritmo de Huffman y en el ejemplo mencionado podemos ver que ocupa solo el 29.8% porciento del la longitud de la cadena original, asi que podemos decir que se redujo hasta un 70% el mensaje.

También se crearon dos archivos el primero que contiene la cadena original y el segundo que es un archivo binario, com se puede ver el tamaño de éstos tiene una gran diferencia, que en archivo con la cadena es de 37KB y en el archivo binario de 5KB.

También podemos ver como éstan enlazados los nodos de las llaves obtenidas y cuales son los nodos con mayor peso.

Notas:
Debo de mencionar un agradecimiento a un compañero de clase por ayudarme en el desarrollo del programa, dejo el link del blog.

Referencias:
https://www.udacity.com/wiki/creating_network_graphs_with_python
http://es.wikipedia.org/wiki/Codificaci%C3%B3n_Huffman
http://stackoverflow.com/questions/10804659/python-dictionary-count
http://wiki.python.org/moin/HowTo/Sorting/
http://www.youtube.com/watch?v=8Gf8wutvS1w

Tarea 2: String Matching

Para esta entrada, lo que se buscó fue hacer una simulación empleando métodos de búsquedas por palabras y representarlas con gnuplot para ver como se comportaban en torno a su tiempo.

Los métodos más comunes de búsqueda por palabra son:

• Knuth Morris Pratt
• Boyer Moore

Boyer Moore

Boyer moore consiste en realizar un escaneo de derecha a izquiera, moverse en dirección hacia la izquierda hasta que se produsca un error, si el primer elemento a comparar es errónea se realiza un salto respecto a su tabla de salto, de lo contrario al pasar el primer elemento de izquierda a derecha, esta se cambia y se continua de derecha a izquierda empezando con el último elemento del patrón, éste algoritmo es considerado como uno de los más eficaces para búsquedas de palabras

[http://es.wikipedia.org/wiki/Algoritmo_de_b%C3%BAsqueda_de_cadenas_Boyer-Moore]

Knuth Morris Pratt
Este algoritmo trata de localizar la posición de comienzo de un string dentro de otra. Obteniendo antes una tabla de fallos que sirve para hacer saltos entre el string cuando se encuentra un fallo. A continuación se explica la forma en la que se trabaja con éste método

"Supongamos una tabla 'F' ya precalculada, y supongamos que la cadena a buscar esté contenida en el array 'P()', y la cadena donde buscamos esté contenida en un array 'T()'. Entonces ambas cadenas comienzan a compararse usando un puntero de avance para la cadena a buscar, si ocurre un fallo en vez de volver a la posición siguiente a la primera coincidencia, se salta hacia donde sobre la tabla, indica el puntero actual de avance de la tabla. El array 'T' utiliza un puntero de avance absoluto que considera donde se compara el primer carácter de ambas cadenas, y utiliza como un puntero relativo (sumado al absoluto) el que utiliza para su recorrido el array 'P'."

Para poder realizar éste método se baso en el psudocódigo que proporciona wikipedia, en la cual, lo contiene lo anterior mencionado.

[http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm]

[http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm]

Código
Para tener la simulación al principio lo que se hizo fueron unas pruebas donde se tenían el texto y el paterno que había preestablecido, pero para tener diferentes resultados se hizo una función donde que se generaba palabras aleatorias dependiendo de un tamaño dado del paterno y del texto. Para así correrlo en un bash donde se metería en un bucle para generar diferentes resultados.

br />

Bash

Resultados:

Una vez generados los archivos lo que se hizo fue plotearlo con gnuplot obteniendo los siguientes resultados:

Donde podemos comentar que con el metodo de naive su tiempo va creciendo al depender de las cantidades de palabras que contenga el texto y el paterno a diferencia con el método Knuth Morris Pratt que se va comportando igual y resaltando que la cantidad de éxitos es mayor cuando el paterno su tamaño es pequeño.

Referencias:

http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

http://www-igm.univ-mlv.fr/~lecroq/string/examples/exp14.html

http://es.wikipedia.org/wiki/Algoritmo_de_b%C3%BAsqueda_de_cadenas_Boyer-Moore

Tarea 1: Flujo de Información

Para esta entrada, se nos pidió simular como es el flujo de la información generando una cierta cantidad de palabras con longitud dada y su contenido son caracteres binarios aleatorios, una vez obtenido se crea otra palabra a partir de la primera dada y dependiendo de la probabilidad de ruido que se haya pedido en determinado carácter es obtendrá la nueva palabra y se crean otras dependiendo del número de iteraciones. Tener las dos palabras con el número de intentos nos servirá para comparar el totales de éxitos que se obtuvo al transmitir la palabra.

Para tener más datos congruentes y tener una buena simulación, hay que realizar la prueba con diferentes valores tanto la longitud de la palabra, la probabilidad de salir uno y cero, la frecuencia de ésta y las iteraciones de la nueva palabra.

Esto se puede lograr, ya sea haciendolo todo en python estableciendo los parámetros y metiéndolos en un archivo ó tener un bash aparte donde mandaremos llamar nuestro archivo en python y lo meteremos en varios bucles, para que nos de sus diferentes resultados y finalmente graficarlos.

Código:
Programa en python donde generamos la frecuencia de las palabras:


Bash que llama nuestro programa en python para correrlo varias veces:


Programa en gnuplot para graficar los resultados obtenidos

Resultados:
Los resultados de como salió nuestra simulación podemos verlos en la siguiente imagen, donde x es el valor de las veces que se corrió el programa y y es la cantidad de éxitos que se obtuvieron.

Archivos generados:

Plot:

**Nota, la imagen en sí no es muy congruente, así que crearé otro plot donde se tome la probabilidad de unos, ceros y la frecuencia que se obtiene.

Referencia:
http://elisa.dyndns-web.com/~elisa/teaching/comp/info/channel.pdf