Kas yra ilgiausios bendrosios posekvencijos problema?

Contents

Ilgiausios bendrosios posekvencijos (LCS) yra tipinė IT problema. LCS problemos sprendimo būdai dažnai pasirodo programuotojų ir algoritmų kursų pokalbiuose.

Koks yra ilgiausias bendras posekvencija?

Tikslas yra rasti ilgiausią bendrą posekvenciją dviejose sekvencijose. Tai yra vieta, kur posekvencija yra išvedama iš sekvencijos. Posekvencija turi tą pačią elementų tvarką, kai kuriais atvejais, kai elementai yra pašalinami. Pažvelkime į keletą pavyzdžių, kad geriau suprastume šį principą:

Sekvencija `X`	Sekvencija `Y`	`LCS(X, Y)`
`FATHER`	`MATTER`	`ATER`
`MOTHER`	`HERBAL`	`HER`
`DAVID`	`DANIEL`	`DAI`

Note

Yra svarbus skirtumas tarp ilgiausios bendrosios posekvencijos ir ilgiausios bendrosios posekvencijos, nes posekvencija negali turėti jokių tarpų. Pavyzdyje „DAVID“ ir „DANIEL“ ilgiausia bendroji posekvencija būtų „DA“, nes „I“ yra atskirta „V“ ir „N“.

Ar yra kokių nors praktinių LCS problemos pavyzdžių?

Ilgiausios bendrosios sekos problema yra svarbus klausimas visose srityse, kuriose naudojamos viena iš kitos kilusios sekos. Yra tam tikri būdai rasti LCS, kad būtų galima pamatyti, ar yra panašumų ar skirtumų, ir atitinkamai aptikti bet kokį plagijavimą. Gerai žinoma „diff“ programa, kuri tikrina šaltinio tekstinių failų pakeitimus, yra pagrįsta LCS problema.

Bioinformatikoje ilgiausios bendrosios posekvencijos problema dažnai naudojama analizuojant DNR sekas. DNR bazės tam tikrose pozicijose laikui bėgant keičiasi dėl mutacijų. Ilgos bendrosios posekvencijos buvimas dviejose sekose rodo genetinį ryšį. Tai leidžia mums atsekti rūšių evoliuciją pagal genetinę raidą.

Lingvistai taip pat gali naudoti ilgiausios bendrosios sekos problemą, kad ištirtų kalbos raidą per šimtmečius. Jei turite du žodžius iš skirtingų kalbų, kurie turi tą pačią reikšmę ir ilgą bendrąją seką, tai rodo, kad jie turi tą pačią šaknį ir etimologiją. Tai būtų laikoma panašia istorine raida.

Kokie yra ilgiausios bendrosios posekvencijos problemos sprendimai?

Pirmiausia, LCS problemą galima išspręsti naiviu metodu. Tai paprastas metodas, nenaudojantis jokių optimizacijų ar specialių metodų. Tam reikia tiesiog apskaičiuoti visas dviejų sekų posekes ir rasti ilgiausią bendrą posekę. Deja, šis metodas nėra labai efektyvus, todėl tinka tik trumpoms sekoms.

Žemiau rasite tris veiksmingus LCS problemos sprendimus:

Rekursyvusis metodas
Optimizavimas naudojant atminties funkciją
Dinaminis programavimas

Visiems metodams būdinga tai, kad, atsižvelgiant į šias dvi sekas, jie skiriasi trimis atvejais:

Paskutinė raidė yra ta pati.
Paskutinė raidė nėra tokia pati.
Vienos sekos ilgis yra nulis.

Kiekvienas iš šių metodų skiriasi savo laiko sudėtingumu (asimptotiniu vykdymo laiku) ir erdvės sudėtingumu (atminties naudojimu):

Prieiga	Trukmė	Atmintis
Naivus požiūris	`O(n * n²)`	`O(n)`
Rekursyvus metodas	`O(n²)`	`O(1)`
Optimizavimas naudojant atminties funkciją	`O(n *m)`	`O(n* m)`
Dinaminis programavimas	`O(n *m)`	`O(n* m)`

Note

Toliau pateikti algoritmai apskaičiuoja ilgiausios bendrosios posekvencijos ilgį. Jei taikoma, yra keletas šios trukmės nustatytų posekvencijų, kurias galima nustatyti naudojant kitus veiksmus.

Ilgiausios bendrosios posekvencijos rekursinis nustatymas

Jei pažvelgsite į LCS problemą, pamatysite, kad ji turi „optimalų substruktūrą“. Tai reiškia, kad problema gali būti suskaidyta į smulkesnes problemas. Kaip sprendimą galite naudoti rekursyvų metodą. Toliau pateikiami keletas algoritmų pavyzdžių, kaip tai įgyvendinti trimis populiariausiomis programavimo kalbomis.

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

Rekursinio metodo optimizavimas naudojant memizaciją

Dar kartą pažvelgus į rekursyvųjį metodą, matyti, kad persidengiančios dalys yra apskaičiuojamos. Šios savybės, vadinamos „persidengiančiomis dalinėmis problemomis“, yra žinomos iš Fibonačio sekų. Šiuo atveju taip pat rekursyvios sekos yra nuolat apskaičiuojamos sprendimui rasti. Kad procesas būtų efektyvesnis, verta naudoti memojavimą. Kitaip tariant, jau apskaičiuotas dalines problemas galima įrašyti į dvimatę 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++

Dinaminis programavimas ilgiausiam bendram posekvencijai

Dinaminis programavimas yra nerekursyvus būdas spręsti optimizavimo problemas, jas suskaidant į mažesnes dalines problemas ir tada sprendžiant jas „iš apačios į viršų“. Be kita ko, dinaminis programavimas taikomas kaip sprendimas kelių paieškos algoritmams. Ilgiausios bendrosios pakartotinės sekos problema taip pat gali būti sprendžiama naudojant dinaminį programavimą, kai naudojama dvimatė matrica.

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

Kas yra il­giau­sios bend­ro­sios po­sek­ven­ci­jos problema?

Koks yra il­giau­sias bendras po­sek­ven­ci­ja?

Ar yra kokių nors praktinių LCS problemos pavyzdžių?

Kokie yra il­giau­sios bend­ro­sios po­sek­ven­ci­jos problemos spren­di­mai?

Il­giau­sios bend­ro­sios po­sek­ven­ci­jos re­kur­si­nis nu­sta­ty­mas

Python

Java

C++

Re­kur­si­nio metodo op­ti­mi­za­vi­mas naudojant me­mi­za­ci­ją

Python

Java

C++

Dinaminis prog­ra­ma­vi­mas il­giau­siam bendram po­sek­ven­ci­jai

Python

Java

C++

Kas yra ilgiausios bendrosios posekvencijos problema?

Koks yra ilgiausias bendras posekvencija?

Kokie yra ilgiausios bendrosios posekvencijos problemos sprendimai?

Ilgiausios bendrosios posekvencijos rekursinis nustatymas

Rekursinio metodo optimizavimas naudojant memizaciją

Dinaminis programavimas ilgiausiam bendram posekvencijai