Η μεγαλύτερη κοινή ακολουθία

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

Η μακρύτερη κοινή ακολουθία (LCS) ορίζεται ως η μακρύτερη ακολουθία που είναι κοινή σε όλες τις δοθείσες ακολουθίες, υπό την προϋπόθεση ότι τα στοιχεία της ακολουθίας δεν απαιτείται να καταλαμβάνουν διαδοχικές θέσεις εντός των αρχικών ακολουθιών.

Εάν τα S1 και S2 είναι οι δύο δεδομένες ακολουθίες τότε, το Ζ είναι η κοινή ακολουθία των S1 και S2 εάν το Ζ είναι ακολουθία και των δύο S1 και S2. Επιπλέον, το Ζ πρέπει να είναι μια αυστηρά αυξανόμενη ακολουθία των δεικτών τόσο του S1 όσο και του S2.

Σε μια αυστηρά αυξανόμενη ακολουθία, οι δείκτες των στοιχείων που επιλέγονται από τις αρχικές ακολουθίες πρέπει να είναι σε αύξουσα σειρά στο Ζ.

Αν

 S1 = (B, C, D, A, A, C, D)

Τότε, (A, D, B)δεν μπορεί να είναι μια ακολουθία του S1 καθώς η σειρά των στοιχείων δεν είναι η ίδια (δηλαδή δεν αυξάνεται αυστηρά η ακολουθία).

Ας κατανοήσουμε το LCS με ένα παράδειγμα.

Αν

 S1 = (B, C, D, A, A, C, D) S2 = (A, C, D, B, A, C)

Τότε, οι κοινές ακολουθίες είναι (B, C), (C, D, A, C), (D, A, C), (A, A, C), (A, C), (C, D), …

Μεταξύ αυτών των ακολουθιών, (C, D, A, C)είναι η μεγαλύτερη κοινή ακολουθία. Θα βρούμε αυτήν τη μεγαλύτερη κοινή ακολουθία χρησιμοποιώντας δυναμικό προγραμματισμό.

Πριν προχωρήσετε περαιτέρω, εάν δεν γνωρίζετε ήδη για το δυναμικό προγραμματισμό, μεταβείτε στον δυναμικό προγραμματισμό.

Χρησιμοποιώντας Δυναμικό Προγραμματισμό για να βρείτε το LCS

Ας πάρουμε δύο ακολουθίες:

Η πρώτη σειρά

Δεύτερη ακολουθία

Τα ακόλουθα βήματα ακολουθούνται για την εύρεση της μεγαλύτερης κοινής ακολουθίας.

Δημιουργήστε έναν πίνακα διαστάσεων n+1*m+1όπου n και m είναι τα μήκη X και Y αντίστοιχα. Η πρώτη σειρά και η πρώτη στήλη γεμίζουν με μηδενικά. Αρχικοποιήστε έναν πίνακα
Γεμίστε κάθε κελί του πίνακα χρησιμοποιώντας την ακόλουθη λογική.
Εάν ο χαρακτήρας που αντιστοιχεί στην τρέχουσα σειρά και στην τρέχουσα στήλη ταιριάζουν, τότε γεμίστε το τρέχον κελί προσθέτοντας ένα στο διαγώνιο στοιχείο. Στρέψτε ένα βέλος στο διαγώνιο κελί.
Διαφορετικά, πάρτε τη μέγιστη τιμή από την προηγούμενη στήλη και το στοιχείο προηγούμενης γραμμής για τη συμπλήρωση του τρέχοντος κελιού. Στρέψτε ένα βέλος στο κελί με τη μέγιστη τιμή. Εάν είναι ίσοι, δείξτε σε οποιοδήποτε από αυτά. Συμπληρώστε τις τιμές
Το βήμα 2 επαναλαμβάνεται έως ότου γεμίσει ο πίνακας. Συμπληρώστε όλες τις τιμές
Η τιμή στην τελευταία σειρά και στην τελευταία στήλη είναι το μήκος της μεγαλύτερης κοινής ακολουθίας. Η κάτω δεξιά γωνία είναι το μήκος του LCS
Για να βρείτε τη μεγαλύτερη κοινή ακολουθία, ξεκινήστε από το τελευταίο στοιχείο και ακολουθήστε την κατεύθυνση του βέλους. Τα στοιχεία που αντιστοιχούν στο σύμβολο () αποτελούν τη μεγαλύτερη κοινή ακολουθία. Δημιουργήστε μια διαδρομή σύμφωνα με τα βέλη

Έτσι, η μεγαλύτερη κοινή ακολουθία είναι το CD.

LCS

Πώς είναι ένας δυναμικός αλγόριθμος προγραμματισμού πιο αποτελεσματικός από τον αναδρομικό αλγόριθμο κατά την επίλυση ενός προβλήματος LCS;

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

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

Έτσι, ο χρόνος που απαιτείται από μια δυναμική προσέγγιση είναι ο χρόνος που απαιτείται για τη συμπλήρωση του πίνακα (δηλ. O (mn)). Ενώ, ο αλγόριθμος αναδρομής έχει την πολυπλοκότητα 2 ^{max (m, n)} .

Μεγαλύτερος κοινός αλγόριθμος ακολουθίας

 Τα X και Y είναι δύο δεδομένες ακολουθίες. Αρχικοποιήστε έναν πίνακα LCS διάστασης X. μήκος * Y. μήκος X. ετικέτα = X Y. ετικέτα = Y LCS (0) () = 0 LCS () (0) = 0 Έναρξη από LCS ( 1) (1) Σύγκριση X (i) και Y (j) Εάν X (i) = Y (j) LCS (i) (j) = 1 + LCS (i-1, j-1) Στρέψτε ένα βέλος στο LCS (i) (j) Αλλιώς LCS (i) (j) = max (LCS (i-1) (j), LCS (i) (j-1)) Τοποθετήστε ένα βέλος στο max (LCS (i-1) ( j), LCS (i) (j-1))

Παραδείγματα Python, Java και C / C ++

Python Java C C ++

 # The longest common subsequence in Python # Function to find lcs_algo def lcs_algo(S1, S2, m, n): L = ((0 for x in range(n+1)) for x in range(m+1)) # Building the mtrix in bottom-up way for i in range(m+1): for j in range(n+1): if i == 0 or j == 0: L(i)(j) = 0 elif S1(i-1) == S2(j-1): L(i)(j) = L(i-1)(j-1) + 1 else: L(i)(j) = max(L(i-1)(j), L(i)(j-1)) index = L(m)(n) lcs_algo = ("") * (index+1) lcs_algo(index) = "" i = m j = n while i> 0 and j> 0: if S1(i-1) == S2(j-1): lcs_algo(index-1) = S1(i-1) i -= 1 j -= 1 index -= 1 elif L(i-1)(j)> L(i)(j-1): i -= 1 else: j -= 1 # Printing the sub sequences print("S1 : " + S1 + "S2 : " + S2) print("LCS: " + "".join(lcs_algo)) S1 = "ACADB" S2 = "CBDA" m = len(S1) n = len(S2) lcs_algo(S1, S2, m, n)

 // The longest common subsequence in Java class LCS_ALGO ( static void lcs(String S1, String S2, int m, int n) ( int()() LCS_table = new int(m + 1)(n + 1); // Building the mtrix in bottom-up way for (int i = 0; i <= m; i++) ( for (int j = 0; j <= n; j++) ( if (i == 0 || j == 0) LCS_table(i)(j) = 0; else if (S1.charAt(i - 1) == S2.charAt(j - 1)) LCS_table(i)(j) = LCS_table(i - 1)(j - 1) + 1; else LCS_table(i)(j) = Math.max(LCS_table(i - 1)(j), LCS_table(i)(j - 1)); ) ) int index = LCS_table(m)(n); int temp = index; char() lcs = new char(index + 1); lcs(index) = ''; int i = m, j = n; while (i> 0 && j> 0) ( if (S1.charAt(i - 1) == S2.charAt(j - 1)) ( lcs(index - 1) = S1.charAt(i - 1); i--; j--; index--; ) else if (LCS_table(i - 1)(j)> LCS_table(i)(j - 1)) i--; else j--; ) // Printing the sub sequences System.out.print("S1 : " + S1 + "S2 : " + S2 + "LCS: "); for (int k = 0; k <= temp; k++) System.out.print(lcs(k)); System.out.println(""); ) public static void main(String() args) ( String S1 = "ACADB"; String S2 = "CBDA"; int m = S1.length(); int n = S2.length(); lcs(S1, S2, m, n); ) )

 // The longest common subsequence in C #include #include int i, j, m, n, LCS_table(20)(20); char S1(20) = "ACADB", S2(20) = "CBDA", b(20)(20); void lcsAlgo() ( m = strlen(S1); n = strlen(S2); // Filling 0's in the matrix for (i = 0; i <= m; i++) LCS_table(i)(0) = 0; for (i = 0; i <= n; i++) LCS_table(0)(i) = 0; // Building the mtrix in bottom-up way for (i = 1; i <= m; i++) for (j = 1; j = LCS_table(i)(j - 1)) ( LCS_table(i)(j) = LCS_table(i - 1)(j); ) else ( LCS_table(i)(j) = LCS_table(i)(j - 1); ) ) int index = LCS_table(m)(n); char lcsAlgo(index + 1); lcsAlgo(index) = ''; int i = m, j = n; while (i> 0 && j> 0) ( if (S1(i - 1) == S2(j - 1)) ( lcsAlgo(index - 1) = S1(i - 1); i--; j--; index--; ) else if (LCS_table(i - 1)(j)> LCS_table(i)(j - 1)) i--; else j--; ) // Printing the sub sequences printf("S1 : %s S2 : %s ", S1, S2); printf("LCS: %s", lcsAlgo); ) int main() ( lcsAlgo(); printf(""); )

 // The longest common subsequence in C++ #include using namespace std; void lcsAlgo(char *S1, char *S2, int m, int n) ( int LCS_table(m + 1)(n + 1); // Building the mtrix in bottom-up way for (int i = 0; i <= m; i++) ( for (int j = 0; j <= n; j++) ( if (i == 0 || j == 0) LCS_table(i)(j) = 0; else if (S1(i - 1) == S2(j - 1)) LCS_table(i)(j) = LCS_table(i - 1)(j - 1) + 1; else LCS_table(i)(j) = max(LCS_table(i - 1)(j), LCS_table(i)(j - 1)); ) ) int index = LCS_table(m)(n); char lcsAlgo(index + 1); lcsAlgo(index) = ''; int i = m, j = n; while (i> 0 && j> 0) ( if (S1(i - 1) == S2(j - 1)) ( lcsAlgo(index - 1) = S1(i - 1); i--; j--; index--; ) else if (LCS_table(i - 1)(j)> LCS_table(i)(j - 1)) i--; else j--; ) // Printing the sub sequences cout << "S1 : " << S1 << "S2 : " << S2 << "LCS: " << lcsAlgo << ""; ) int main() ( char S1() = "ACADB"; char S2() = "CBDA"; int m = strlen(S1); int n = strlen(S2); lcsAlgo(S1, S2, m, n); )