Algoritmo Rabin-Karp

Neste tutorial, você aprenderá o que é o algoroitmo de rabin-karp. Além disso, você encontrará exemplos funcionais do algoritmo rabin-karp em C, C ++, Java e Python.

O algoritmo Rabin-Karp é um algoritmo usado para pesquisar / combinar padrões no texto usando uma função hash. Ao contrário do algoritmo de correspondência de string ingênuo, ele não viaja por todos os caracteres na fase inicial, em vez disso, filtra os caracteres que não correspondem e, em seguida, realiza a comparação.

Uma função hash é uma ferramenta para mapear um valor de entrada maior para um valor de saída menor. Este valor de saída é chamado de valor hash.

Como funciona o algoritmo Rabin-Karp?

Uma sequência de caracteres é obtida e verificada quanto à possibilidade da presença da string necessária. Se a possibilidade for encontrada, a correspondência de caracteres é realizada.

Vamos entender o algoritmo com as seguintes etapas:

  1. Seja o texto: Texto
    E a string a ser pesquisada no texto acima: Padrão
  2. Vamos atribuir um numerical value(v)/weightpara os caracteres que usaremos no problema. Aqui, pegamos os primeiros dez alfabetos apenas (ou seja, A a J). Pesos de Texto
  3. m é o comprimento do padrão e n é o comprimento do texto. Aqui, m = 10 and n = 3.
    seja d o número de caracteres no conjunto de entrada. Aqui, pegamos o conjunto de entrada (A, B, C, …, J). Então d = 10,. Você pode assumir qualquer valor adequado para d.
  4. Vamos calcular o valor hash do padrão. Valor hash do texto
valor hash para o padrão (p) = Σ (v * dm-1) mod 13 = ((3 * 10 2 ) + (4 * 10 1 ) + (4 * 10 0 )) mod 13 = 344 mod 13 = 6

No cálculo acima, escolha um número primo (aqui, 13) de forma que possamos realizar todos os cálculos com aritmética de precisão simples.

A razão para calcular o módulo é fornecida abaixo.

  1. Calcule o valor do hash para a janela de texto de tamanho m.
Para a primeira janela 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 o valor hash do padrão com o valor hash do texto. Se eles corresponderem, então, a correspondência de caracteres será executada.
    Nos exemplos acima, o valor hash da primeira janela (ou seja, t) corresponde a p, portanto, vá para a correspondência de caracteres entre ABC e CDD. Como eles não correspondem, vá para a próxima janela.
  2. Calculamos o valor hash da próxima janela subtraindo o primeiro termo e adicionando o próximo termo, conforme mostrado abaixo.
t = ((1 * 10 2 ) + ((2 * 10 1 ) + (3 * 10 0 )) * 10 + (3 * 10 0 )) mod 13 = 233 mod 13 = 12

Para otimizar esse processo, usamos o valor de hash anterior da seguinte maneira.

t = ((d * (t - v (caractere a ser removido) * h) + v (caractere a ser adicionado)) mod 13 = ((10 * (6 - 1 * 9) + 3) mod 13 = 12 Onde , h = d m-1 = 10 3-1 = 100.
  1. Para BCC, t = 12 ( ≠ 6). Portanto, vá para a próxima janela.
    Após algumas pesquisas, obteremos a correspondência para a janela CDA no texto. Valor de hash de janelas diferentes

Algoritmo

 n = t.length m = p.length 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 a n - m se p = ts se p (1… m) = t (s + 1… s + m) imprima "padrão encontrado na posição" s Se s <nm ts + 1 = (d ( ts - t (s + 1) h) + t (s + m + 1)) mod q

Exemplos de Python, Java e 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); )

Limitações do Algoritmo Rabin-Karp

Golpe Espúrio

Quando o valor hash do padrão corresponde ao valor hash de uma janela do texto, mas a janela não é o padrão real, é chamado de acerto espúrio.

O acerto espúrio aumenta a complexidade de tempo do algoritmo. Para minimizar o acerto espúrio, usamos o módulo. Isso reduz bastante o acerto espúrio.

Complexidade do algoritmo Rabin-Karp

O caso médio e a complexidade do melhor caso do algoritmo Rabin-Karp são O(m + n)e a complexidade do pior caso é O (mn).

A complexidade do pior caso ocorre quando ocorrências espúrias ocorrem em um número para todas as janelas.

Aplicativos de algoritmo Rabin-Karp

  • Para correspondência de padrões
  • Para pesquisar string em um texto maior

Artigos interessantes...