jueves, 21 de febrero de 2013

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