String matching

Programa

• "Program: Implement both BM and KMP in Python"

He implementado dos algoritmos en Python para poder encontrar un patron de caracteres en una cadena.
El primero que hice es el de KMP, para comenzar a hacer este algoritmo lo primero que hay que hacer es una tabla de fallos, esta tabla consiste en no permitir que se examine T (el texto) más de una vez. Esto se puede hacer si se compara un fragmento de la cadena donde se busca con un fragmento de la cadena que se busca, y esto nos da un sitio potencial para que haya una nueva coincidencia.
Ejemplos de Textos y su tabla de fallo:

La palabra a buscar es ANA
La tabla de fallos es [-1, 0, 0]

La palabra a buscar es BCABCBABCABC
La tabla de fallos es [-1, 0, 0, 0, 1, 2, 1, 0, 1, 2, 3, 4]

Después en el algoritmo de KMP teniendo esta tabla cada ves que se examinan las cadenas entre si se usa la tabla de fallos para hacer saltos cuando se localiza un fallo.
Este es el algoritmo que implementé:

	#!/usr/bin/python
	import sys
	def kmp(P, T):
	m = 0 #salta dentro del texto y encuentra la posicion que se busca
	i = 0 #indice que recorre la palabra
	pos = 0 #es para saber cuando la palabra no existe
	l_p = len(P)#largo del patron
	l_t = len(T)#largo del texto
	if(l_t >= l_p):#tiene que ser mas grande el texto que el patron
	tabla = tabla_fallos(P)#se genera la tabla de fallos
	print "La tabla de fallos es %s" %tabla
	while((m<l_t) and (i<=l_p)):
	if(P[i] == T[m+i]):
	if(i == (l_p-1)):
	pos = pos + 1 #regresa las posiciones donde se encuentre una coincidencia
	print "esta en la posicion %s" %m
	return
	i= i+1
	else:
	m = m + i - tabla[i]
	if(i>0):
	i = tabla[i]
	if pos == 0:
	print "no se encuentra"
	else:
	"no se puede"
	def tabla_fallos(P):
	"""recibe como parametro el patron y devuelve
	una tabla que contiene los saltos que se deben
	hacer
	"""
	l_p = len(P)
	k = 0
	table = [0] * l_p
	for q in range(1, l_p):
	while P[k] != P[q] and k > 0:
	k = table[k - 1]
	if P[k] == P[q]:
	k += 1
	table[q] = k
	table.insert(0, -1)
	return table[:-1]
	def main():
	"""funcion principal
	"""
	try:
	T = sys.argv[1]
	P = sys.argv[2]
	except:
	print "No escribiste las frases"
	return
	print "El texto es %s" %T
	print "La palabra a buscar es %s" %P
	kmp(P, T)
	main()

view raw gistfile1.py hosted with ❤ by GitHub

Algunas ejecuciones:

Después implemente el algoritmo de Boyer-Moore que el objetivo es el mismo pero lo hace de manera distinta primero procesa la cadena objetivo que esta siendo buscada, generalmente este algoritmo es más rápido mientras la cadena sea más grande.
El código con comentarios:

	#!/usr/bin/python
	import sys
	def boyer_moore(P, T):
	"""funcion principal para obtener las
	correspondencias
	"""
	encontrados = []
	m = len(T)
	n = len(P)
	pre = preprocesamiento(P)
	c = 0
	while m > c + (n - 1):
	for pos_P in xrange(n-1, -1, -1):
	pos_T = c + pos_P
	x = T[pos_T]
	y = P[pos_P]
	if pos_T >= m:
	break
	if x != y:
	r = pre.get(x)
	if x not in pre:
	c = pos_T + 1
	else:
	mov = pos_T - (c + r)
	c += (mov > 0 and mov or 1)
	break
	elif pos_P == 0:
	encontrados.append(c)
	c += 1
	return encontrados
	def preprocesamiento(P):
	"""funcion de preprocesamiento
	"""
	map = { }
	l_p = len(P)
	for i in xrange(l_p-1, -1, -1):
	s = P[i]
	if s not in map:
	map[s] = i
	return map
	def main():
	try:
	T = sys.argv[1]
	P = sys.argv[2]
	except:
	print "No escribiste palabras"
	return
	print "El texto es %s" %T
	print "El patron es %s" %P
	encontrados = boyer_moore(P, T)
	if len(encontrados) > 0:
	print "Las cadenas se encuentran en %s" %encontrados
	main()

view raw gistfile1.py hosted with ❤ by GitHub

Este es un ejemplo:

• Design, document, and analyze an experiment to determine the worst-case time complexities of the two.
  

Para esta parte he creado palabras y textos de diferentes tamaños en python para poder analizar como se comporta el algoritmo, genero dos archivos uno que se llama bm.dat y otro que se llama kmp.dat, cada uno tiene en la primera columna la longitud del texto, el la segunda columna la longitud del patron y por último el tiempo de ejecución, este es el código:

	#!/usr/bin/python
	import sys
	import time
	import random
	lista = []
	for j in [0,5,10,15,20,25,30]:
	#se varia el largo de la frase
	pot = j
	texto = ""
	for s in range(pot):
	a = random.randint(0, 1)
	a = str(a)
	texto = texto + a
	for i in range(6):
	#se varia el largo del patron
	pot = 2 ** i
	patron = ""
	for m in range(pot):
	a = random.randint(0, 1)
	a = str(a)
	patron = patron + a
	lista.append([patron, texto])
	print lista
	T1 = []
	T2 = []
	for j in lista:
	total_1 = 0
	total_2 = 0
	for i in range(30):
	t1 = time.time()
	#se escriben las estadisticas
	ins = "kmp.py %s %s" %(lista[1], lista[0])
	t1 = time.time()-t1
	t2 = time.time()
	ins2 = "bm.py %s %s" %(lista[1], lista[0])
	t2 = time.time()-t2
	total_1 = total_1 + t1
	total_2 = total_1 + t2
	T1.append([len(j[1]), len(j[0]), total_1/30.0*1000])
	T2.append([len(j[1]), len(j[0]), total_2/30.0*1000])
	print T1
	print T2
	f = open("knp.dat", "a")
	m = open("bm.dat", "a")
	for i in range(len(T1)):
	f.write("%s %s %s\n" %(T1[i][0], T1[i][1], T1[i][2]))
	m.write("%s %s %s\n" %(T2[i][0], T2[i][1], T2[i][2]))
	f.close()
	m.close()

view raw gistfile1.py hosted with ❤ by GitHub

Podemos ver que el algoritmo Boyer-Moore tiene un mejor tiempo cuando las cadenas son más largas, Boyer-Moore es más rápido ya que compara las palabras de derecha a izquierda, y tan pronto como se encuentra una carta en el texto que no está presente en el patrón de búsqueda se mueve, lugares m adelante, por lo que para archivos de gran tamaño, es de esperar que muchos de estos movimientos estarían allí por lo que una gran cantidad de caracteres de texto no será accesible ni una sola vez a diferencia de KMP donde se accede a cada letra al menos una vez.

Y en número de comparaciones se ve algo así:

Podemos notar que el Boyer-Moore es más eficiente que el KMP ya que hace mucho menor número de comparaciones. El promedio del KMP es de O(n+m). El algoritmo Boyer-More cuenta con un promedio de tiempo de ejecución de O(nlog(m/n)) (en el mejor caso), en el peor caso es de O(m*n).

Para los experimientos se hicieron 30 repeticiones.

Referencias

KMP
BM