Cadenas de Caracteres y
Emparejamiento de Patrones
•
•
•
•
Fuerza Bruta
Rabin-Karp
Knuth-Morris-Pratt
Tries
1
Búsqueda de cadenas
• El objetivo de búsqueda en cadenas es hallar la localización
de un patrón de texto específico dentro de un texto largo
(e.g., una oración, un parráfo, un libro, etc.).
• Los requisitos son velocidad y eficiencia.
• Hay un gran número de algoritmos para esto, entre los
cuales están Fuerza Bruta,Rabin-Karp, y Knuth-MorrisPratt.
2
Fuerza Bruta
• El algoritmo de Fuerza Bruta compara el patrón con el texto un
caracter cada vez, hasta encontrar que no coinciden los caracteres
3
Complejidad Fuerza Bruta
• Dado un patrón de M caracteres de longitud, y un texto de N
caracteres de longitud:
• Peor caso: compara el patrón con cada subcadena de texto de longitud
M.
• Complejidad: O(MN)
• Mejor caso: encuentra el patrón en las primeras M posiciones del
texto.
• Complejidad: O(N)
4
Rabin-Karp
• Calcula un valor hash para el patrón, y para cada subsecuencia de
M-caracteres de texto.
• Si los valores hash son diferentes, se calcula una valor para la
siguiente secuencia.
• Si los valores hash son iguales se usa una comparación de Fuerza
Bruta.
5
Ejemplo Rabin-Karp
• Valor Hash de “AAAAA” es 37
• Valor Hash de“AAAAH” es 100
6
Algoritmo Knuth-Morris-Pratt
• El algoritmo de búsqueda Knuth-Morris-Pratt (KMP) se diferencia del
método de fuerza bruta porque mantiene una pista de información obtenida
en comparaciones previas.
• Se calcula una función de fallo (f) qie indica cuanto se la última
comparación se puede reusar si existe un fallo.
•
7
Algoritmo KMP
• Complejidad: O(n + m)
8
Descargar

Emparejamiento de cadenas de caracteres