Ir al contenido principal

Tarea #2 - Métodos de acoplamiento de texto

Que tal para esta entrada se nos encargo hacer un .py que buscara un patrón en un texto e hizieramos un reporte como conclusiones.

En clase vimos temas de búsqueda de patrones mas aparte escribimos uno en clase y nos llevamos 2 de tarea el Boyer-Moore y el Morris-Pratt. Así que si mas rollo aquí esta el código.

BOYER-MOORE
Es el mejor sistema de búsqueda de patrones en un texto, lo que las comparaciones no las hace 1 por 1 este hace un brinco según... la llamaremos tabla de saltos, para ir descartando palabras en donde no se encuentre el patrón.


La tabla lo que hace es sacar los indices de cada letra del patrón empezando de izquierda a derecha, cuando alla terminado a esa lista de patrón se le agregaran todas las letras del texto que no aparezcan en en patrón e ir contando su indice, NOTA: esta lista no puede contener letras repetidas.

Supongamos que tenemos el texto "GCATCGCAGAGAGTATACAGTACG" y el patrón "GCAGAGAG" entonces la tabla de saltos quedaría de la siguiente forma:

y el pedazo de codigo en donde lo hago es este:


Una vez que tenemos la tabla de saltos lo que procede es aplicar el algoritmo... el cual me base de esta pagina



Knuth-Morris

Este es un poco mas sencillo a cuanto de programación se trata pero no es recomendable porque itera por cada letra del texto buscando el patrón. En caso de equivocarse  salta las veces que tubo que comparar haciendo muchas, pero muchas comparaciones.



Reporte 

Ahora para que quede un poco mas gráfico cual es mejor, corrimos varias veces el .py con largos deferentes de patrones y texto para ver en cuantas iteraciones tardaban en recorrer el texto.

Knuth-Morris

Boyer-Moore

En las gráficas podemos observar que el incremento de Morris es casi similar a la longitud del patrón  en cuanto a Boyer como hace brincos(por así decirlo) estratégicos este tarda casi la mitad del longitud del texto para recorrerlo todo y encontrar llaves en caso de tenerlas.

El cogido completo lo pueden encontrar en mi git.


REFERENCIAS
http://www-igm.univ-mlv.fr/~lecroq/string/node14.html
http://www-igm.univ-mlv.fr/~lecroq/string/node8.html

Comentarios

  1. Quería ver el código del experimento en la entrada, pero mínimo está en el git. 5+5.

    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