Garākās kopējās ap­akš­sek­ven­ces (LCS) ir tipiska problēma IT jomā. LCS problēmas ri­si­nā­ša­nas pieejas bieži tiek iz­man­to­tas prog­ram­mē­tā­ju in­ter­vi­jās un algoritmu kursos.

Kāda ir garākā kopīgā ap­akš­sek­ven­ce?

Mērķis ir atrast garāko kopīgo ap­akš­sek­ven­ci divās sekvencēs. Šeit ap­akš­sek­ven­ce ir at­va­si­nā­ta no sekvences. Ap­akš­sek­ven­cei ir tāds pats elementu secības kārtība, dažos gadījumos, kad elementi tiek noņemti. Ap­ska­tī­sim dažus piemērus, lai labāk izprastu šo principu:

Sekvence X Sekvence Y LCS(X, Y)
FATHER MATTER ATER
MOTHER HERBAL HER
DAVID DANIEL DAI
Note

Ir svarīga atšķirība starp garāko kopīgo ap­akš­sek­ven­ci un garāko kopīgo ap­akš­vir­kni, jo ap­akš­virknei var nebūt nekādu atstarpju. Piemērā ar vārdiem „DAVID” un „DANIEL” garākā kopīgā ap­akš­virkne būtu „DA”, jo „I” ir atdalīts ar „V” un „N”.

Vai ir kādi praktiski piemēri par LCS problēmu?

Garākās kopējās ap­akš­sek­ven­ces problēma ir svarīgs jautājums visās jomās, kurās tiek iz­man­to­tas sav­star­pē­ji saistītas sekvences. Ir noteikti veidi, kā atrast LCS, lai redzētu, vai pastāv līdzības vai at­šķi­rī­bas, un, savukārt, atklātu jebkādu plaģiātu. Pa­zīs­ta­mais rīks “diff”, kas pārbauda izmaiņas avota teksta failos, ir balstīts uz LCS problēmu.

Bioin­for­mā­ti­kā garākās kopējās ap­akš­sek­ven­ces problēma bieži tiek izmantota, ana­li­zē­jot DNS sekvences. DNS bāzes laika gaitā mainās noteiktās pozīcijās mutāciju dēļ. Garas kopējās ap­akš­sek­ven­ces klātbūtne divās sekvencēs liecina par ģenētisku saistību. Tas ļauj mums izsekot sugu evolūciju, pa­tei­co­ties ģe­nē­tis­ka­jai at­tīs­tī­bai.

Lingvisti var izmantot garākās kopīgās ap­akš­sek­ven­ces problēmu, lai pētītu valodas attīstību gadsimtu gaitā. Ja ir divi vārdi no dažādām valodām, kuriem ir vienāda nozīme un gara kopīga ap­akš­sek­ven­ce, tas liecina, ka tiem ir vienāds sakne un eti­mo­lo­ģi­ja. Tādā gadījumā to var uzskatīt par līdzīgu vēs­tu­ris­ko attīstību.

Kādi ir ri­si­nā­ju­mi garākās kopējās ap­akš­sek­ven­ces problēmai?

Pirmkārt, LCS problēmu var atrisināt ar naivu pieeju. Tā ir vienkārša pieeja, ne­iz­man­to­jot nekādas op­ti­mi­zā­ci­jas vai īpašas metodes. Lai to izdarītu, vienkārši aprēķina visas divu secību ap­akš­se­cī­bas un atrod garāko kopīgo ap­akš­se­cī­bu. Diemžēl šī pieeja nav ļoti efektīva un tādēļ ir piemērota tikai īsām secībām.

Zemāk at­ra­dī­siet trīs efektīvus ri­si­nā­ju­mus LCS problēmai:

  1. Rekursīvā pieeja
  2. Op­ti­mi­zā­ci­ja ar me­moi­sā­ci­ju
  3. Dinamiskā prog­ram­mē­ša­na

Visām pieejām ir kopīgs tas, ka attiecībā uz abām secībām tās atšķiras trīs gadījumos:

  • Pēdējā burta ir tāds pats.
  • Pēdējā burta nav tāds pats.
  • Vienas no secībām garums ir nulle.

Katra pieeja atšķiras ar savu laika sa­rež­ģī­tī­bu (asim­pto­tis­ko izpildes laiku) un telpas sa­rež­ģī­tī­bu (atmiņas iz­man­to­ša­nu):

Pieeja Darba laiks Atmiņa
Naivā pieeja O(n * n²) O(n)
Rekursīvā pieeja O(n²) O(1)
Op­ti­mi­zā­ci­ja ar me­moi­sā­ci­ju O(n *m) O(n* m)
Dinamiskā prog­ram­mē­ša­na O(n *m) O(n* m)
Note

Zemāk iz­klās­tī­tie algoritmi aprēķina garāko kopīgo ap­akš­sek­ven­ci. Ja pie­mē­ro­jams, ir vairākas šāda garuma ap­akš­sek­ven­ces, kuras var noteikt, iz­man­to­jot citus soļus.

Ilgākās kopējās ap­akš­sek­ven­ces rekursīva no­teik­ša­na

Ja aplūkojat LCS problēmu, varat redzēt, ka tai ir „optimāla ap­akš­struk­tū­ra”. Tas nozīmē, ka problēmu var sadalīt ap­akš­prob­lē­mās. Kā ri­si­nā­ju­mu varat izmantot rekursīvu pieeju. Zemāk atrodami daži algoritmu piemēri, lai to īstenotu trīs visbiežāk lie­to­ta­jās prog­ram­mē­ša­nas valodās.

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++

Re­kur­sī­vās pieejas op­ti­mi­zē­ša­na, iz­man­to­jot me­moi­zā­ci­ju

Atkal aplūkojot rekursīvo pieeju, var redzēt, ka tiek ap­rē­ķi­nā­tas pār­klā­jo­šās daļas. Šīs īpašības, ko sauc par „pār­klā­jo­šām ap­akš­prob­lē­mām”, ir pa­zīs­ta­mas no Fibonači sekvencēm. Arī šajā gadījumā re­kur­sī­vās sekvences tiek ne­pār­trauk­ti ap­rē­ķi­nā­tas, lai iegūtu ri­si­nā­ju­mu. Lai padarītu procesu efek­tī­vā­ku, ir vērts izmantot me­moi­sā­ci­ju. Citiem vārdiem sakot, jūs varat kešēt ap­akš­prob­lē­mas, kas jau ir ap­rē­ķi­nā­tas divdi­men­sio­nā­lā matricā.

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++

Dinamiskā prog­ram­mē­ša­na garākajai kopīgajai ap­akš­sek­ven­ci­jai

Dinamiskā prog­ram­mē­ša­na ir ne­re­kur­sīvs veids, kā risināt op­ti­mi­zā­ci­jas problēmas, sadalot tās mazākās ap­akš­prob­lē­mās un pēc tam risinot tās „no apakšas uz augšu”. Cita starpā dinamiskā prog­ram­mē­ša­na tiek izmantota kā ri­si­nā­jums ceļu mek­lē­ša­nas al­go­rit­miem. Garākās kopējās ap­akš­sek­ven­ces problēmu var risināt arī ar di­na­mis­kās prog­ram­mē­ša­nas palīdzību, iz­man­to­jot divdi­men­sio­nā­lu matricu.

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