Ο αλγόριθμος Rabin-Karp εξήγησε

Ο αλγόριθμος Rabin-Karp είναι ένας αλγόριθμος αντιστοίχισης / αναζήτησης συμβολοσειρών που αναπτύχθηκε από τους Michael O. Rabin και Richard M. Karp. Χρησιμοποιεί τεχνική κατακερματισμού και ωμή δύναμη για σύγκριση και είναι ένας καλός υποψήφιος για ανίχνευση λογοκλοπής.

Σημαντικοί όροι

  • το μοτίβο είναι η συμβολοσειρά που θα αναζητηθεί. Σκεφτείτε το μήκος του μοτίβου ωςχαρακτήρες Μ .
  • Το κείμενο είναι ολόκληρο το κείμενο από το οποίο θα αναζητηθεί το μοτίβο. Σκεφτείτε το μήκος του κειμένου ωςχαρακτήρες Ν .

Τι είναι η σύγκριση ωμής δύναμης;

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

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

  1. Υπολογίστε την τιμή κατακερματισμού του μοτίβου
  2. Υπολογίστε την τιμή κατακερματισμού των πρώτων χαρακτήρων M του κειμένου
  3. Συγκρίνετε και τις δύο τιμές κατακερματισμού
  4. Εάν είναι άνιση, υπολογίστε την τιμή κατακερματισμού για τους επόμενους χαρακτήρες M του κειμένου και συγκρίνετε ξανά.
  5. Εάν είναι ίσοι, πραγματοποιήστε μια σύγκριση ωμής δύναμης.
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)

Πλεονέκτημα έναντι του αλγόριθμου Naive String Matching

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