L16 · Δυναμικός Προγραμματισμός III — Ευθυγράμμιση Συμβολοσειρών

Τι θα δούμε

Πόσο όμοιες είναι δύο συμβολοσειρές; Ακούγεται απλό ερώτημα — αλλά πάνω του στηρίζονται το unix diff, ο διορθωτής ορθογραφίας, η αναγνώριση φωνής, και η σύγκριση ακολουθιών DNA. Η απάντηση λέγεται απόσταση επεξεργασίας (edit distance) και είναι ένα από τα πιο κομψά DP του μαθήματος.

Και κρύβει δύο βαθιές ιδέες που αξίζουν από μόνες τους:

1. Ο πίνακας του DP δεν είναι απλώς πίνακας — είναι γράφημα, και η βέλτιστη λύση είναι ένα συντομότερο μονοπάτι.
2. Συνδυάζοντας DP με διαίρει-και-κυρίευε, λύνουμε το πρόβλημα σε γραμμικό χώρο — ο αλγόριθμος του Hirschberg.

Ομοιότητα συμβολοσειρών

Φαντάσου ότι πληκτρολογείς μια λέξη και ο διορθωτής σού προτείνει διόρθωση. Πώς ξέρει ποια λέξη εννοούσες; Συγκρίνει αυτό που έγραψες με κάθε λέξη του λεξικού και διαλέγει την πιο κοντινή. Αλλά τι θα πει «κοντινή» για δύο λέξεις;

Δες αυτές τις δύο:

o c u r r a n c e
o c c u r e n c e

Καταλαβαίνεις αμέσως ότι είναι «η ίδια λέξη με λάθη». Το μάτι το βλέπει — αλλά ο υπολογιστής χρειάζεται έναν αριθμό. Πώς ποσοτικοποιείς αυτή τη διαίσθηση;

Η ιδέα: μέτρα πόσες στοιχειώδεις αλλαγές χρειάζονται για να μετατρέψεις τη μία λέξη στην άλλη. Τρία είδη αλλαγής, και μόνο τρία:

• εισαγωγή ενός χαρακτήρα,
• διαγραφή ενός χαρακτήρα,
• αντικατάσταση ενός χαρακτήρα με άλλον.

Όσο λιγότερες αλλαγές χρειάζονται, τόσο πιο όμοιες οι λέξεις. Αυτός ο ελάχιστος αριθμός αλλαγών — με κατάλληλο κόστος για την καθεμία — είναι η απόσταση επεξεργασίας.

Ευθυγράμμιση συμβολοσειρών

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

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

X:  o c - u r r a n c e
Y:  o c c u r e - n c e

Κάθε στήλη είναι μία «κίνηση»: είτε ένα ζευγάρι γραμμάτων, είτε ένα γράμμα με ένα κενό. Το κόστος της στήλης:

• δύο ίδια γράμματα → $0$ (τέλειο ταίριασμα)·
• δύο διαφορετικά γράμματα → $\alpha$ (σύγκρουση)·
• ένα γράμμα κι ένα κενό → $\delta$.

Η ευθυγράμμιση πιο πάνω έχει ένα κενό (στήλη 3), μία σύγκρουση r–e (στήλη 6) κι άλλο ένα κενό (στήλη 7): κόστος $\delta +\alpha +\delta$. Το κόστος μιας ευθυγράμμισης είναι το άθροισμα όλων των στηλών της, και στόχος μας είναι η ευθυγράμμιση ελάχιστου κόστους — αυτό ακριβώς το ελάχιστο είναι η απόσταση επεξεργασίας.

Ένας κανόνας κάνει τις ευθυγραμμίσεις «λογικές»: τα ζεύγη δεν διασταυρώνονται. Αν διαβάσεις και τις δύο λέξεις από αριστερά προς δεξιά, τα ζεύγη πρέπει να κρατούν τη σειρά τους — μια λέξη δεν «ανακατεύεται». Αυτό φαίνεται καλύτερα στο εργαλείο παρακάτω.

Δες το μόνος σου. Παρακάτω χτίζεις μια ευθυγράμμιση δύο σύντομων συμβολοσειρών DNA, κίνηση-κίνηση, και παρακολουθείς το κόστος να σχηματίζεται:

Η αναδρομή

Τώρα ο αλγόριθμος. Όπως πάντα στον δυναμικό προγραμματισμό, ρωτάμε: ποια είναι η τελευταία απόφαση;

Ορίζουμε $\text{OPT}(i,j)$ = ελάχιστο κόστος ευθυγράμμισης των προθεμάτων $x_1\cdots x_i$ και $y_1\cdots y_j$. Κοίτα την τελευταία στήλη μιας βέλτιστης ευθυγράμμισης — τι μπορεί να περιέχει; Ακριβώς τις τρεις κινήσεις που μόλις δοκίμασες:

• Ταίριασμα $x_i$ με $y_j$: πληρώνεις ${\alpha }_{x_i{y}_j}$ (ή $0$ αν είναι ίδιοι), συν το βέλτιστο για $x_1\cdots x_{i-1}$, $y_1\cdots y_{j-1}$.
• Το $x_i$ αταίριαστο: πληρώνεις κενό $\delta$, συν το βέλτιστο για $x_1\cdots x_{i-1}$, $y_1\cdots y_j$.
• Το $y_j$ αταίριαστο: πληρώνεις κενό $\delta$, συν το βέλτιστο για $x_1\cdots x_i$, $y_1\cdots y_{j-1}$.

Δεν ξέρουμε ποια από τις τρεις είναι η σωστή — οπότε τις δοκιμάζουμε όλες και κρατάμε τη φθηνότερη. Αυτό είναι το $\min$.

Δες το πλέγμα να γεμίζει. Σε κάθε γραμμή φωτίζεται ένα κελί με τους τρεις γείτονες από τους οποίους εξαρτάται, και στο τέλος ανακτάται η βέλτιστη ευθυγράμμιση με πέρασμα προς τα πίσω:

Το DP πλέγμα είναι γράφημα

Εδώ έρχεται η πρώτη βαθιά ιδέα — και είναι μια αλλαγή οπτικής, όχι νέος αλγόριθμος.

Μέχρι τώρα λέγαμε «γεμίζουμε έναν πίνακα». Αλλά κοίτα ξανά τι κάναμε: κάθε κελί $(i,j)$ πήρε την τιμή του από τρία άλλα κελιά, προσθέτοντας ένα κόστος. «Παίρνω την τιμή μου από γείτονες, συν ένα κόστος» — αυτό είναι ο ορισμός ενός γραφήματος με βάρη.

Φτιάχνουμε λοιπόν ένα γράφημα απόστασης επεξεργασίας: μια κορυφή για κάθε ζεύγος $(i,j)$, με τρεις ακμές που αντιστοιχούν στις τρεις περιπτώσεις της αναδρομής:

• κάτω $(i-1,j)\to (i,j)$ — κόστος $\delta$: αφήνει το $x_i$ αταίριαστο,
• δεξιά $(i,j-1)\to (i,j)$ — κόστος $\delta$: αφήνει το $y_j$ αταίριαστο,
• διαγώνια $(i-1,j-1)\to (i,j)$ — κόστος ${\alpha }_{x_i{y}_j}$: ταιριάζει το $x_i$ με το $y_j$.

Στο εργαλείο παρακάτω, ο αριθμός μέσα σε κάθε κορυφή είναι το $\text{OPT}(i,j)$ της — και βλέπεις ότι είναι όντως η συντομότερη απόσταση από το $(0,0)$. Περπάτησε το βέλτιστο μονοπάτι και δες κάθε ακμή του να γίνεται μία στήλη της ευθυγράμμισης:

Ευθυγράμμιση σε γραμμικό χώρο — Hirschberg

Ο πίνακας $\Theta (mn)$ είναι το πρόβλημα. Στην υπολογιστική βιολογία ευθυγραμμίζονται ακολουθίες DNA με $m=n=100.000$ — ένας πίνακας $10^{10}$ κελιών δεν χωράει σε καμία μνήμη.

Πρώτη παρατήρηση — η τιμή σε γραμμικό χώρο

Πρώτη παρατήρηση, και σώζει πολλά: για να υπολογίσεις μια γραμμή $\text{OPT}(i,\cdot )$ του πίνακα, χρειάζεσαι μόνο την αμέσως προηγούμενη, $\text{OPT}(i-1,\cdot )$ — η αναδρομή κοιτάει πάντα ένα κελί από πάνω, ένα διαγώνια, κι ένα αριστερά στην ίδια γραμμή. Όλες οι παλιότερες γραμμές είναι πια άχρηστες.

Άρα κράτα μόνο δύο γραμμές κάθε φορά. Η τιμή $\text{OPT}(m,n)$ υπολογίζεται έτσι σε $O(m+n)$ χώρο και $O(mn)$ χρόνο.

Δες ακριβώς τι κρατιέται και τι πετιέται — και γιατί αυτό αρκεί για την τιμή αλλά όχι για την ευθυγράμμιση:

Η ιδέα του Hirschberg (1975) — διαίρει-και-κυρίευε + DP

Δουλεύουμε στο γράφημα απόστασης που μόλις είδαμε. Ορίζουμε δύο ποσότητες — και οι δύο υπολογίζονται με το κόλπο των δύο γραμμών, σε γραμμικό χώρο:

• $f(i,j)$ = συντομότερο μονοπάτι από την αρχή $(0,0)$ στο $(i,j)$ — δηλαδή ακριβώς το $\text{OPT}(i,j)$·
• $g(i,j)$ = συντομότερο μονοπάτι από το $(i,j)$ στο τέλος $(m,n)$ — το ίδιο πράγμα «ανάποδα», με τις ακμές αντεστραμμένες.

Το $f$ μετρά «πόσο κοστίζει να φτάσω εδώ»· το $g$ μετρά «πόσο κοστίζει να τελειώσω από εδώ».

Διαλέγουμε τώρα τη μεσαία στήλη $j=n/2$. Για κάθε κελί της, το $f+g$ λέει πόσο θα κόστιζε η καλύτερη ευθυγράμμιση αν ήταν αναγκασμένη να περάσει από εκεί. Πάρε τη γραμμή $q$ με το ελάχιστο $f(q,n/2)+g(q,n/2)$: τότε υπάρχει βέλτιστη ευθυγράμμιση που όντως περνά από την κορυφή $(q,n/2)$. Βρήκαμε ένα σίγουρο κελί της απάντησης — και μόνο με γραμμικό χώρο.

Και τώρα διαίρει-και-κυρίευε: η ευθυγράμμιση πάνω-αριστερά του $(q,n/2)$ κι αυτή κάτω-δεξιά είναι ανεξάρτητα, μικρότερα αντίγραφα του ίδιου προβλήματος. Αναδρομή στο καθένα.

Κλείδωσε τη γνώση

Βάλε στη σειρά τα βήματα του DP για την ευθυγράμμιση:

Και συμπλήρωσε τα κενά:

Μοτίβο σκέψης