Algorytm Rabina-Karpa

W tym samouczku dowiesz się, czym jest algoroithm rabina-karpa. Znajdziesz również działające przykłady algorytmu rabin-karp w językach C, C ++, Java i Python.

Algorytm Rabina-Karpa to algorytm służący do wyszukiwania / dopasowywania wzorców w tekście za pomocą funkcji skrótu. W przeciwieństwie do algorytmu dopasowywania ciągów naiwnych, nie przechodzi on przez każdy znak w początkowej fazie, a raczej filtruje znaki, które nie pasują, a następnie przeprowadza porównanie.

Funkcja skrótu to narzędzie do mapowania większej wartości wejściowej na mniejszą wartość wyjściową. Ta wartość wyjściowa jest nazywana wartością skrótu.

Jak działa algorytm Rabina-Karpa?

Pobierany jest ciąg znaków i sprawdzany pod kątem możliwości występowania wymaganego ciągu. Jeśli taka możliwość zostanie znaleziona, wykonywane jest dopasowywanie znaków.

Rozumiemy algorytm, wykonując następujące kroki:

  1. Niech tekst będzie: Tekst
    A ciągiem do wyszukania w powyższym tekście będzie: Wzorzec
  2. Przypiszmy numerical value(v)/weightznakom, których będziemy używać w zadaniu . Tutaj wzięliśmy tylko pierwsze dziesięć alfabetów (tj. Od A do J). Waga tekstu
  3. m jest długością wzoru, an jest długością tekstu. Tutaj, m = 10 and n = 3.
    niech d będzie liczbą znaków w zestawie wejściowym. Tutaj wzięliśmy zestaw wejściowy (A, B, C,…, J). Więc d = 10. Możesz przyjąć dowolną odpowiednią wartość dla d.
  4. Obliczmy wartość skrótu wzoru. Wartość skrótu tekstu
wartość skrótu dla wzorca (p) = Σ (v * dm-1) mod 13 = ((3 * 10 2 ) + (4 * 10 1 ) + (4 * 10 0 )) mod 13 = 344 mod 13 = 6

W powyższym obliczeniu wybierz liczbę pierwszą (tutaj 13) w taki sposób, aby wszystkie obliczenia wykonać arytmetyką pojedynczej precyzji.

Powód obliczenia modułu podano poniżej.

  1. Oblicz wartość skrótu dla okna tekstowego o rozmiarze m.
Dla pierwszego okna ABC wartość skrótu dla tekstu (t) = Σ (v * dn-1) mod 13 = ((1 * 10 2 ) + (2 * 10 1 ) + (3 * 10 0 )) mod 13 = 123 mod 13 = 6
  1. Porównaj wartość skrótu wzorca z wartością skrótu tekstu. Jeśli pasują, następuje dopasowywanie znaków.
    W powyższych przykładach wartość skrótu pierwszego okna (tj. T) pasuje do p, więc przejdź do dopasowania znaków między ABC i CDD. Ponieważ tak nie jest, przejdź do następnego okna.
  2. Obliczamy wartość skrótu następnego okna, odejmując pierwszy termin i dodając następny termin, jak pokazano poniżej.
t = ((1 * 10 2 ) + ((2 * 10 1 ) + (3 * 10 0 )) * 10 + (3 * 10 0 )) mod 13 = 233 mod 13 = 12

Aby zoptymalizować ten proces, wykorzystujemy poprzednią wartość skrótu w następujący sposób.

t = ((d * (t - v (znak do usunięcia) * h) + v (znak do dodania)) mod 13 = ((10 * (6-1 * 9) + 3) mod 13 = 12 Gdzie , h = d m-1 = 10 3-1 = 100.
  1. Dla BCC t = 12 ( ≠ 6). Dlatego przejdź do następnego okna.
    Po kilku poszukiwaniach otrzymamy w tekście dopasowanie do okna CDA. Wartość skrótu różnych okien

Algorytm

 n = t.length m = p.length h = dm-1 mod qp = 0 t0 = 0 dla i = 1 do mp = (dp + p (i)) mod q t0 = (dt0 + t (i)) mod q dla s = 0 do n - m jeśli p = ts jeśli p (1… m) = t (s + 1… s + m) print "wzorzec znaleziony w pozycji" s Jeśli s <nm ts + 1 = (d ( ts - t (s + 1) h) + t (s + m + 1)) mod q

Przykłady w Pythonie, Javie i 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); )

Ograniczenia algorytmu Rabina-Karpa

Fałszywe trafienie

Kiedy wartość skrótu wzorca pasuje do wartości skrótu okna tekstu, ale okno nie jest faktycznym wzorcem, wówczas nazywa się to fałszywym trafieniem.

Fałszywe trafienie zwiększa złożoność czasową algorytmu. Aby zminimalizować fałszywe trafienie, używamy modułu. Znacznie redukuje fałszywe trafienie.

Złożoność algorytmu Rabina-Karpa

Średnia i najlepsza złożoność przypadku algorytmu Rabina-Karpa wynosi, O(m + n)a najgorsza złożoność przypadku wynosi O (mn).

W najgorszym przypadku złożoność występuje, gdy fałszywe trafienia występują w wielu oknach.

Zastosowania algorytmu Rabina-Karpa

  • Do dopasowania wzorców
  • Do wyszukiwania ciągów w większym tekście

Interesujące artykuły...