Explicación del algoritmo de Rabin-Karp

El algoritmo de Rabin-Karp es un algoritmo de búsqueda / búsqueda de cadenas desarrollado por Michael O. Rabin y Richard M. Karp. Utiliza la técnica de hash y la fuerza bruta para la comparación, y es un buen candidato para la detección de plagio.

Términos importantes

  • patrón es la cadena que se buscará. Considere la longitud del patrón como M caracteres.
  • texto es el texto completo en el que se buscará el patrón. Considere la longitud del texto como N caracteres.

¿Qué es la comparación de fuerza bruta?

En la comparación de fuerza bruta, cada carácter del patrón se compara con cada carácter del texto hasta que se encuentran los caracteres que no coinciden.

Cómo funciona el algoritmo de Rabin-Karp

  1. Calcular el valor hash del patrón
  2. Calcular el valor hash de los primeros M caracteres de texto
  3. Compare ambos valores hash
  4. Si no son iguales, calcule el valor hash para los siguientes M caracteres de texto y compare nuevamente.
  5. Si son iguales, realice una comparación de fuerza bruta.
hash_p = hash value of pattern hash_t = hash value of first M letters in body of text do if (hash_p == hash_t) brute force comparison of pattern and selected section of text hash_t= hash value of next section of text, one character over while (end of text or brute force comparison == true)

Ventaja sobre el algoritmo de coincidencia de cadenas ingenuo

Esta técnica da como resultado solo una comparación por subsecuencia de texto y la fuerza bruta solo se requiere cuando los valores hash coinciden.