Búsqueda de Cadenas

Teoría de la Información y Métodos de Codificación
Tarea 2

Boyer-Moore

Es un eficiente algoritmo de búsqueda de cadenas, y ha sido el punto de referencia estándar para la literatura de búsqueda de cadenas. Fue desarrollado por Bob Boyer y J. Strother Moore en 1977. El algoritmo preprocesa la cadena objetivo que está siendo buscada, pero no en la cadena en que se busca. El tiempo de ejecución del algoritmo Boyer-Moore, aunque es lineal en el tamaño de la cadena siendo buscada, puede tener un factor significativamente más bajo que muchos otros algoritmos de búsqueda ya que no necesita comprobar cada carácter de la cadena que es buscada, puesto que salta algunos de ellos. Generalmente el algoritmo es más rápido cuanto más grande es la clave que es buscada, usa la información conseguida desde un intento para descartar tantas posiciones del texto como sean posibles en donde la cadena no coincida. [1]

Knuth-Morris-Pratt

Es un algoritmo de búsqueda de cadenas simple y por lo tanto su objetivo es buscar la existencia de una subcadena dentro de una cadena. Para ello utiliza información basada en los fallos previos, aprovechando la información que la propia palabra a buscar contiene de sí, para determinar donde podría darse la siguiente existencia, sin necesidad de analizar más de 1 vez los caracteres de la cadena donde se busca. El algoritmo originalmente fue elaborado por Donald Knuth y Vaughan Pratt y de modo independiente por James H. Morris en 1977, pero lo publicaron juntos los tres. [2]

Código

En el siguiente código pueden encontrar los tres algoritmos más conocidos para la búsqueda de cadenas, que son Naive, Boyer-Moore (BM) y Knuth-Morris-Pratt (KMP).

El programa recibe como parámetros el largo del patrón y el largo del texto, ya que he incluido también un generador para ello.

	import sys, time, random
	def naive(pattern, text):
	# Used variables:
	# m - length of the pattern
	# n - length of the text
	matches_positions = list()
	counter = 0
	m = len(pattern)
	n = len(text)
	start = time.time()
	for i in range(n - m + 1):
	section = ''
	for j in range(m):
	section += text[i+j]
	counter += 1
	if section == pattern:
	matches_positions.append(i)
	end = time.time()
	runtime = end - start
	return matches_positions, runtime, counter
	def boyer_moore(pattern, text):
	# Used variables:
	# m - length of the pattern
	# n - length of the text
	# k - first position of the character to compare
	# i - current position of the pattern
	# h - current position of the text
	bad_character = bad_character_rule(pattern, text)
	matches_positions = list()
	counter = 0
	m = len(pattern)
	n = len(text)
	k = m
	start = time.time()
	while k <= n:
	i = m
	h = k
	while i > 0 and pattern[i-1] == text[h-1]:
	counter += 1
	i -= 1
	h -= 1
	if i == 0:
	matches_positions.append(k - m)
	k += 1
	else:
	k += bad_character[text[h-1]]
	end = time.time()
	runtime = end - start
	return matches_positions, runtime, counter
	def bad_character_rule(pattern, text):
	m = len(pattern)
	n = len(text)
	bad_character = {}
	for i in range(n - 1):
	if text[i] not in pattern:
	bad_character[text[i]] = m
	for i in range(m - 1):
	bad_character[pattern[i]] = m - 1 - i
	return bad_character
	def knuth_morris_pratt(pattern, text):
	# Used variables:
	# m - length of the pattern
	# n - length of the text
	# p - current position of the pattern
	# c - current position of the text
	table = kmp_table(pattern)
	matches_positions = list()
	counter = 0
	m = len(pattern)
	n = len(text)
	p = 0
	c = 0
	start = time.time()
	while p + c < n:
	if pattern[p] == text[c + p]:
	counter += 1
	if p == m - 1:
	matches_positions.append(c)
	c += 1
	p = 0
	else:
	p += 1
	else:
	c = c + p - table[p]
	if table[p] > -1:
	p = table[p]
	else:
	p = 0
	end = time.time()
	runtime = end - start
	return matches_positions, runtime, counter
	def kmp_table(pattern):
	table = list()
	m = len(pattern)
	for i in range(m):
	table.append(0)
	table[0] = -1
	table[1] = 0
	position = 2
	candidate = 0
	while position < m:
	if pattern[position-1] == pattern[candidate]:
	candidate += 1
	table[position] = candidate
	position += 1
	elif candidate > 0:
	candidate = table[candidate]
	else:
	table[position] = 0
	position += 1
	return table
	def instance_generator(pattern_len, text_len):
	letters_set = map(chr, range(97, 123))
	random.shuffle(letters_set)
	letters_subset = letters_set[:5]
	pattern = ''
	text = ''
	length = 0
	for i in range(pattern_len):
	pattern += letters_subset[int(random.uniform(0, 5))]
	while length < text_len:
	if random.random() < 0.2 and length < (text_len - pattern_len):
	text += pattern
	length += pattern_len
	else:
	text += letters_subset[int(random.uniform(0, 5))]
	length += 1
	return pattern, text
	def main():
	pattern, text = instance_generator(int(sys.argv[1]), int(sys.argv[2]))
	print pattern, text
	matches_positions, runtime, counter = naive(pattern, text)
	print 'naive', matches_positions, runtime, counter
	matches_positions, runtime, counter = boyer_moore(pattern, text)
	print 'bm ', matches_positions, runtime, counter
	matches_positions, runtime, counter = knuth_morris_pratt(pattern, text)
	print 'kmp ', matches_positions, runtime, counter
	if __name__ == '__main__':
	main()

view raw string_matching.py hosted with ❤ by GitHub

Análisis

Analíticamente se sabe que el algoritmo Boyer-More tiene en promedio un tiempo de ejecución de $$O(n \log(m/n))$$ en el mejor caso, pero en el peor caso se llega a tener $$O(m*n)$$ en cambio para el algoritmo Knuth-Morris-Pratt se tiene $$O(n + m)$$ lo que significa que es muy rápido.

En seguida las gráficas para los dos algoritmos donde el color de cada rectángulo es el tiempo promedio para encontrar los patrones de largo mencionado en el eje x, en un texto de largo mencionado en el eje y.

BM

KMP

Según interpreto los resultados, el algoritmo BM parece ser más rápido en tiempo de ejecución ya que mientras más tiende a ser oscuro el color, indica que el tiempo fue mucho menor.

Ahora veamos las gráficas para la cantidad de comparaciones hechas por cada algoritmo, esto lo hice ya que es evidente que el tiempo de ejecución no solo depende del algoritmo usado, sino que también esta involucrado el sistema operativo, y una forma más práctica de conocer su eficiencia, es contando la cantidad de comparaciones que se hace dentro del algoritmo.

BM

KMP

Aquí también podemos notar que BM realizó menos comparaciones que el KMP.

En conclusión podríamos decir que BM es ligeramente mejor que que KMP, y digo ligeramente por que a comparación con el algoritmo Naive, estos dos no tienen resultados muy distantes.

Por último para hablar de los algoritmos en términos de uso de memoria, tanto BM como KMP usan un arreglo de tamaño del largo del patrón, para almacenar los saltos debidos, y también los arreglos de tamaño n y m, donde n es el largo del texto, y m el largo del patrón, por lo que concluyo que en cuanto a memoria, los dos algoritmos prácticamente usan lo mismo.

Referencias:
[1] Knuth-Morris-Pratt
[2] Boyer-Moore
Boyer-Moore Exact Pattern Match
Algoritmo Boyer-Moore