Algoritmo de comparación
Enviado por Programa Chuletas y clasificado en Informática y Telecomunicaciones
Escrito el en 
español con un tamaño de 70,3 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 . 
. Etc.
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.