Η μεγαλύτερη κοινή υποακολουθία: Python, C++ Παράδειγμα

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

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

Παράδειγμα

Για παράδειγμα, παρέχονται δύο συμβολοσειρές.

Ας υποθέσουμε ότι,

Pattern_1 = "RGBGARGA"
Pattern_2 = "BGRARG"

• Από το σχέδιο_1, μπορούν να παραχθούν ακολουθίες όπως "RGB", "RGGA", "RGAR". Για να δημιουργήσετε μια ακολουθία, πρέπει να διατηρήσετε τη σχετική θέση κάθε χαρακτήρα στη συμβολοσειρά.
• Από το σχέδιο_2, μπορούμε να παράγουμε ακολουθίες όπως "BGR", "BRAG", "RARG". Οι ακολουθίες μπορούν να παραχθούν εφόσον διατηρούν τη σχετική θέση της αρχικής χορδής.

Ο όρος σχετική θέση σημαίνει τάξη.

Για παράδειγμα, το "BRG" είναι μια έγκυρη ακολουθία επειδή το "B" εμφανίστηκε πρώτα, μετά το "R" και μετά το "G" στο αρχικό μοτίβο συμβολοσειράς_2. Ωστόσο, εάν μια ακολουθία είναι "RBRG", δεν είναι έγκυρη. Επειδή στην αρχική συμβολοσειρά (μοτίβο_2), το "Β" έρχεται πρώτο.

Έχουμε δύο επιλογές για να βρούμε τη μεγαλύτερη κοινή υποακολουθία από τις δύο δεδομένες ακολουθίες ή πίνακες.

• Αφελής μέθοδος
• Λύση δυναμικού προγραμματισμού: Η μεγαλύτερη κοινή υποακολουθία είναι επίσης γνωστή ως LCS.

Μια αφελής Λύση έχει μεγαλύτερη χρονική πολυπλοκότητα και δεν είναι η βέλτιστη λύση. Χρησιμοποιώντας τη λύση Dynamic Programming Solution (DP), ξεπερνάμε το πρόβλημα πολυπλοκότητας.

Αφελή μέθοδος

Η αφελής μέθοδος είναι μια απλή προσέγγιση του προβλήματος ανεξάρτητα από τη χρονική πολυπλοκότητα και άλλους παράγοντες βελτιστοποίησης.

Η μέθοδος Naive αποτελείται από "Brute Force", πολλαπλούς βρόχους, αναδρομικές μεθόδους στις περισσότερες περιπτώσεις.

Ο όρος ωμή δύναμη σημαίνει διέλευση από όλα τα πιθανά πρότυπα για ένα δεδομένο πρόβλημα.

Παράδειγμα

Από το παραπάνω παράδειγμα του σχεδίου1 και του μοτίβου2, ας υποθέσουμε ότι το σχέδιο1 έχει μήκος m και το σχέδιο2 έχει μήκος n. Για να ελέγξουμε κάθε πιθανή περίπτωση, πρέπει να αξιολογήσουμε κάθε πιθανή υποακολουθία του μοτίβου1 με το πρότυπο2.

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

Αυτοί είναι:

• Ο χαρακτήρας θα προστεθεί στη συνέχεια.
• Ο χαρακτήρας δεν θα προστεθεί στη συνέχεια.

Εδώ, οι εικόνες δείχνουν όλες τις ακολουθίες που μπορούμε να κάνουμε από τη συμβολοσειρά "ABCD".

Ακολουθία με 1 χαρακτήρα:

Ακολουθίες με 2 χαρακτήρες:

Ακολουθίες με 3 χαρακτήρες:

Από το παραπάνω διάγραμμα, υπάρχουν 14 ακολουθίες. Εάν δεν πάρουμε γράμματα, βασικά μια κενή συμβολοσειρά, οι συνολικές ακολουθίες θα είναι 15. Επιπλέον, η ίδια η συμβολοσειρά "ABCD" είναι μια ακολουθία. Άρα, οι συνολικές ακολουθίες είναι 16.

Έτσι, είναι δυνατή η δημιουργία 2⁴ ή 16 δευτερεύουσες ακολουθίες από το «ABCD». Στη συνέχεια, μια χορδή με μήκος m θα πρέπει να ακολουθήσει συνολικά 2^m.

Για κάθε υποακολουθία, πρέπει να το ελέγξουμε για ολόκληρο το μοτίβο2. Θα χρειαστεί 0(n) χρόνος. 0(n) σημαίνει τη συνάρτηση πολυπλοκότητας που υπολογίζει το χρόνο που απαιτείται για την εκτέλεση.

Έτσι, η συνολική χρονική πολυπλοκότητα γίνεται O(n*2^m). Για το παράδειγμα, είδαμε παραπάνω την τιμή των m=8 και n=5.

Ακολουθούν τα βήματα της αφελούς μεθόδου:

Βήμα 1) Πάρτε μια σειρά από το σχέδιο1.
Βήμα 2) Αντιστοιχίστε την ακολουθία από το βήμα 1 με το σχέδιο2.
Βήμα 3) Εάν ταιριάζει, τότε αποθηκεύστε την δευτερεύουσα σειρά.
Βήμα 4) Εάν έχει μείνει περισσότερη ακολουθία στο μοτίβο1, μεταβείτε ξανά στο βήμα 1.
Βήμα 5) Εκτυπώστε τη μεγαλύτερη υποακολουθία.

Βέλτιστη Υποδομή

Ο όρος βέλτιστη υποδομή σημαίνει ότι μια βέλτιστη λύση (απλή) μπορεί να βρεθεί με την επίλυση των υποπροβλημάτων. Για παράδειγμα, στο παραπάνω παράδειγμα, έχουμε το μοτίβο1 και το μοτίβο2.

Βήμα 1) Πάρτε τους δύο πρώτους χαρακτήρες από κάθε μοτίβο

Βήμα 2) Πάρτε τον τρίτο έως τον πέμπτο χαρακτήρες από κάθε μοτίβο.

Βήμα 3) Συνεχίστε παρόμοια με τους υπόλοιπους χαρακτήρες.

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

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

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

Για παράδειγμα, ας δούμε το δέντρο αναδρομής.

Στο σκουρόχρωμο πλαίσιο, μπορείτε να παρατηρήσετε επικαλυπτόμενα υποπροβλήματα. ("RG", "RA"), ("RG","R") και άλλα καλούνται πολλές φορές.

Για τη βελτιστοποίηση αυτού, έχουμε την προσέγγιση του Δυναμικός προγραμματισμός (DP).

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

Το γράφημα που φαίνεται παραπάνω είναι η αναδρομική μέθοδος. Κάθε αναδρομική συνάρτηση έχει μια βασική περίπτωση για να σπάσει την αναδρομή ή να αρχίσει να επιστρέφει από τη στοίβα της.

Για αυτήν την υλοποίηση, θα χρησιμοποιήσουμε μια θήκη βάσης. Ετσι το αλγόριθμος είναι σαν το εξής:

• Εάν όλα τα στοιχεία πριν από το τελευταίο στοιχείο έχουν ταίριασμα, τότε αυξήστε το μήκος κατά ένα και επιστρέψτε
• Περάστε δύο μοτίβα στη συνάρτηση και λάβετε τη μέγιστη τιμή της επιστροφής
• Αν ένα μοτίβο έχει μηδενικό μήκος, τότε δεν έχουμε καμία υποακολουθία για σύγκριση. Επιστρέψτε 0 σε αυτήν την περίπτωση. Αυτή είναι η βασική περίπτωση της αναδρομής.

Ψευδοκώδικας:

def lcs:
    input: pattern_1, pattern_2, len_1, len_2
if len_1 or len_2 is zero:
    then
return 0
if pattern_1[len_1 - 1] equals pattern_2[len_2 - 1]
then
return 1 + lcs(pattern_1, pattern_2,
    len_1 - 1, len_2 - 1)
else
    max of lcs(pattern_1, pattern_2, len_1 - 1, len_2),
    lcs(pattern_1, pattern_2, len_1, len_2 - 1)

Εφαρμογή στο C++

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int lcs(string pattern_1, string pattern_2, int len_1, int len_2) {
  if (len_1 == 0 || len_2 == 0)
    return 0;
  if (pattern_1[len_1 - 1] == pattern_2[len_2 - 1]) {
    return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1);
  } else {
    return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2), lcs(pattern_1, pattern_2, len_1, len_2 - 1));
  }
}
int main() {
  string pattern_1, pattern_2;
  pattern_1 = "RGBGARGA";
  pattern_2 = "BGRARG";
  cout<<"Length of LCS is: "<<lcs(pattern_1, pattern_2, pattern_1.size(), pattern_2.size())<<endl;
}

Παραγωγή:

Length of LCS is: 5

Εφαρμογή σε python

def lcs(pattern_1, pattern_2, len_1, len_2):
    if len_1 == 0 or len_2 == 0:
    return 0
if pattern_1[len_1 - 1] == pattern_2[len_2 - 1]:
    return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1)
else :
    return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2), lcs(pattern_1, pattern_2, len_1, len_2 - 1))
pattern_1 = "RGBGARGA"
pattern_2 = "BGRARG"
print("Lenght of LCS is: ", lcs(pattern_1, pattern_2, len(pattern_1), len(pattern_2)))

Παραγωγή:

Lenght of LCS is:  5

Μέθοδος δυναμικού προγραμματισμού της μεγαλύτερης κοινής υποακολουθίας (LCS)

Δυναμικός προγραμματισμός σημαίνει βελτιστοποίηση της απλής αναδρομικής μεθόδου. Για παράδειγμα, αν δούμε το αναδρομικό ή απλό γράφημα προσέγγισης, μπορούμε να δούμε ότι υπάρχουν πολλές ίδιες κλήσεις συναρτήσεων. Η μέθοδος Dynamic Programing καταγράφει όλους τους υπολογισμούς σε έναν πίνακα και τον χρησιμοποιεί όταν χρειάζεται.

Θα χρησιμοποιήσουμε έναν πίνακα 2D με διαστάσεις mxn, όπου m και n είναι τα μήκη του σχεδίου1 και του μοτίβου2.

Για Τρισδιάστατος πίνακας, μπορούμε να χρησιμοποιήσουμε δομές δεδομένων λίστας σε python ή δομές δεδομένων διανύσματος/πίνακα σε C++.

Ψευδοκωδικός για LCS με χρήση DP:

LCS(pattern_1, pattern_2):
    m = length of pattern_1 + 1
n = length of pattern_2 + 1
dp[n][m]
for i in range 0 to n + 1:
    for j in range 0 to m + 1:
    if i or j equals to 0:
    dp[i][j] = 0
else if pattern_1[i] == pattern_2[j]:
    dp[i]][j] = dp[i - 1][j - 1] + 1
else :
    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[n][m]

Ακολουθεί ο πίνακας LCS που χρησιμοποιείται ως δομή δεδομένων πίνακα 2D για την προσέγγιση δυναμικού προγραμματισμού.

Ας συζητήσουμε τη λογική που χρησιμοποιήσαμε εδώ. Τα βήματα είναι:

Βήμα 1) Εάν το i ή το j είναι μηδέν, παίρνουμε μια κενή συμβολοσειρά από τις δύο δεδομένες συμβολοσειρές και προσπαθούμε να βρούμε τις κοινές υποακολουθίες. Ωστόσο, καθώς η υποσυμβολοσειρά που παίρνουμε είναι κενή, το μήκος της δευτερεύουσας ακολουθίας είναι 0.

Βήμα 2) Εάν ταιριάζουν δύο χαρακτήρες, θα εκχωρήσουμε την τιμή στον δείκτη (i,j) αυξάνοντας το LCS που υπολογίστηκε προηγουμένως, το οποίο υπάρχει στον δείκτη (i-1,j-1) (από την προηγούμενη σειρά).

Βήμα 3) Εάν δεν ταιριάζει, τότε θα πάρουμε το μέγιστο LCS των δύο διπλανών ευρετηρίων. Και με αυτόν τον τρόπο, πρέπει να συμπληρώσουμε όλες τις τιμές στον πίνακα 2D.

Βήμα 4) Τέλος, θα επιστρέψουμε την τιμή του τελευταίου κελιού του πίνακα 2D.

Βασικά, όλη η τιμή στον πίνακα 2D περιέχει το μήκος των κοινών υποακολουθιών. Μεταξύ αυτών, το τελευταίο κελί περιέχει το μήκος της μεγαλύτερης κοινής υποακολουθίας.

Εφαρμογή στο C++

#include<iostream>
using namespace std;
int lcs(string pattern_1, string pattern_2) {
  int m = pattern_1.size();
  int n = pattern_2.size();
  // dp will store solutions as the iteration goes on
  int dp[n + 1][m + 1];
  for (int i = 0; i & lt; n + 1; i++) {
    for (int j = 0; j & lt; m + 1; j++) {
      if (i == 0 || j == 0) {
        dp[i][j] = 0;
      } else if (pattern_2[i - 1] == pattern_1[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[n][m];
}
int main() {
  string pattern_1 = "RGBGARGA";
  string pattern_2 = "BGRARG";
  cout<<"Length of LCS: "<<lcs(pattern_1, pattern_2)<<endl;
}

Παραγωγή:

Length of LCS: 5

Εφαρμογή στο Python

def lcs(pattern_1, pattern_2):
    m = len(pattern_1)
n = len(pattern_2)
# dp will store solutions as the iteration goes on
dp = [
    [None] * (n + 1) for item in range(m + 1)
]
for i in range(m + 1):
    for j in range(n + 1):
    if i == 0 or j == 0:
    dp[i][j] = 0
elif pattern_1[i - 1] == pattern_2[j - 1]:
    dp[i][j] = dp[i - 1][j - 1] + 1
else :
    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
pattern_1 = "RGBGARGA"
pattern_2 = "BGRARG"
print("Length of LCS: ", lcs(pattern_1, pattern_2))

Παραγωγή:

Length of LCS: 5

Έτσι, και οι δύο χορδές έχουν τη μεγαλύτερη κοινή υποακολουθία μήκους 5.

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

Σε αυτόν τον αλγόριθμο δυναμικού προγραμματισμού, χρησιμοποιούμε μια μήτρα 2D. Θα δοθούν δύο συμβολοσειρές (υποθέστε ότι και οι δύο έχουν μήκος n). Τότε ο χώρος που χρειάζεται στον πίνακα είναι nx n. Εάν οι συμβολοσειρές είναι αρκετά μεγάλες, θα χρειαστούμε μια βελτιστοποιημένη για μνήμη έκδοση της λύσης DP.

Η απλοποιημένη λογική που ελήφθη στον κώδικα είναι:

• Δηλώστε έναν πίνακα 2D DP[m][n].
• Συμπληρώστε την πρώτη γραμμή και την πρώτη στήλη του πίνακα DP με 0.
• Πάρτε i και j για την επανάληψη.
• Εάν το μοτίβο 1[i] ισούται με το μοτίβο 2[j], τότε ενημερώστε το DP[i][j] = DP[i-1][j-1] + 1
• Εάν το μοτίβο1[i] δεν ισούται με το μοτίβο2[j], τότε το DP[i][j] θα είναι η μέγιστη τιμή μεταξύ DP[i-1][j] και DP[i][j-1].
• Συνεχίστε μέχρι το i και το j να φτάσουμε στα m και n.
• Το τελευταίο στοιχείο ή DP[m-1][n-1], θα περιέχει το μήκος.

Εδώ, αντιμετωπίζεται ως DP[m-1][n-1], επειδή ο δείκτης πίνακα ξεκινά από 0.

Σύνοψη

• Η μέθοδος DP έχει μικρότερη χρονική πολυπλοκότητα. είναι O(mn), όπου m και n είναι το μήκος της συμβολοσειράς ή του πίνακα εισόδου.
• Η DP είναι μια πιο γρήγορη προσέγγιση από την αναδρομική, με τη χρονική πολυπλοκότητα O(n*2^m).
• Ο δυναμικός προγραμματισμός (DP) δεν είναι βελτιστοποιημένος στη μνήμη. Χρησιμοποιήσαμε έναν πίνακα 2D που έχει μήκος m*n. Άρα, η πολυπλοκότητα του χώρου είναι (m*n).
• Αναδρομική μέθοδος, σε ένα σενάριο χειρότερης περίπτωσης, η υψηλότερη μνήμη που θα καταλάβει θα είναι m+n, βασικά το συνολικό μήκος της συμβολοσειράς που έχει εισαχθεί.
• Ο σημερινός σύγχρονος υπολογιστής επαρκεί για να χειριστεί αυτή την ποσότητα μνήμης.