Κεφάλαιο 12Αλγόριθμοι Συμβολοσειρών

Αρχικά, ορίζουμε ως αλφάβητο ένα σύνολο $\mathrm{\Sigma }$ μεγέθους $\sigma =|\mathrm{\Sigma }|$ το οποίο αποτελείται από ένα πεπερασμένο πλήθος συμβόλων και συμβολίζουμε με ${\mathrm{\Sigma }}^{*}$ το σύνολο όλων των πεπερασμένων συμβολοσειρών που σχηματίζονται με βάση τα σύμβολα του $\mathrm{\Sigma }$. Παραδείγματα αλφάβητων αποτελούν το ελληνικό αλφάβητο $\{\alpha ,\beta ,\gamma ,\mathrm{\dots },\omega \}$, το δυαδικό αλφάβητο $\{0,1\}$, το αλφάβητο των αζωτούχων βάσεων των νουκλετιδίων $\{A,G,C,T\}$ κ.α. Στη συνέχεια, παραθέτουμε έναν τυπικό ορισμό για το πρόβλημα του ταιριάσματος συμβολοσειρών.

Για παράδειγμα, για το κείμενο $T$=“abrarabraba” και το πρότυπο $P$=“bra” υπάρχουν δύο ταυτίσεις και συγκεκριμένα στις θέσεις $2$ και $7$ του $T$.

Ίσως ο πιο απλός τρόπος για να επιλυθεί το πρόβλημα είναι με έναν αλγόριθμο Ωμής Βίας ο οποίος λειτουργεί ως εξής: Πρώτα από όλα, η αρχή του προτύπου τοποθετείται στην ίδια θέση με την αρχή του κειμένου και συγκρίνονται ένας-ένας οι χαρακτήρες του κειμένου και του προτύπου για να διαπιστωθεί αν υπάρχει ταύτιση. Αν υπάρχει ταύτιση, επιστρέφεται η θέση του $T$ στην οποία αυτή συνέβη και ο αλγόριθμος συνεχίζει μετατοπίζοντας το πρότυπο κατά μία θέση δεξιά. Σε περίπτωση που κατά τις συγκρίσεις διαπιστωθεί μία ασυμφωνία χαρακτήρων ο αλγόριθμος μετατοπίζει το πρότυπο κατά μία θέση δεξιά και επαναλαμβάνει τα ίδια βήματα. Η διαδικασία τερματίζεται όταν έχουν ελεγχθεί όλοι οι χαρακτήρες του κειμένου με το πρότυπο. Παρακάτω παρουσιάζεται ο ψευδοκώδικας του αλγορίθμου, ενώ ένα παράδειγμα εκτέλεσης βρίσκεται στο Σχήμα 12.1. Προσέξτε ότι με το συγκεκριμένο ψευδοκώδικα επιστρέφεται η θέση του κειμένου που συμβαίνει μόνο το πρώτο ταίριασμα και -1 αν δεν υπάρχει κάποιο ταίριασμα. Με τις κατάλληλες αλλαγές (γραμμές 5-6) είναι δυνατό ο ψευδοκώδικας να επιστρέφει τις θέσεις όλων των ταιριασμάτων.

    Algorithm BruteForceSM(T[1..n], P[1..m])
1.  for (i=1; i<=n-m+1; i++)
2.      j=1;
3.      while (j<=m && T[i+j-1]==P[j])
4.          j++;
5.      if (j==m+1)
6.          return i;
7.  return -1;

Ο αλγόριθμος Ωμής Βίας απαιτεί $O(nm)$ συνολικό χρόνο, καθώς υπάρχουν $O(n)$ πιθανές μετακινήσεις του προτύπου σε σχέση με το κείμενο και σε κάθε μια μετακίνηση πραγματοποιούνται $O(m)$ συγκρίσεις χαρακτήρων. Ως εκ τούτου, η επίδοση του δεν είναι ιδιαίτερα γρήγορη και γι’ αυτό το λόγο η χρήση του συνίσταται, όταν το μέγεθος του κειμένου και του προτύπου είναι σχετικά μικρά. Στη συνέχεια, θα εξετάσουμε αλγορίθμους που είτε επιταχύνουν τη σύγκριση μεταξύ προτύπου και κειμένου είτε μετακινούν το πρότυπο με πιο αποδοτικό τρόπο.

Μια πρώτη βελτίωση σε σχέση με τον αλγόριθμο Ωμής Βίας είναι ο αλγόριθμος Rabin-Karp ο οποίος και πάλι μεταφέρει το πρότυπο κατά μία θέση δεξιά σε κάθε επανάληψη, αλλά φιλοδοξεί επίσης να εκτελέσει τις συγκρίσεις κειμένου και προτύπου με έξυπνο τρόπο. Για να το πετύχει αυτό, ο αλγόριθμος εκμεταλλεύεται το γεγονός ότι κάθε συμβολοσειρά είναι δυνατό να αναπαρασταθεί ως ένας αριθμός (τιμή) με τη χρήση μιας συνάρτησης κατακερματισμού και ότι δύο ίδιες συμβολοσειρές έχουν ίσους αριθμούς για την ίδια συνάρτηση κατακερματισμού.

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

    Algorithm RabinKarpSM(T[1..n], P[1..m])
1.  hash_pattern = hash(P[1..m]);
2.  hash_string = hash(T[1..m]);
3.  for (i=1; i<=n-m+1; i++)
4.      if hash_string == hash_pattern then
5.          j=1;
6.          while (j<=m && T[i+j-1]==P[j])
7.              j++;
8.          if (j==m+1) then
9.              return i;
10.     hash_string = hash(T[i+1..i+m]);
11. return -1;

Για την εφαρμογή μιας συνάρτησης κατακερματισμού σε μια συμβολοσειρά μήκους $m$ χαρακτήρων απαιτείται $O(m)$ χρόνος. Παρατηρείστε ότι και αυτός ο αλγόριθμος έχει $O(nm)$ πολυπλοκότητα στη χειρότερη περίπτωση καθώς, αν επιλέξουμε μια «κακή» συνάρτηση κατακερματισμού η οποία αντιστοιχίζει συμβολοσειρές σε ένα μικρό σύνολο αριθμών⁹⁹Ένα ακραίο παράδειγμα θα ήταν μια συνάρτηση $hash(string)=c$, $c\in ℛ$ η οποία αποδίδει σε κάθε συμβολοσειρά $string$ την ίδια σταθερά $c$., η γραμμή 4 θα επαληθεύεται συχνά με αποτέλεσμα οι γραμμές 5-9, που έχουν συνολικό κόστος $O(m)$, να εκτελεστούν πολλές φορές. Στη πράξη, αυτό μπορεί να αποφευχθεί με τη χρήση συναρτήσεων κατακερματισμού οι οποίες προσφέρουν ικανοποιητική διακριτική ικανότητα μεταξύ των συμβολοσειρών.

Προτού μελετήσουμε το είδος των συναρτήσεων κατακερματισμού που μπορούν να χρησιμοποιηθούν από τον αλγόριθμο, πρέπει να αναφερθούμε στη γραμμή 10 και στην εφαρμογή της συνάρτησης κατακερματισμού στην εκάστοτε υποσυμβολοσειρά $T[i+\mathrm{1..}m+i]$. Αν σε κάθε επανάληψη υπολογίζεται εκ νέου η τιμή για κάθε συμβολοσειρά, αυτό θα έχει ως αποτέλεσμα η πολυπλοκότητα του αλγορίθμου να είναι ίση με $O(nm)$. Αυτό μπορούμε να το αποφύγουμε, παρατηρώντας ότι ανά πάσα στιγμή η τιμή $hash\mathrm{\_}string$ για τη συμβολοσειρά $T[i+\mathrm{1..}i+m]$ μπορεί να βασιστεί στη τιμή $hash\mathrm{\_}string$ της συμβολοσειράς $T[i..m+i-1]$, η οποία έχει ήδη υπολογιστεί στο προηγούμενο βήμα της επανάληψης.

Πιο συγκεκριμένα, μπορούμε να χρησιμοποιήσουμε ένα είδος κυλιόμενης συνάρτησης κατακερματισμού (rolling hash function), η οποία αντιστοιχίζει σε κάθε χαρακτήρα της συμβολοσειράς μια τιμή που εξαρτάται από τη θέση του μέσα στη συμβολοσειρά. Για παράδειγμα, η συμβολοσειρά $S$=“abra” μπορεί να αναπαρασταθεί από την τιμή $hash(abra)=(97*7^3)+(98*7^2)+(114*7^1)+(97*7^0)=38968$, όπου $97,98,114$ είναι οι ASCII αναπαραστάσεις των χαρακτήρων “a”, “b”, “r” αντίστοιχα και ο αριθμός 7 αντιστοιχεί σε μια βάση στην οποία εκφράζεται η τιμή $hash(abra)$¹⁰¹⁰Συνήθως ως βάση επιλέγεται ένας πρώτος αριθμός.

Έστω ότι στην επόμενη επανάληψη του αλγορίθμου προκύπτει η συμβολοσειρά “brab”. Τότε, για να υπολογίσουμε την τιμή $hash(brab)$, θα αφαιρέσουμε από την τιμή $hash(abra)$ την ποσότητα που αντιστοιχεί στο πρώτο “a”, θα πολλαπλασιάσουμε το υπόλοιπο με τη βάση και τέλος θα προσθέσουμε τη ποσότητα που αντιστοιχεί στο τελευταίο “b”. Αναλυτικότερα:

Με αυτό τον τρόπο, η γραμμή 10 απαιτεί $O(1)$ χρόνο σε κάθε επανάληψη, καθώς η τιμή $hash(T[i+\mathrm{1..}i+m])$ θα υπολογιστεί με βάση την τιμή $hash(T[i..i+m-1])$ που έχει υπολογιστεί στο αμέσως προηγούμενο βήμα της επανάληψης.

Οι αλγόριθμοι που παρουσιάστηκαν μέχρι αυτό το σημείο είχαν ως κοινό γνώρισμα τη μετατόπιση του προτύπου μία θέση δεξιά κατά τις διαδοχικές συγκρίσεις με το κείμενο. Στη συγκεκριμένη ενότητα θα αναλύσουμε τον αλγόριθμο Boyer-Moore-Horspool, ο οποίος κάνει χρήση ενός κανόνα για τη μετακίνηση του προτύπου σε σχέση με το κείμενο κατά περισσότερες από μία θέσεις.

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

Έστω ότι κατά τη διάρκεια των συγκρίσεων μεταξύ των υποσυμβολοσειρών του προτύπου και του κειμένου διαπιστωθεί μια ασυμφωνία χαρακτήρων. Τότε, αν με το σύμβολο $c$ συμβολίζουμε τον χαρακτήρα του κειμένου που είναι ευθυγραμμισμένος με τον τελευταίο χαρακτήρα του προτύπου, διακρίνουμε τέσσερις περιπτώσεις:

Περίπτωση 1

Η ασυμφωνία προκύπτει στον χαρακτήρα $c$ και δεν υπάρχουν χαρακτήρες με την τιμή του $c$ στο πρότυπο. Σε αυτή την περίπτωση μετακινούμε το πρότυπο κατά $m$ θέσεις.

                        c
      T[1]..            W           ..T[n]
                  EXAMPLE
                         EXAMPLE
      

Περίπτωση 2

Η ασυμφωνία προκύπτει στον χαρακτήρα $c$ και υπάρχουν χαρακτήρες με την τιμή του $c$ στο πρότυπο. Σε αυτή την περίπτωση μετακινούμε το πρότυπο, έτσι ώστε να ευθυγραμμιστεί η δεξιότερη εμφάνιση του $c$ στο πρότυπο με το $c$ του κειμένου.

                        c
      T[1]..            P           ..T[n]
                 PROPOSAL
                     PROPOSAL
      

Περίπτωση 3

Η ασυμφωνία προκύπτει αριστερότερα του $c$ και το $c$ δεν υπάρχει στους $m-1$ πρώτους χαρακτήρες του προτύπου. Αυτή η περίπτωση είναι αντίστοιχη με την Περίπτωση 1 και το πρότυπο θα μετακινηθεί κατά $m$ θέσεις.

                        c
      T[1]..         ASAL           ..T[n]
                 PROPOSAL
                         PROPOSAL
      

Περίπτωση 4

Η ασυμφωνία προκύπτει αριστερότερα του $c$ και το $c$ υπάρχει στους $m-1$ πρώτους χαρακτήρες του προτύπου. Αυτή η περίπτωση είναι αντίστοιχη με την Περίπτωση 2 και το πρότυπο θα μετακινηθεί με τέτοιο τρόπο, ώστε να ευθυγραμμιστεί η δεξιότερη εμφάνιση του $c$ στο πρότυπο με το $c$ του κειμένου.

                        c
      T[1]..          VER           ..T[n]
                 STRANGER
                      STRANGER
      

Οι παραπάνω περιπτώσεις μπορούν να κωδικοποιηθούν εύκολα με ένα προεπεξεργαστικό βήμα κατά το οποίο υπολογίζεται το πλήθος των θέσεων μετατόπισης ανάλογα με τον χαρακτήρα $c$ του κειμένου. Αναλυτικότερα, δημιουργούμε έναν πίνακα μετατοπίσεων $\sigma$ θέσεων, στον οποίο το κάθε κελί αντιστοιχεί σε έναν χαρακτήρα από το αλφάβητο. Έπειτα, αρχικοποιούμε κάθε κελί με την τιμή $m$ και για κάθε χαρακτήρα που εμφανίζεται στις $m-1$ πρώτες θέσεις του προτύπου, τοποθετούμε στο κελί του το πλήθος των θέσεων που απέχει η δεξιότερη εμφάνισή του από τον τελευταίο χαρακτήρα του προτύπου. Για παράδειγμα για το αλφάβητο $\{A,G,C,T\}$ και το πρότυπο “AAGATATTAG” έχουμε τον Πίνακα 12.1.

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

   Algorithm GenerateShiftTable(P[1..m])
1. for (i=1; i<=m; i++) do
2.     table[i] = m;
3. for (j=1; j<=m-1; j++) do
4.     table[P[j]] = m-j;
5. return table;

Με βάση όλα τα παραπάνω ο αλγόριθμος Boyer-Moore-Horspool παίρνει την ακόλουθη μορφή:

   Algorithm Boyer-Moore-HorspoolSM(T[1..n], P[1..m])
1. table = GenerateShiftTable(P[1..m]);
2. i = m;
3. while i<=n do
4.      k=0;
5.      while k<=m-1 and P[m-k]=T[i-k] do
6.          k=k+1;
7.      if k==m then
8.          return i-m+1;
9.      else
10.         i = i+table[T[i]]
11. return -1;

Αρχικά δημιουργείται ο πίνακας μετατοπίσεων σε $O(\sigma +m)$ χρόνο και ευθυγραμμίζεται η αρχή του προτύπου με την αρχή του κειμένου. Στη συνέχεια, εκτελούνται οι συγκρίσεις από τα δεξιά στα αριστερά και όποτε διαπιστωθεί ασυμφωνία η μετατόπιση γίνεται με βάση τον πίνακα μετατοπίσεων (γραμμή 10). Ένα παράδειγμα εκτέλεσης για $\mathrm{\Sigma }=\{a,b,r\}$, $T$=“abbrrab” και $P$=“rab” παρουσιάζεται στο Σχήμα 12.2. Ο αλγόριθμος Boyer-Moore-Horspool απαιτεί $O(nm)$ χρόνο στη χειρότερη περίπτωση, ωστόσο είναι δυνατό να αποδειχθεί ότι ο μέσος αριθμός συγκρίσεων για ένα χαρακτήρα είναι μεταξύ $1/\sigma$ και $2/(\sigma +1)$.

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

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

Μια παραλλαγή στο κλασικό πρόβλημα είναι αυτή του προσεγγιστικού ταιριάσματος συμβολοσειρών κατά το οποίο σκοπός είναι να βρεθούν συμβολοσειρές σε ένα κείμενο οι οποίες ταιριάζουν προσεγγιστικά με ένα πρότυπο. Μια μετρική για το πόσο ταιριάζουν δύο συμβολοσειρές είναι η Απόσταση Μετασχηματισμού (edit distance) η οποία μετράει το πλήθος των ενεργειών (εισαγωγή χαρακτήρα, διαγραφή χαρακτήρα, αλλαγή χαρακτήρα) που πρέπει να εφαρμοστούν στη μία συμβολοσειρά, έτσι ώστε να προκύψει η άλλη. Για παράδειγμα, η απόσταση μετασχηματισμού μεταξύ των συμβολοσειρών “example” και “excellent” είναι 5.

Τότε ένας τυπικός ορισμός για το πρόβλημα είναι: Για ένα κείμενο $T[\mathrm{1..}n]$ και ένα πρότυπο $P[\mathrm{1..}m]$ να βρεθεί η υποσυμβολοσειρά $T[i..j]$ η οποία έχει την ελάχιστη απόσταση μετασχηματισμού από το $P$ σε σχέση με όλες τις υποσυμβολοσειρές του $T$. Τη λύση στο πρόβλημα μπορεί να τη δώσει ένας αλγόριθμος Ωμής Βίας κατά τον οποίον υπολογίζεται η απόσταση μετασχηματισμού του $P$ από κάθε υποσυμβολοσειρά του $T$ και επιλέγεται η ελάχιστη. Ωστόσο, αν δεχθούμε ότι ο υπολογισμός της απόστασης μετασχηματισμού μεταξύ δύο συμβολοσειρών απαιτεί $O(nm)$ χρόνο, ο παραπάνω αλγόριθμος Ωμής Βίας θα απαιτούσε $O(n^{3}m)$ χρόνο συνολικά. Στη βιβλιογραφία έχουν προταθεί λύσεις οι οποίες βασίζονται στις γνωστές τεχνικές σχεδίασης (π.χ. δυναμικό προγραμματισμό) και πετυχαίνουν καλύτερη απόδοση.

Ο αλγόριθμος Rabin-Karp προτάθηκε στο [86], ενώ ο αλγόριθμος Boyer-Moore-Horspool, ο οποίος αποτελεί παραλλαγή του αλγορίθμου Boyer-Moore [17], προτάθηκε στο [79]. Άλλοι αλγόριθμοι για ταίριασμα συμβολοσειρών είναι οι αλγόριθμοι των Knuth-Morris-Pratt [93] και των Apostolico-Giancarlo [6]. Πειραματικά αποτελέσματα σχετικά με την απόδοση των αλγορίθμων έχουν παρουσιαστεί από τον Lecroq [96].

Για το ταίριασμα πολλαπλών προτύπων, πέρα από τον αλγόριθμο Rabin-Karp, έχουν προταθεί οι αλγόριθμοι Aho-Corasick [4] και Commentz-Walter [32], ενώ μια καλή αφετηρία στο πρόβλημα του προσεγγιστικού ταιριάσματος είναι η εργασία του Navarro [136].

1. 1.

   Για κείμενο $T$=“5621718”, πρότυπο $P$=“71” και συνάρτηση κατακερματισμού η οποία αντιστοιχίζει κάθε υποσυμβολοσειρά με το άθροισμα των χαρακτήρων της (π.χ. $hash(T[\mathrm{1..2}])=T[1]+T[2]=5+6=11)$ να εκτελέσετε τον αλγόριθμο Rabin-Karp. Πόσες φορές επαληθεύεται η γραμμή 4 στον ψευδοκώδικα της Ενότητας 12.2 χωρίς πράγματι να υπάρχει ταύτιση;

2. 2.

   Για αλφάβητο $\mathrm{\Sigma }=\{A,G,C,T\}$, κείμενο $T$=“AAGTTACTAAGAGGCTA” και πρότυπο $P$=“AGA” να εκτελέσετε τον αλγόριθμο Ωμής Βίας και τον αλγόριθμο Horspool. Πόσες μετακινήσεις του προτύπου και πόσες συγκρίσεις χαρακτήρων μέχρι την πρώτη ταύτιση θα γίνουν για κάθε αλγόριθμο;

3. 3.

   Να δώσετε ένα παράδειγμα εισόδου χειρότερης περίπτωσης για τον αλγόριθμο Horspool.

4. 4.

   Να προσαρμόσετε τον ψευδοκώδικα του αλγορίθμου Rabin-Karp (Ενότητα 12.2), έτσι ώστε να υποστηρίζει πολλαπλά πρότυπα. Με ποιον τρόπο θα ελέγχατε αποδοτικά την ύπαρξη μιας συγκεκριμένης τιμής μέσα στη δομή συνόλου;