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

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

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

Ακολουθία X Ακολουθία Y LCS(X, Y)
FATHER MATTER ATER
MOTHER HERBAL HER
DAVID DANIEL DAI
Note

Υπάρχει μια σημαντική διαφορά μεταξύ της μακρύτερης κοινής υποακολούθου και της μακρύτερης κοινής υποσειράς, η οποία συνίσταται στο ότι μια υποσειρά δεν μπορεί να έχει κενά. Στο παράδειγμα των λέξεων «DAVID» και «DANIEL», η μακρύτερη κοινή υποσειρά θα ήταν «DA», καθώς το «I» χωρίζεται από τα «V» και «N».

Υπάρχουν πρακτικά παραδείγματα του προβλήματος LCS;

Το πρόβλημα της μακρύτερης κοινής υποακολούθου είναι ένα σημαντικό ζήτημα σε όλους τους τομείς όπου χρησιμοποιούνται ακολουθίες που προέρχονται η μία από την άλλη. Υπάρχουν ορισμένοι τρόποι για να βρείτε την LCS, ώστε να διαπιστώσετε αν υπάρχουν ομοιότητες ή διαφορές και, με τη σειρά σας, να ανακαλύψετε τυχόν λογοκλοπή. Το γνωστό βοηθητικό πρόγραμμα «diff», το οποίο ελέγχει τις αλλαγές στα αρχεία κειμένου πηγής, βασίζεται στο πρόβλημα της LCS.

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

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

Ποιες είναι οι λύσεις στο πρόβλημα της μακρύτερης κοινής υποακολούθου;

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

Παρακάτω θα βρείτε τρεις αποτελεσματικές λύσεις για το πρόβλημα LCS:

  1. Αναδρομική προσέγγιση
  2. Βελτιστοποίηση μέσω απομνημόνευσης
  3. Δυναμικός προγραμματισμός

Όλες οι προσεγγίσεις έχουν κοινό το γεγονός ότι, όσον αφορά τις δύο ακολουθίες, διαφέρουν σε τρεις περιπτώσεις:

  • Το τελευταίο γράμμα είναι το ίδιο.
  • Το τελευταίο γράμμα δεν είναι το ίδιο.
  • Το μήκος μιας από τις ακολουθίες είναι μηδέν.

Οι προσεγγίσεις διαφέρουν μεταξύ τους ως προς την χρονική πολυπλοκότητα (ασυμπτωτικός χρόνος εκτέλεσης) και την χωρική πολυπλοκότητα (χρήση μνήμης):

Προσέγγιση Διάρκεια Μνήμη
Αφελής προσέγγιση O(n * n²) O(n)
Αναδρομική προσέγγιση O(n²) O(1)
Βελτιστοποίηση μέσω απομνημόνευσης O(n *m) O(n* m)
Δυναμικός προγραμματισμός O(n *m) O(n* m)
Note

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

Αναδρομικός προσδιορισμός της μακρύτερης κοινής υποακολούθου

Αν εξετάσετε το πρόβλημα LCS, θα διαπιστώσετε ότι έχει μια «βέλτιστη υποδομή». Αυτό σημαίνει ότι το πρόβλημα μπορεί να αναχθεί σε υποπροβλήματα. Ως λύση μπορείτε να χρησιμοποιήσετε μια αναδρομική προσέγγιση. Παρακάτω θα βρείτε μερικά παραδείγματα αλγορίθμων για την υλοποίηση αυτού του προβλήματος σε τρεις από τις πιο κοινές γλώσσες προγραμματισμού.

Python

def lcs(X, Y, m, n):
    # Base case
    if m == 0 or n == 0:
        return 0
    # Last elements are equal
    elif X[m-1] == Y[n-1]:
        return 1 + lcs(X, Y, m-1, n-1)
    # Last elements differ
    else:
        return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n))
# Let's test
X, Y = "DANIEL", "DAVID"
lcs_len = lcs(X, Y, len(X), len(Y))
print(f"Length of LCS is: {lcs_len}")
python

Java

import java.io.*;
class LCS {
    public static int lcs(String A, String B, int m, int n)
    {
        // Base case
        if (m == 0 || n == 0)
            return 0;
        // Last elements are equal
        if (A.charAt(m - 1) == B.charAt(n - 1))
            return 1 + lcs(A, B, m - 1, n - 1);
        // Last elements differ
        else
            return Math.max(lcs(A, B, m, n - 1),
             lcs(A, B, m - 1, n));
    }
    
    // Let's test
    public static void main(String[] args)
        {
            String X = "DAVID";
            String Y = "DANIEL";
            int lcsLength = LCS.lcs(X, Y, X.length(), Y.length());
            System.out.println("Length of LCS is: " + lcsLength);
        }
}
java

C++

#include <iostream>
using namespace std;
int lcs(string X, string Y, int m, int n)
{
    // Base case
    if (m == 0 || n == 0) {
        return 0;
    }
    // Last elements are equal
    if (X[m - 1] == Y[n - 1]) {
        return 1 + lcs(X, Y, m - 1, n - 1);
    }
    // Last elements differ
    else {
        return max(lcs(X, Y, m, n - 1), lcs(X, Y, m - 1, n));
    }
}
// Let's test
int main()
{
    // Initialize variables
    string X = "DAVID";
    string Y = "DANIEL";
    // Compute and output length of LCS
    cout << "Length of LCS is " << lcs(X, Y, X.size(), Y.size());
    return 0;
}
c++

Βελτιστοποίηση της αναδρομικής προσέγγισης με χρήση απομνημόνευσης

Εξετάζοντας ξανά την αναδρομική προσέγγιση, μπορείτε να δείτε ότι υπολογίζονται τα επικαλυπτόμενα μέρη. Αυτά τα χαρακτηριστικά, που ονομάζονται «επικαλυπτόμενα υποπροβλήματα», είναι γνωστά από τις ακολουθίες Fibonacci. Και σε αυτή την περίπτωση, οι αναδρομικές ακολουθίες υπολογίζονται συνεχώς για την εξεύρεση λύσης. Για να γίνει η διαδικασία πιο αποτελεσματική, αξίζει να χρησιμοποιήσετε τη μέθοδο της απομνημόνευσης. Με άλλα λόγια, μπορείτε να αποθηκεύσετε τα υποπροβλήματα που έχουν ήδη υπολογιστεί σε έναν δισδιάστατο πίνακα.

Python

def lcs(X, Y, m, n, table):
    
    # Base case
    if (m == 0 or n == 0):
        return 0
    # Already computed value at given position
    if (table[m][n] != -1):
        return table[m][n]
    # Last elements are equal
    if X[m - 1] == Y[n - 1]:
        table[m][n] = 1 + lcs(X, Y, m - 1, n - 1, table)
    # Last elements differ
    else:
        table[m][n] = max(lcs(X, Y, m, n - 1, table), lcs(X, Y, m - 1, n, table))
    return table[m][n]
# Let's test
X = "DAVID"
Y = "DANIEL"
m, n = len(X), len(Y)
# Initialize table fields to `-1`
table = [[-1 for i in range(n + 1)] for j in range(m + 1)]
// Compute and output length of LCS
print(f"Length of LCS is: {lcs(X, Y, m, n, table)}")
python

Java

import java.io.*;
class LCS {
    public static int lcs(String X, String Y, int m, int n, int[][] table) {
        // Base case
        if (m == 0 || n == 0) {
            return 0;
        }
        // Already computed value at given position
        if (table[m][n] != -1) {
            return table[m][n];
        }
        // Last elements are equal
        if(X.charAt(m - 1) == Y.charAt(n - 1)) {
            table[m][n] = 1 + lcs(X, Y, m - 1, n - 1, table);
            return table[m][n];
        }
        // Last elements differ
        else {
            table[m][n] = Math.max(lcs(X, Y, m, n - 1, table),lcs(X, Y, m - 1, n, table));
            return table[m][n];
        }
    }
    // Let's test
    public static void main(String args[]){
        // Initialize variables
        String X = "DAVID";
        String Y = "DANIEL";
        int m = X.length();
        int n = Y.length();
        int[][] table = new int[m + 1][n + 1];
        
        // Initialize table fields to `-1`
        for(int i=0; i < m + 1; i++) {
            for(int j=0; j < n + 1; j++) {
                table[i][j] = -1;
            }
        }
        // Compute and output length of LCS
        int lcsLength = lcs(X, Y, m, n, table);
        System.out.println("Length of LCS is: " + lcsLength);
    }
}
java

C++

#include <bits/stdc++.h>
using namespace std;
int lcs(char *X, char* Y, int m, int n, vector<vector<int>>& table)
{
    // Base case
    if (m == 0 || n == 0)
        return 0;
    // Already computed value at given position
    if (table[m][n] != -1) {
        return table[m][n];
    }
    // Last elements are equal
    if (X[m - 1] == Y[n - 1]) {
        table[m][n] = 1 + lcs(X, Y, m - 1, n - 1, table);
        return table[m][n];
    }
    // Last elements differ
    else { 
        table[m][n] = max(lcs(X, Y, m, n - 1, table), lcs(X, Y, m - 1, n, table));
        return table;
    }
}
// Let's test
int main()
{
    // Initialize variables
    char X[] = "DAVID";
    char Y[] = "DANIEL";
    int m = strlen(X);
    int n = strlen(Y);
    // Initialize table with `-1`
    vector<vector<int>> table(m + 1, vector<int>(n + 1, -1));
    
    // Compute and output length of LCS
    cout << "Length of LCS is: " << lcs(X, Y, m, n, table);
    return 0;
}
c++

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

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

Python

def lcs(X , Y, m, n): 
    
    # Initialize dynamic programming table fields to `None`
    table = [[None] * (n + 1) for _ in range(m + 1)]
    
    # Compute table values
    for i in range(m + 1):
        for j in range(n + 1):
            # Base case
            if i == 0 or j == 0 :
                table[i][j] = 0
            # Last elements are equal
            elif X[i - 1] == Y[j - 1]:
                table[i][j] = table[i - 1][j - 1]+ 1
            # Last elements differ
            else:
                table[i][j] = max(table[i - 1][j] , table[i][j - 1])
    
    return table[m][n]
# Let's test
X = "DAVID"
Y = "DANIEL"
# Compute and output length of LCS
lcs_len = lcs(X, Y, len(X), len(Y))
print(f"Length of LCS is: {lcs_len}")
python

Java

import java.io.*;
class LCS {
    public static int lcs(String X, String Y, int m, int n)
    {
        // Initialize dynamic programming table fields
        int table[][] = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                // Base case
                if (i == 0 || j == 0)
                    table[i][j] = 0;
                // Last elements are equal
                else if (X.charAt(i - 1) == Y.charAt(j - 1))
                    table[i][j] = table[i - 1][j - 1] + 1;
                // Last elements differ
                else
                    table[i][j] = Math.max(table[i - 1][j], table[i][j - 1]);
            }
        }
        return table[m][n];
    }
    // Let's test
    public static void main(String args[]){
        // Initialize variables
        String X = "DAVID";
        String Y = "DANIEL";
        int m = X.length();
        int n = Y.length();
        // Compute and output length of LCS
        int lcsLength = lcs(X, Y, m, n);
        System.out.println("Length of LCS is: " + lcsLength);
    }
}
java

C++

#include <bits/stdc++.h>
using namespace std;
int lcs(string X, string Y, int m, int n) {
	// Initialize dynamic programming table
	int table[m + 1][n + 1];
	// Compute table values
	for (int i = 0; i <= m; i++) {
		for (int j = 0; j <= n; j++) {
			// Base case
			if (i == 0 || j == 0)
				table[i][j] = 0;
			// Last elements are equal
			else if (X[i - 1] == Y[j - 1])
				table[i][j] = table[i - 1][j - 1] + 1;
			// Last elements differ
			else
				table[i][j] = max(table[i - 1][j], table[i][j - 1]);
		}
	}
	return table[m][n];
}
// Let's test
int main() {
  // Initialize variables
  string X = "DAVID";
  string Y = "DANIEL";
  int m = X.size();
  int n = Y.size();
  // Compute and output length of LCS
  cout << "Length of LCS is " << lcs(X, Y, m, n);
  return 0;
}
c++
Go to Main Menu