Tarea 2

Tarea 2 - String matching

Hola, esta actividad consiste en realizar un programa en python sobre el tema de string matching. String matching son las coincidencias u ocurrencias de palabras (no necesariamente palabras) en una cadena de texto (no necesariamente de texto XD).

El escenario es el siguiente:

Dada una cadena de texto (T), y una cadena patrón (P), vamos a encontrar las ocurrencias presentadas. Por ejemplo:

T = (issttstsisitstsisitstttits)

P = (its)

Vamos a encontrar las veces que se hace un match, en el ejemplo anterior tendriamos 3 matches.

Los algoritmos que usaremos para la búsqueda de cadenas serán el de Boyer-Moore y el de Knuth-Morris-Pratt.

A continuación explicaré el funcionamiento del algoritmo Boyer-Moore

Boyer-Moore

El algoritmo Boyer-Moore es un algoritmo de búsqueda de cadenas desarrollado por Bob Boyer y J Strother Moore en 1977. Lo que este algoritmo hace es buscar la coincidencia del último elemento de la cadena patrón con un elemento cualquiera de una cadena de texto; por ejemplo si la cadena patrón es 'a,b,c' y la cadena de texto es 'ccbacababca', el algoritmo realiza una comparación entre c (último elemento de la cadena patrón) y la cadena de texto. En caso de que ocurra una coincidencia, ahora se comparará la penúltima posición de la cadena patrón con la ocurrencia en la cadena de texto-1. Luego si también hay concidencia se compara la antepenúltima posición de la cadena patrón con la posición de la cadena de texto-2 y así sucesivamente, lo que provoca un buen ahorro de tiempo en ejecución debido a que no tiene . En conclusión y resumidas cuentas, el algoritmo hace una verificación hacia atrás.

Yo realicé el código en python de manera sencilla, lo que hice fue iterar el recorrido de toda la cadena de texto, luego cuando enontraba match de una letra de la cadena con la última posición de la cadena patrón, tomaba una sub cadena de la cadena de texto, donde esa subcadena se compone de la letra match más las posiciones anteriores correspondientes a la cadena patrón, al final comparé la subcadena con la cadena patrón. Si la comparación arroja un "True" pues cuento un match. Y así hasta recorrer toda la cadena de texto.

A continuación el código:

import random 
from sys import argv
import string
import time

def boyer(largoM, largoN):

 #Para m = largo de texto, n = largo de patron
 archi=open('BM.dat','a') #Abro el archivo
 #largoM = int(argv[1]) 
 #largoN = int(argv[2])
 newporcent = 0.0
 M = []
 N = []
 com = []
 # Llenando listas ------------------------------------
 for i in range(largoM):
  let = random.choice(string.ascii_lowercase)
  M.append(let) #Rellenando la cadena de texto
  
 for j in range(largoN):
  let = random.choice(string.ascii_lowercase)
  N.append(let) #Rellenando el patron
 #print M
 #print N, "\n\n"

 # Algoritmo Boyer-Moore -------------------------------
 tiempoInicial = time.time()

 for x in range(largoM):
  if x >= largoN:
   if M[x] == N[-1]:
    miLargo = (x)-(largoN-1)
    com = M[miLargo:x+1]
    #print "i = ",x,  "  -  M[x] = ", M[x], " - com = ", com     
    print com
    if com == N:
     print "match: com = ", com, " - N = ", N 
     
    else:
     print "No exito :("

 tiempoFinal = time.time()
 d = tiempoFinal - tiempoInicial
 diferencia = round(d, 6) 
 
 newlargoM = str(largoM)
 newlargoN = str(largoN)   #Para poder meter los datos al dat
 newdiferencia = str(diferencia)
   
 if largoN != 10:  # Cuando el largo del patron es 9, saltamos 2 lineas en el dat
  archi.write(newlargoM) #Escribe largo de texto
  archi.write(' ')
  archi.write(newlargoN) # Escribiendo largo del patron 
  archi.write(' ')
  archi.write(newdiferencia) #Escribiendo los promedios de tiempo
  archi.write('\n')

 else:
  archi.write(newlargoM) #Lo mismo que arriba
  archi.write(' ')
  archi.write(newlargoN)
  archi.write(' ')  
  archi.write(newdiferencia)
  archi.write('\n\n')
 
 archi.close()   # Cerrando el archivo, se abre cada vez que se ejecuta esta subrutina

 
def main():
  for i in range(10): #Correr distintos tipos de largo de texto
   for j in range(10): #Correr distintos tipos de largo de patron  
    print "\nTransmitiendo con largo de texto = ", i+1, "y con patron = ", j+1      # Meramente informativo para el programador
    boyer(i+1, j+1) 
  

if __name__ == "__main__":
 main() 

Para poder graficar los tiempos hice que en un dat se fueran guardando los largos de cadena de texto y largos de cadena patrón, luego obtuve los tiempos para cada combinación. Al final realicé un plot con los datos obtenidos (como en la tarea anterior):

A continuación los datos obtenidos (en primera columna los largos de M ó largos de texto, en segunda columna los largos de N o patrón, y al final los tiempos obtenidos):

1 1 3e-06
1 2 3e-06
1 3 2e-06
1 4 3e-06
1 5 2e-06
1 6 2e-06
1 7 3e-06
1 8 2e-06
1 9 1e-06
1 10 2e-06

2 1 3e-06
2 2 2e-06
2 3 2e-06
2 4 2e-06
2 5 2e-06
2 6 2e-06
2 7 2e-06
2 8 2e-06
2 9 3e-06
2 10 2e-06

3 1 3e-06
3 2 2e-06
3 3 3e-06
3 4 2e-06
3 5 3e-06
3 6 2e-06
3 7 2e-06
3 8 3e-06
3 9 3e-06
3 10 2e-06

4 1 2e-06
4 2 2e-06
4 3 2e-06
4 4 2e-06
4 5 2e-06
4 6 3e-06
4 7 2e-06
4 8 2e-06
4 9 2e-06
4 10 2e-06

5 1 2e-06
5 2 3e-06
5 3 3e-06
5 4 2e-06
5 5 2e-06
5 6 2e-06
5 7 2e-06
5 8 2e-06
5 9 2e-06
5 10 2e-06

6 1 5.4e-05
6 2 4e-06
6 3 4.3e-05
6 4 2e-06
6 5 2e-06
6 6 2e-06
6 7 2e-06
6 8 2e-06
6 9 2e-06
6 10 2e-06

7 1 4.5e-05
7 2 2e-06
7 3 3e-06
7 4 2e-06
7 5 3e-06
7 6 2e-06
7 7 3e-06
7 8 2e-06
7 9 2e-06
7 10 1e-06

8 1 2e-06
8 2 1.8e-05
8 3 2e-06
8 4 1.8e-05
8 5 1.9e-05
8 6 1.8e-05
8 7 2e-06
8 8 1e-06
8 9 2e-06
8 10 2e-06

9 1 2e-06
9 2 2e-06
9 3 2e-06
9 4 1.9e-05
9 5 2e-06
9 6 2e-06
9 7 1e-06
9 8 2e-06
9 9 1e-06
9 10 2e-06

10 1 3e-06
10 2 2e-06
10 3 3e-06
10 4 2e-06
10 5 2e-06
10 6 2e-06
10 7 2e-06
10 8 2e-06
10 9 2e-06
10 10 2e-06


 

A continuación la gráfica obtenida:

Los resultados son tiempos bastante cortos y aceptables, donde es más tardado con largos 6 y 8 de texto y patrón respectivamente.

En la siguiente liga   se menciona más a detalle el funcionamiento de este algoritmo.

Quedo pendiente con el algoritmo Knuth-Morris-Pratt por falta de tiempo. 

Liga a mi git (se encuetra el archivo py, dat y el plot): https://github.com/eddypre/M-todosCodificaci-n

Bibliografía:

http://banyut.obolog.com/python-listas-115312
http://techerald.com/page/python-generacin-cadena-aleatoria-de-letras-maysculas-y-cifras.html

Cualquier duda o aclaración pueden dejarla en comentarios.

Saludos para todos!