Optimización de Algoritmos de Búsqueda: Boyer-Moore y Rabin-Karp
Clasificado en Informática
Escrito el en 
español con un tamaño de 71,28 KB
Cogemos el resto. Ejemplo: Tenemos una tabla de tamaño
Sondeo. Inserción. Clave
y
y
. Probamos con
Ejemplo: Para resolver colisiones se utiliza el método de doble dispersión, el primero es aritmética modular y el segundo el método de la multiplicación. Encontrar los elementos con las claves
en una tabla de tamaño
Algoritmo de Boyer-Moore
El desplazamiento
depende del carácter en
que causa el error
y el número de coincidencias hasta el error
La función
si
.
Índice de la última aparición de
en el patrón
(empezando a numerar por la derecha). Ejemplo:
.
.
Ejemplo:
. Vamos comparando.
Comparo de derecha a izquierda, pruebo
con
. Resultan distintas y el número de coincidencias antes del error es
. Por tanto:
. Desplazo el patrón
a la derecha.
Como la
ocurre igual
. Desplazo el patrón
a la derecha.
Esta vez en el primero acierta pero en el segundo falla.
.
. Se sigue así hasta que
. Y por lo tanto habríamos encontrado la palabra o hasta que se acabe la cadena (y por tanto no lo habríamos encontrado porque no está). Ejercicio: Encontrar la función para el patrón
y dar razonadamente la evolución de dicho método para encontrar el patrón anterior en la cadena
La función
.
Como falla en la primera comparación
.
Falla en la primera comparación, luego
.
Algoritmo de Rabin-Karp
. Mezclan tablas Hash y cadenas de caracteres. Sea
y un patrón
con
. Se obtienen de la cadena
subcadenas de longitud
tal que
. Con una función hash llevamos el patrón a una imagen y cada subcadena también. Comparamos solo las cadenas
con
si
. ¿Cómo transformamos una cadena en un número? Ejemplo: Si tenemos un alfabeto de
letras
tenemos que codificar cada una de ellas en orden (
). El patrón
quedaría como
pero el valor hash es
. Ejercicio: Aplicar el método de rabin-Karp con modulo
para encontrar la cadena
en el texto
. Hay
subconjuntos consecutivos de tamaño
en la cadena de tamaño
. Son los siguientes:
Veamos donde va cada uno de ellos por hash y dónde va el patrón
.
.
. Tengo que comparar.
. Tengo que comparar.
. Comparo
con
por fuerza bruta o cualquier método de comparación. Veo que no son iguales. Comparo
con
y coincide. Lo he encontrado.