Rabin-Karp
El algoritmo Rabin-Karp es una técnica en la que se busca una substring dentro de una string más grande. Se puede buscar carácter a carácter, pero esto sería muy poco eficiente, ya que, dependiendo de la cadena, se podría contar el mismo carácter más de una vez.
Así, se necesita una técnica que pueda comparar toda la cadena más eficientemente. De ésta manera llegamos al algoritmo de Rabin-Karp.
Fue desarrollado por Michael Rabin y Richard Karp en 1987, y usa técnicas de Hashing para convertir cada string en un número (hash) que se puede comparar mucho más eficientemente.
Descripción del algoritmo
En realidad, éste algoritmo está diseñado originalmente para trabajar sobre un sólo patrón, pero es fácil de adaptar para múltiples patrones.
En términos generales, el algoritmo funciona de la siguiente manera:
- Calcula el hash de el o los patrones, y los guarda en un set.
- Itera sobre la cadena original, tomando substrings del mismo largo que los patrones.
- Calcula el hash de la substring.
- Si el hash está en el set de hash de los patrones, retorna el índice del inicio de la substring.
- Si no, continúa hasta que lleguemos al final de la string.
- No coincide ningún patrón, retorna no encontrado.
Implementación
Para implementar el algoritmo Rabin-Karp, es necesario tener:
- Una implementación de hashset
- Una implementación de hash para strings
La siguiente implementación está dada en Python:
def rabinkarp(cadena : str, patrones: list[str]) -> int:
n = len(cadena)
m = len(patrones[0])
hpatrones = set(hash(patron) for patron in patrones)
patrones = set(patrones)
hcadena = hash(cadena[:m])
for i in range(n-m+1):
if hcadena in hpatrones and cadena[i:i+m] in patrones:
return i
hcadena = hash(cadena[i+1])
return -1
Uso
Uso básico
En éste ejemplo, vemos el uso de la función definida más arriba, utilizando un sólo patrón. Simplemente hay que especificar una cadena y una lista de tamaño 1 con el patrón a buscar.
Uso con varios patrones
En éste ejemplo, se ve cómo utilizar la función con más de un patrón. Es importante que todos los patrones tengan la misma longitud, ya que el algoritmo asume una longitud constante.