Αλγόριθμοι για αναζήτηση προτύπων

Brute-Force Algorithm

Ο αλγόριθμος Brute Force είναι ίσως ο ποιο απλός από όλους τους αλγορίθμους , αλλά είναι πολύ αργός . Ο αλγόριθμος έχει ως εξής :

Βήμα 1: Θέσε j <- 0 και i <- 0.

Βήμα 2: Αν i<= n και j<= m τότε πήγαινε στο βήμα 3, διαφορετικά πήγαινε το 5.

Βήμα 3: Αν P[j]=T[i] τότε θέσε i <- i+1 και j <- j+1,διαφορετικά θέσε i <- i-j+1 και

Βήμα 4: Πήγαινε στο βήμα 2.

Βήμα 5: Αν j>m-1 τότε θέσε i <- i-m,διαφορετικά θέσε i<- 0

Βήμα 6: Εκτύπωσε τη θέση i

Βήμα 7: Τερμάτισε

Ο δείκτης j αντιστοιχεί στο j χαρακτήρα του P και ο δείκτης i αντιστοιχεί στο i χαρακτήρα του Τ. P είναι το πρότυπο και T είναι το αλφαριθμητικό.

Εάν ψάχνουμε για ένα πρότυπο abaa σε ένα string, η διαδικασία θα έμοιαζε κάπως έτσι:

a b c a b a a d e f a b e a b a a b a a d e ταιριάζει στη θέση 4

a b c a b a a d e f a b e a b a a b a a d e ταιριάζει στη θέση 14

a b c a b a a d e f a b e a b a a b a a d e ταιριάζει στη θέση 17

Knuth-Morris-Pratt Algorithm

Η βασική ιδέα του αλγορίθμου αυτού είναι ότι όταν δεν έχουμε ταύτιση χαρακτήρων ανάμεσα στο T και στο P στις θέσεις i και j αντίστοιχα, ο αλγόριθμος δεν οπισθοδρομεί σε προηγούμενους χαρακτήρες του T, αλλά χρησιμοποιεί ειδική πληροφορία που μετατοπίζει το P στους επόμενους χαρακτήρες προς τα δεξιά. Αυτή η ειδική πληροφορία υπολογίζεται πριν αρχίσει η αναζήτηση του P στο T.

Με άλλα λόγια ο ΚΜP ακολουθεί δύο φάσεις : την προεπεξεργασία του P και την αναζήτηση του P στο T. Η αναζήτηση γίνεται σαρώνοντας το κείμενο από αριστερά προς τα δεξιά, αλλά στην περίπτωση που έχουμε μη ταύτιση στο j-χαρακτήρα του Ρ, δεν κάνει οπισθοδρόμηση αλλά χρησιμοποιεί έναν ειδικό πίνακα που λέγεται next, ο οποίος παρέχει μια πληροφορία σχετικά με το πόσο θα μετατοπιστεί το Ρ προς τα δεξιά. Με άλλα λόγια, σε κάθε θέση του πίνακα next, δηλαδή next[j] είναι η θέση του χαρακτήρα στο Ρ, το οποίο πρέπει να εξετάσουμε στην επόμενη σύγκριση μετά τη μη ταύτιση που εμφανίστηκε στο j χαρακτήρα του Ρ. Έτσι το πρότυπο θα μετατοπιστεί j-next[j] θέσεις προς τα δεξιά σε σχέση με το Τ.

Ο αλγόριθμος είναι ο παρακάτω:

Βήμα 2: Θέσε i <- 0 και j <- 0

Βήμα 3: Αν i<=n και j<=m τότε πήγαινε στο βήμα 4, διαφορετικά πήγαινε στο 6

Βήμα 4: Αν P[j]=T[i] ή j=0 τότε θέσε i <- i+1 και j <- j+1,διαφορετικά θέσε j<-next[j]

Βήμα 5: Πήγαινε στο βήμα 3

Βήμα 6: Αν j>m-1 τότε θέσε i <- i-m, διαφορετικά θέσε i <- 0

Βήμα 7: Εκτύπωσε την θέση i

Βήμα 8: Τερμάτισε

Διαδικασία PRE_KMP(P,m,next)

Βήμα 2: Αν j<m τότε πήγαινε στο βήμα 3, διαφορετικά τερμάτισε

Βήμα 4: Αν P[j]=T[i] τότε θέσε next[i] <- next[j], διαφορετικά θέσε next[i] <- j

Βήμα 5: Πήγαινε στο βήμα 2

Βήμα 6: Επέστρεψε τον πίνακα next

Boyer-Moore (ΒΜ) Algorithm

Ο αλγόριθμος αυτός είναι ο ποιο γρήγορος από όλους τους αλγόριθμους. Ακολουθεί δύο φάσεις: την προεπεξεργασία του Ρ και την αναζήτηση του Ρ στο Τ. Η αναζήτηση γίνεται ως εξής: Ο ΒΜ εκτελεί συγκρίσεις των χαρακτήρων ανάμεσα στο Ρ και το Τ,

από δεξιά προς τα αριστερά. Στην περίπτωση που έχουμε μη ταύτιση στο j-χαρακτήρα του Ρ, τότε χρησιμοποιεί τους πίνακες delta1, και delta2 που μας δίνουν την πληροφορία κατά πόσους χαρακτήρες πρέπει να μετατοπιστεί πρέπει να μετατοπιστεί το πρότυπο Ρ.

Ο πρώτος πίνακας delta1 έχει μέγεθος όσοι είναι οι χαρακτήρες του αλφάβητου (ASIZE) ενώ ο δεύτερος πίνακας delta2 έχει μέγεθος όσοι είναι οι χαρακτήρες του προτύπου Ρ. Οι αλγόριθμος για την κατασκευή του πίνακα delta1 είναι ο εξής :

Διαδικασία PRE_D1(P,m,delta1)

Βήμα 1: Για w από 0 έως ASIZE κάνε

Θέσε delta1[w] <- m

Βήμα 2: Για j από 0 έως m-1 κάνε

Θέσε delta1[P[j]] <- m-j-1

Βήμα 3: Επέστρεψε τον πίνακα delta1

Ο αλγόριθμος ΒΜ υπό μορφή βημάτων είναι ο εξής:

Βήμα 2: Κάλεσε την διαδικασία PRE_D2(P,m,delta2)

Βήμα 3: Θέσε i <- m-1 και j <- m-1

Βήμα 4: Αν i<=n και j>0 τότε πήγαινε στο βήμα 5, διαφορετικά πήγαινε στο βήμα 7

Βήμα 5: Αν Ρ[j]=T[i] τότε θέσε i <- i-1 και j <- j-1, διαφορετικά θέσε

Βήμα 6: Πήγαινε στο βήμα 4

Βήμα 7: Αν j<1 τότε θέσε i <- i+1, διαφορετικά θέσε i <- 0

Βήμα 8: Εκτύπωσε την θέση i

Βήμα 9: Τερμάτισε

Σημείωση: Στη διαδικασία PRE_D2(P,m,delta2) συμπληρώνεται ο πίνακας delta2

Rabin-Karp (RK)Algorithm

Ο αλγόριθμος αυτός στηρίζεται στην εξής λογική. Αντί να ελέγχουμε σε κάθε διαδοχική θέση του Τ για το αν το Ρ ταυτίζεται , όπως γίνεται ακριβώς στον αλγόριθμο Brute Force, φαίνεται περισσότερο αποτελεσματικό να ελέγχουμε μόνο αν ένα τμήμα m (όπου m είναι το μήκος του Ρ) χαρακτήρων του Τ είναι ταυτισμένο με το Ρ. Για να μπορέσουμε να ελέγξουμε την ομοιότητα ή την ταύτιση ανάμεσα στο τμήμα m χαρακτήρων του Τ με το Ρ, πρέπει να χρησιμοποιήσουμε τη συνάρτηση κατακερματισμού. Δηλαδή κατά τη διάρκεια της φάσης αναζήτησης για το Ρ, ο αλγόριθμος συγκρίνει την τιμή κατακερματισμού των m χαρακτήρων του Τ[i] σε διαδοχικές θέσεις ανάμεσα από το 0 έως n-m με την τιμή κατακερματισμού των m χαρακτήρων του Ρ. Εάν δεν έχουμε ισότητα των τιμών κατακερματισμού, τότε μετατοπίζουμε το Ρ μια θέση προς τα δεξιά, που υπολογίζουμε την τιμή των επόμενων χαρακτήρων του Τ και την συγκρίνουμε με την τιμή των m χαρακτήρων του Ρ.

Η συνάρτηση κατακερματισμού πρέπει να έχει τις ακόλουθες ιδιότητες:

1) να είναι αποτελεσματικός ο υπολογισμός

2) να έχει υψηλή διάκριση για τα αλφαριθμητικά

3) η συνάρτηση πρέπει να είναι της μορφής h(k)=k mod q, όπου q είναι ένας

μεγάλος πρώτος αριθμός ώστε να αποφύγουμε συχνές συγκρούσεις.

Ο αλγόριθμος RK υπο μορφή βημάτων είναι ο εξής :

Βήμα 1: Θέσε i <- 1, c <-d^(m-1) mod q,

Βήμα 2: Αν i<=n-m+1 τότε πήγαινε στο βήμα 3, διαφορετικά πήγαινε στο βήμα 5

Βήμα 3: Αν (hP=hT) και (P[0..m-1]=T[i..i+m-1]) τότε εμφάνισε την θέση i,

διαφορετικά θέσε

Βήμα 4: Πήγαινε στο βήμα 2

Βήμα 5: Αν i > n-m+1 τότε θέσε i <- 0, διαφορετικά εκτύπωσε την θέση i

Βήμα 6: Τερμάτισε

Σημείωση: το d είναι ίσο με 2, d=2.

Έστω ότι ψάχνουμε για το 31415 στο αλφαριθμητικό 2359023141526739921.

31415 mod 13 = 7, έτσι ψάχνουμε για όλες τους combinations p με p mod 13 = 7

7 Ταιριάζει στη θέση 7

7 (ψεύτικη ισότητα)