Embed Size (px)
Citation preview
www.utel.edu.mx
UNIDAD III
INTELIGENCIA ARTIFICIAL
PIERRE SERGEI ZUPPA AZÚA
ALGORITMO DE BM
www.utel.edu.mx
Inteligencia Artificial
Algoritmo BM
Algunos Algoritmo de procesamiento de caracteres
• Trivial• Rabin-Karp• Knuth-Morris_Pratt• Boyer-Moore• Búsqueda de expresiones
regulares
www.utel.edu.mx
Inteligencia Artificial
Algoritmo BM
algoritmo de Boyer-Moore(1977)
Preprocesa la cadena objetivo (clave) 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: no necesita comprobar cada carácter de la cadena que es buscada, puesto que salta algunos de ellos.
J Strother Moore
www.utel.edu.mx
Inteligencia Artificial
Algoritmo BM
Algoritmo BMPuede encontrar todas las apariciones de un patrón P (de longitud m) en una cadena madre S (de longitud n) en un tiempo O(n) en el caso peor.
Es sublineal: no examina necesariamente todos los caracteres de S y el n° de comparaciones, a menudo, inferior a n.
En el mejor caso encuentra todas las apariciones de P en S en un tiempo O(m+n/m)
Robert S. Boyer
www.utel.edu.mx
Inteligencia Artificial
Algoritmo BM
Calculo de la tabla D1(Prefijo malo)
Patrón “OSTENTE”
Ejemplo de comprobación:S: FADFAEVASEGSOSTENTEP: OSTENTE
S: Cadena madreP: Patrón
O S T E N T E
6 5 4 3 2 1 0
E N O S T otros
D1 0 2 6 5 1 7
F A D F A E V A S E G S O S T E N T E
1 2 3 4 5 6 7 1 2 3 4 5 O S T E N T E
www.utel.edu.mx
Inteligencia Artificial
Algoritmo BM
Paso 1Patrón “OSTENTE”
Armar la tabla primera fila:
Se coloca cada ocurrencia de cada carácter del patrón en una tabla en orden alfabético.
En el ejemplo la “E” y la “T” solo se coloca una vez.
E N O S T otros
D1
www.utel.edu.mx
Inteligencia Artificial
Algoritmo BM
Paso 2Patrón “OSTENTE”
Posición de los caracteres del patrón:
Poner la posición de la primera aparición del carácter en el patrón contando desde la derecha y comenzando en 0.
O S T E N T E
6 5 4 3 2 1 0
www.utel.edu.mx
Inteligencia Artificial
Algoritmo BM
Paso 3Patrón “OSTENTE”
Rellenar la segunda fila
Se coloca la primera ocurrencia de derecha a izquierda.
Otros es el total de caracteres o tamaño del patrón.
O S T E N T E
6 5 4 3 2 1 0
E N O S T otros
D1 0 2 6 5 1 7
www.utel.edu.mx
Inteligencia Artificial
Algoritmo BM
Comprovación
Ejemplo:
S: FADFAEVASEGSOSTENTEP: OSTENTE
Se compara la última letra del patrón con la primera fila que en este caso es “V” y como no es la misma la comparamos con la tabla y como no tenemos “V” se desplaza 7 caracteres que pertenece a otros.
F A D F A E V A S E G S O S T E N T E
O S T E N T E
E N O S T otros
D1 0 2 6 5 1 7
www.utel.edu.mx
Inteligencia Artificial
Algoritmo BM
Comprobación
Ejemplo:
S: FADFAEVASEGSOSTENTEP: OSTENTE
Al recorrer 7 caracteres volvemos a comparar la última letra con la primera fila en este caso es “S” como no son iguales la buscamos con la tabla y la encontramos con 5 por lo que recorreremos 5 caracteres.
E N O S T otros
D1 0 2 6 5 1 7
F A D F A E V A S E G S O S T E N T E
1 2 3 4 5 6 7 O S T E N T E
www.utel.edu.mx
Inteligencia Artificial
Algoritmo BM
ComprobaciónEjemplo:
S: FADFAEVASEGSOSTENTEP: OSTENTE
Al recorrer 5 caracteres volvemos a comparar la última letra con la primera fila en este caso son iguales pasamos a comparar los demás caracteres hasta encontrar un fallo pero como hay termina el algoritmo.
Nota: Si se encuentra un fallo volver a comparar con la tabla.
E N O S T otros
D1 0 2 6 5 1 7
F A D F A E V A S E G S O S T E N T E
1 2 3 4 5 6 7 1 2 3 4 5 O S T E N T E
