Lengste felles delsekvenser (LCS) er et typisk problem innen IT. Tilnærminger for å løse LCS-problemet dukker ofte opp i intervjuer med programmerere og i algoritmekurs.

Hva er den lengste felles delsekvensen?

Målet er å finne den lengste felles delsekvensen i to sekvenser. Her er en delsekvens avledet fra en sekvens. Delsekvensen har samme elementære rekkefølge, i noen tilfeller når elementer fjernes. La oss se på noen eksempler for å få en bedre forståelse av prinsippet:

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

Det er en viktig forskjell mellom den lengste felles delsekvensen og den lengste felles delstrengen, nemlig at en delstreng ikke kan ha noen mellomrom. I eksemplet med «DAVID» og «DANIEL» vil den lengste felles delstrengen være «DA», siden «I» er adskilt av «V» og «N».

Er det noen praktiske eksempler på LCS-problemet?

Problemet med lengste felles delsekvens er et viktig tema på alle områder hvor sekvenser som stammer fra hverandre brukes. Det finnes visse måter å finne LCS på for å se om det er likheter eller forskjeller, og dermed oppdage eventuelle plagiater. Det velkjente verktøyet «diff», som sjekker endringer i kildetekstfiler, er basert på LCS-problemet.

I bioinformatikk brukes ofte problemet med den lengste felles delsekvensen når man analyserer DNA-sekvenser. DNA-baser endres i visse posisjoner over tid på grunn av mutasjoner. Tilstedeværelsen av en lang felles delsekvens i to sekvenser kan tyde på et genetisk slektskap. Dette kan gjøre det mulig for oss å spore evolusjonen mellom arter takket være genetisk utvikling.

Lingvister kan også bruke problemet med den lengste felles delsekvensen til å forske på språkutviklingen gjennom århundrene. Hvis du har to ord fra forskjellige språk som har samme betydning og en lang felles delsekvens, tyder det på at de har samme rot og etymologi. Dette vil da bli ansett som en lignende historisk utvikling.

Hva er løsningene på problemet med den lengste felles delsekvensen?

Først og fremst kan du løse LCS-problemet med en naiv tilnærming. Dette er en enkel tilnærming uten bruk av optimaliseringer eller spesielle metoder. For å gjøre dette beregner du ganske enkelt alle delsekvenser fra to sekvenser og finner den lengste felles delsekvensen. Dessverre er denne tilnærmingen ikke særlig effektiv og er derfor kun egnet for korte sekvenser.

Nedenfor finner du tre effektive løsninger på LCS-problemet:

  1. Rekursiv tilnærming
  2. Optimalisering gjennom memoisation
  3. Dynamisk programmering

Det alle tilnærmingene har til felles, er at de i forhold til de to sekvensene skiller seg fra hverandre i tre tilfeller:

  • Den siste bokstaven er den samme.
  • Den siste bokstaven er ikke den samme.
  • Lengden på en av sekvensene er null.

Tilnærmingene skiller seg fra hverandre når det gjelder tidskompleksitet (asymptotisk kjøretid) og romkompleksitet (minnebruk):

Tilnærming Kjøretid Minne
Naiv tilnærming O(n * n²) O(n)
Rekursiv tilnærming O(n²) O(1)
Optimalisering via memoisation O(n *m) O(n* m)
Dynamisk programmering O(n *m) O(n* m)
Note

Algoritmene nedenfor beregner alle lengden på den lengste felles delsekvensen. Det finnes, hvis aktuelt, flere delsekvenser av denne lengden som kan bestemmes ved hjelp av andre trinn.

Rekursiv bestemmelse av den lengste felles delsekvensen

Hvis du ser på LCS-problemet, kan du se at det har en «optimal understruktur». Dette betyr at problemet kan reduseres til delproblemer. Som løsning kan du bruke en rekursiv tilnærming. Nedenfor finner du noen eksempler på algoritmer for å implementere dette i tre av de vanligste programmeringsspråkene.

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

Optimalisering av den rekursive tilnærmingen ved hjelp av memoisation

Når du ser på den rekursive tilnærmingen igjen, kan du se at de overlappende delene beregnes. Disse egenskapene, kalt «overlappende delproblemer», er kjent fra Fibonacci-sekvenser. Også i dette tilfellet beregnes rekursive sekvenser kontinuerlig for å finne en løsning. For å gjøre prosessen mer effektiv, er det lurt å bruke memoisation. Med andre ord kan du cache de delproblemene som allerede er beregnet i en todimensjonal matrise.

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

Dynamisk programmering for den lengste felles delsekvensen

Dynamisk programmering er en ikke-rekursiv metode for å løse optimaliseringsproblemer ved å dele dem opp i mindre delproblemer og deretter løse dem «nedenfra og opp». Dynamisk programmering brukes blant annet som en løsning for banesøkingsalgoritmer. Problemet med lengste felles delsekvens kan også løses ved hjelp av dynamisk programmering når man bruker en todimensjonal matrise.

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