Algoritmo de Rabin-Karp

En este tutorial, aprenderá qué es el algoroitmo de rabin-karp. Además, encontrará ejemplos prácticos del algoritmo rabin-karp en C, C ++, Java y Python.

El algoritmo de Rabin-Karp es un algoritmo que se utiliza para buscar / hacer coincidir patrones en el texto mediante una función hash. A diferencia del algoritmo de coincidencia de cadenas ingenuo, no recorre todos los caracteres en la fase inicial, sino que filtra los caracteres que no coinciden y luego realiza la comparación.

Una función hash es una herramienta para asignar un valor de entrada más grande a un valor de salida más pequeño. Este valor de salida se llama valor hash.

¿Cómo funciona el algoritmo de Rabin-Karp?

Se toma una secuencia de caracteres y se verifica la posibilidad de la presencia de la cadena requerida. Si se encuentra la posibilidad, se realiza la coincidencia de caracteres.

Entendamos el algoritmo con los siguientes pasos:

  1. Deje que el texto sea: Texto
    Y la cadena a buscar en el texto anterior sea: Patrón
  2. Asignemos una numerical value(v)/weightpara los caracteres que usaremos en el problema. Aquí, hemos tomado solo los primeros diez alfabetos (es decir, de la A a la J). Pesos de texto
  3. m es la longitud del patrón yn la longitud del texto. Aquí, m = 10 and n = 3.
    sea ​​d el número de caracteres en el conjunto de entrada. Aquí, hemos tomado el conjunto de entrada (A, B, C,…, J). Por lo tanto, d = 10. Puede asumir cualquier valor adecuado para d.
  4. Calculemos el valor hash del patrón. Valor hash del texto
valor hash para el patrón (p) = Σ (v * dm-1) mod 13 = ((3 * 10 2 ) + (4 * 10 1 ) + (4 * 10 0 )) mod 13 = 344 mod 13 = 6

En el cálculo anterior, elija un número primo (aquí, 13) de tal manera que podamos realizar todos los cálculos con aritmética de precisión simple.

La razón para calcular el módulo se da a continuación.

  1. Calcule el valor hash para la ventana de texto de tamaño m.
Para la primera ventana ABC, valor hash para texto (t) = Σ (v * dn-1) mod 13 = ((1 * 10 2 ) + (2 * 10 1 ) + (3 * 10 0 )) mod 13 = 123 mod 13 = 6
  1. Compare el valor hash del patrón con el valor hash del texto. Si coinciden, se realiza la coincidencia de caracteres.
    En los ejemplos anteriores, el valor hash de la primera ventana (es decir, t) coincide con p, así que busque la coincidencia de caracteres entre ABC y CDD. Como no coinciden, ve a la siguiente ventana.
  2. Calculamos el valor hash de la siguiente ventana restando el primer término y agregando el siguiente término como se muestra a continuación.
t = ((1 * 10 2 ) + ((2 * 10 1 ) + (3 * 10 0 )) * 10 + (3 * 10 0 )) mod 13 = 233 mod 13 = 12

Para optimizar este proceso, utilizamos el valor hash anterior de la siguiente manera.

t = ((d * (t - v (carácter que se eliminará) * h) + v (carácter que se agregará)) mod 13 = ((10 * (6 - 1 * 9) + 3) mod 13 = 12 Donde , h = d m-1 = 10 3-1 = 100.
  1. Para BCC, t = 12 ( ≠ 6). Por lo tanto, vaya a la siguiente ventana.
    Después de algunas búsquedas, obtendremos la coincidencia de la ventana CDA en el texto. Valor hash de diferentes ventanas

Algoritmo

 n = t.longitud m = p.longitud h = dm-1 mod qp = 0 t0 = 0 para i = 1 a mp = (dp + p (i)) mod q t0 = (dt0 + t (i)) mod q para s = 0 an - m si p = ts si p (1… m) = t (s + 1… s + m) imprima "patrón encontrado en la posición" s Si s <nm ts + 1 = (d ( ts - t (s + 1) h) + t (s + m + 1)) mod q

Ejemplos de Python, Java y C / C ++

Python Java C C ++ 
 # Rabin-Karp algorithm in python d = 10 def search(pattern, text, q): m = len(pattern) n = len(text) p = 0 t = 0 h = 1 i = 0 j = 0 for i in range(m-1): h = (h*d) % q # Calculate hash value for pattern and text for i in range(m): p = (d*p + ord(pattern(i))) % q t = (d*t + ord(text(i))) % q # Find the match for i in range(n-m+1): if p == t: for j in range(m): if text(i+j) != pattern(j): break j += 1 if j == m: print("Pattern is found at position: " + str(i+1)) if i < n-m: t = (d*(t-ord(text(i))*h) + ord(text(i+m))) % q if t < 0: t = t+q text = "ABCCDDAEFG" pattern = "CDD" q = 13 search(pattern, text, q)
 // Rabin-Karp algorithm in Java public class RabinKarp ( public final static int d = 10; static void search(String pattern, String txt, int q) ( int m = pattern.length(); int n = txt.length(); int i, j; int p = 0; int t = 0; int h = 1; for (i = 0; i < m - 1; i++) h = (h * d) % q; // Calculate hash value for pattern and text for (i = 0; i < m; i++) ( p = (d * p + pattern.charAt(i)) % q; t = (d * t + txt.charAt(i)) % q; ) // Find the match for (i = 0; i <= n - m; i++) ( if (p == t) ( for (j = 0; j < m; j++) ( if (txt.charAt(i + j) != pattern.charAt(j)) break; ) if (j == m) System.out.println("Pattern is found at position: " + (i + 1)); ) if (i < n - m) ( t = (d * (t - txt.charAt(i) * h) + txt.charAt(i + m)) % q; if (t < 0) t = (t + q); ) ) ) public static void main(String() args) ( String txt = "ABCCDDAEFG"; String pattern = "CDD"; int q = 13; search(pattern, txt, q); ) )
 // Rabin-Karp algorithm in C #include #include #define d 10 void rabinKarp(char pattern(), char text(), int q) ( int m = strlen(pattern); int n = strlen(text); int i, j; int p = 0; int t = 0; int h = 1; for (i = 0; i < m - 1; i++) h = (h * d) % q; // Calculate hash value for pattern and text for (i = 0; i < m; i++) ( p = (d * p + pattern(i)) % q; t = (d * t + text(i)) % q; ) // Find the match for (i = 0; i <= n - m; i++) ( if (p == t) ( for (j = 0; j < m; j++) ( if (text(i + j) != pattern(j)) break; ) if (j == m) printf("Pattern is found at position: %d ", i + 1); ) if (i < n - m) ( t = (d * (t - text(i) * h) + text(i + m)) % q; if (t < 0) t = (t + q); ) ) ) int main() ( char text() = "ABCCDDAEFG"; char pattern() = "CDD"; int q = 13; rabinKarp(pattern, text, q); )
 // Rabin-Karp algorithm in C++ #include #include using namespace std; #define d 10 void rabinKarp(char pattern(), char text(), int q) ( int m = strlen(pattern); int n = strlen(text); int i, j; int p = 0; int t = 0; int h = 1; for (i = 0; i < m - 1; i++) h = (h * d) % q; // Calculate hash value for pattern and text for (i = 0; i < m; i++) ( p = (d * p + pattern(i)) % q; t = (d * t + text(i)) % q; ) // Find the match for (i = 0; i <= n - m; i++) ( if (p == t) ( for (j = 0; j < m; j++) ( if (text(i + j) != pattern(j)) break; ) if (j == m) cout << "Pattern is found at position: " << i + 1 << endl; ) if (i < n - m) ( t = (d * (t - text(i) * h) + text(i + m)) % q; if (t < 0) t = (t + q); ) ) ) int main() ( char text() = "ABCCDDAEFG"; char pattern() = "CDD"; int q = 13; rabinKarp(pattern, text, q); )

Limitaciones del algoritmo de Rabin-Karp

Golpe espurio

Cuando el valor hash del patrón coincide con el valor hash de una ventana del texto, pero la ventana no es el patrón real, se denomina acierto falso.

El acierto espurio aumenta la complejidad temporal del algoritmo. Para minimizar el impacto espurio, usamos módulo. Reduce en gran medida el golpe falso.

Complejidad del algoritmo de Rabin-Karp

El caso promedio y la complejidad del mejor caso del algoritmo de Rabin-Karp es O(m + n)y la complejidad del peor caso es O (mn).

La complejidad del peor de los casos ocurre cuando se producen aciertos falsos en un número para todas las ventanas.

Aplicaciones del algoritmo Rabin-Karp

  • Para combinar patrones
  • Para buscar cadenas en un texto más grande

Articulos interesantes...