Entrada # 2

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

Para esta entrada se nos encargo una simulación utilizando los métodos de búsqueda para palabras.

El primer método es el de Boyer-Moore.

Es un Algoritmo de búsqueda de cadenas desarrollado por Bob Boyer y J Strother Moore en 1977.

El algoritmo funciona de esta manera:

• Teniendo una frase o cadena de caracteres se pretende buscar una palabra en esta cadena.

• La palabra se pre procesada  primero invierte la palabra: si la palabra es "perro" se convierte a "orrep".

• Teniendo la palabra pre procesada se elimina el primer carácter de este.

• Después se genera una especie de patrón, el cuál contiene la palabra y las letras de la frase que no están en la palabra.

• Teniendo estos datos el proceso del algoritmo seria un ciclo repetitivo del siguiente paso hasta que se haya encontrado la palabra en la frase o ya se halla pasado por toda la frase.

• Se colocan la palabra al principio de la frase y se hace una comparación de derecha a izquierda, si el ultimo elemento de la palabra es diferente a la letra de la frase que se encuentra en la misma posición 

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.

Solo tengo un mugrero de código.

	# -*- coding: utf-8 -*-
	#Algoritmo Boyer-Moore
	from random import randint
	import sys
	def main():
	abecedario = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n','o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
	#tamano = int(raw_input("Tamaño de la Frase a generar: "))
	tamano = int(sys.argv[1])
	tamanob = int(sys.argv[2])
	frase = generarfrase(abecedario, tamano)
	print frase
	#tamanob = int(raw_input("Tamaño de la Frase a Buscar: "))
	buscar = generapalabra(abecedario, tamanob)
	print buscar
	buscaralrevez = voltear(buscar)
	buscaralrevez.pop(0) #Elimino el primer elemento
	print buscaralrevez
	patron = distibuscar(buscaralrevez, frase)
	print patron
	tamano1 = len(frase) - 1 #Tamaño de la frase generada - 1
	tamano2 = len(buscaralrevez) #Tamaño de la frase a buscar
	posicion = tamano2 - 1
	ultima = tamano2 - 1 #Para que comience a buscar con el ultimo elemento de la frase a buscar
	algoritmo(ultima, posicion, tamano1, tamano2, frase, buscaralrevez, patron)
	def generarfrase(abecedario, tamano):
	generada = []
	for i in range(tamano):
	x = randint(0, len(abecedario) - 1)
	letra = abecedario[x]
	generada.append(letra)
	return generada
	def generapalabra(abecedario, tamano):
	palabra = []
	for i in range(tamano):
	j = randint(0, len(abecedario) - 1)
	palabra.append(abecedario[j])
	return palabra
	def voltear(buscar):
	palabra = []
	limite = len(buscar)
	tamano = limite - 1
	contador = 0
	while contador < limite:
	palabra.append(buscar[tamano])
	contador = contador + 1
	tamano = tamano - 1 #Le resto uno para que tome la siguiente letra de la frase
	return palabra
	def distibuscar(busalre, frase):
	distinto = 0
	fuera = 0
	for i in busalre:
	if frase[0] != i and fuera == 0:
	busalre.append(frase[0])
	fuera = 1
	for i in frase:
	for j in busalre:
	if distinto == 1:
	#print i, j
	if i != j:
	#print "Son Distintos: "+str(i)+", "+str(j)
	distinto = 1
	else:
	#print "Son Iguales: "+str(i)+", "+str(j)
	distinto = 0
	if distinto == 1:
	busalre.append(i)
	distinto = 1
	return busalre
	def algoritmo(final, posicion, tamanof, tamanob, frase, buscar, patron):
	inicio = 0
	i = 0
	pas = 0 #Pasado
	mov = 0 #Cantidad de movimientos por busqueda
	conta = 0 #Lugar es Posicion
	while final <= tamanof:
	conta = conta + 1
	pas = inicio
	if buscar[posicion] == frase[final]:
	i = i + 1
	posicion = 0
	while inicio <= final - 1:
	i = i + 1
	if buscar[posicion] == frase[inicio]:
	print "1: "+str(buscar[posicion])
	print "2: "+str(frase[inicio])
	inicio = inicio + 1
	posicion = posicion + 1
	if inicio == final - 1:
	print "MATCH :D"
	posicion = len(buscar) - 1
	final = final + 1
	else:
	inicio = final
	posicion = len(buscar) - 1
	inicio = pas + i
	final = inicio + len(buscar) - 1
	else:
	print buscar[posicion]
	print frase[final]
	for j in range(len(patron)):
	if patron[j] == frase[final]:
	mov = j + 1
	inicio = inicio + mov
	final = final + mov
	posicion = len(buscar) - 1
	main()

view raw Tarea2.py hosted with ❤ by GitHub