Αλγόριθμος Rabin-Karp

Σε αυτό το σεμινάριο, θα μάθετε τι είναι ο αλγόριθμος rabin-karp. Επίσης, θα βρείτε λειτουργικά παραδείγματα αλγορίθμου rabin-karp σε C, C ++, Java και Python.

Ο αλγόριθμος Rabin-Karp είναι ένας αλγόριθμος που χρησιμοποιείται για αναζήτηση / αντιστοίχιση μοτίβων στο κείμενο χρησιμοποιώντας μια συνάρτηση κατακερματισμού. Σε αντίθεση με τον αλγόριθμο αντιστοίχισης συμβολοσειρών Naive, δεν ταξιδεύει σε κάθε χαρακτήρα στην αρχική φάση, αλλά φιλτράρει τους χαρακτήρες που δεν ταιριάζουν και στη συνέχεια εκτελεί τη σύγκριση.

Η συνάρτηση κατακερματισμού είναι ένα εργαλείο για την αντιστοίχιση μιας μεγαλύτερης τιμής εισόδου σε μια μικρότερη τιμή εξόδου. Αυτή η τιμή εξόδου ονομάζεται τιμή κατακερματισμού.

Πώς λειτουργεί ο αλγόριθμος Rabin-Karp;

Λαμβάνεται και ελέγχεται μια ακολουθία χαρακτήρων για την πιθανότητα παρουσίας της απαιτούμενης συμβολοσειράς. Εάν βρεθεί τότε η πιθανότητα, πραγματοποιείται αντιστοίχιση χαρακτήρων.

Ας κατανοήσουμε τον αλγόριθμο με τα ακόλουθα βήματα:

Αφήστε το κείμενο να είναι: Κείμενο
και η συμβολοσειρά που θα αναζητηθεί στο παραπάνω κείμενο είναι: Μοτίβο
Ας αντιστοιχίσουμε ένα numerical value(v)/weightγια τους χαρακτήρες που θα χρησιμοποιήσουμε στο πρόβλημα. Εδώ, έχουμε πάρει μόνο τα πρώτα δέκα αλφάβητα (δηλαδή A έως J). Βάρη κειμένου
m είναι το μήκος του μοτίβου και n είναι το μήκος του κειμένου. Εδώ, m = 10 and n = 3.
ας είναι ο αριθμός χαρακτήρων στο σύνολο εισόδου. Εδώ, έχουμε πάρει το σύνολο εισόδου (A, B, C,…, J). Έτσι, d = 10. Μπορείτε να υποθέσετε οποιαδήποτε κατάλληλη τιμή για το d.
Ας υπολογίσουμε την τιμή κατακερματισμού του μοτίβου. Κατακερματισμένη τιμή κειμένου

τιμή κατακερματισμού για μοτίβο (p) = Σ (v * dm-1) mod 13 = ((3 * 10 ² ) + (4 * 10 ¹ ) + (4 * 10 ⁰ )) mod 13 = 344 mod 13 = 6

Στον παραπάνω υπολογισμό, επιλέξτε έναν πρώτο αριθμό (εδώ, 13) με τέτοιο τρόπο ώστε να μπορούμε να εκτελέσουμε όλους τους υπολογισμούς με αριθμητική μίας ακρίβειας.

Ο λόγος για τον υπολογισμό του συντελεστή δίνεται παρακάτω.

Υπολογίστε την τιμή κατακερματισμού για το παράθυρο κειμένου μεγέθους m.

Για το πρώτο παράθυρο ABC, τιμή κατακερματισμού για κείμενο (t) = Σ (v * dn-1) mod 13 = ((1 * 10 ² ) + (2 * 10 ¹ ) + (3 * 10 ⁰ )) mod 13 = 123 mod 13 = 6

Συγκρίνετε την τιμή κατακερματισμού του μοτίβου με την τιμή κατακερματισμού του κειμένου. Εάν ταιριάζουν τότε, πραγματοποιείται αντιστοίχιση χαρακτήρων.
Στα παραπάνω παραδείγματα, η τιμή κατακερματισμού του πρώτου παραθύρου (δηλ. T) ταιριάζει με το p έτσι, πηγαίνετε για αντιστοίχιση χαρακτήρων μεταξύ ABC και CDD. Εφόσον δεν ταιριάζουν, πηγαίνετε στο επόμενο παράθυρο.
Υπολογίζουμε την τιμή κατακερματισμού του επόμενου παραθύρου αφαιρώντας τον πρώτο όρο και προσθέτοντας τον επόμενο όρο όπως φαίνεται παρακάτω.

t = ((1 * 10 ² ) + ((2 * 10 ¹ ) + (3 * 10 ⁰ )) * 10 + (3 * 10 ⁰ )) mod 13 = 233 mod 13 = 12

Για τη βελτιστοποίηση αυτής της διαδικασίας, χρησιμοποιούμε την προηγούμενη τιμή κατακερματισμού με τον ακόλουθο τρόπο.

t = ((d * (t - v (χαρακτήρας που πρέπει να αφαιρεθεί) * h) + v (χαρακτήρας που θα προστεθεί)) mod 13 = ((10 * (6 - 1 * 9) + 3) mod 13 = 12 Όπου , h = d ^m-1 = 10 ^3-1 = 100.

Για BCC, t = 12 ( ≠ 6). Επομένως, προχωρήστε στο επόμενο παράθυρο.
Μετά από μερικές αναζητήσεις, θα λάβουμε την αντιστοίχιση για το παράθυρο CDA στο κείμενο. Κατακερματισμένη τιμή διαφορετικών παραθύρων

Αλγόριθμος

 n = t.length m = p.length h = dm-1 mod qp = 0 t0 = 0 for i = 1 to mp = (dp + p (i)) mod q t0 = (dt0 + t (i)) mod q για s = 0 έως n - m εάν p = ts εάν p (1… m) = t (s + 1… s + m) εκτύπωση "μοτίβο βρέθηκε στη θέση" s Εάν s <nm ts + 1 = (d ( ts - t (s + 1) h) + t (s + m + 1)) mod q

Παραδείγματα Python, Java και 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); )

Περιορισμοί του αλγόριθμου Rabin-Karp

Ψευδής επιτυχία

Όταν η τιμή κατακερματισμού του μοτίβου ταιριάζει με την τιμή κατακερματισμού ενός παραθύρου του κειμένου, αλλά το παράθυρο δεν είναι το πραγματικό μοτίβο, τότε ονομάζεται ψευδής επιτυχία.

Η ψευδής επιτυχία αυξάνει την πολυπλοκότητα του χρόνου στον αλγόριθμο. Για να ελαχιστοποιήσουμε την ψευδή επιτυχία, χρησιμοποιούμε συντελεστή. Μειώνει σημαντικά το ψεύτικο χτύπημα.