Bei Longest Common Sub­se­quence (LCS) handelt es sich um ein klas­si­sches Problem in der In­for­ma­tik. Ansätze zur Lösung des LCS-Problems tauchen oft in Pro­gram­mier-In­ter­views und Al­go­rith­men-Kursen auf.

Worum handelt es sich beim Longest-Common-Sub­se­quence-Problem?

Ziel der Aufgabe ist das Auffinden der längsten ge­mein­sa­men Teilfolge („Longest common sub­se­quence“) von zwei Sequenzen. Dabei ist eine Teilfolge („Sub­se­quence“) ab­ge­lei­tet aus einer Ori­gi­nal­fol­ge. Die Teilfolge hat dieselbe Rei­hen­fol­ge der Elemente, ggf. wurden jedoch einige Elemente entfernt. Ver­an­schau­li­chen wir uns das Prinzip an ein paar Bei­spie­len:

Sequenz X Sequenz Y LCS(X, Y)
FATHER VATER ATER
MOTHER MUTTER MTER
DAVID DANIEL DAI
Hinweis

Es besteht ein wichtiger Un­ter­schied zwischen der längsten ge­mein­sa­men Teilfolge und dem längsten ge­mein­sa­men Teil­string („Longest common substring“). Ein Teil­string darf im Gegensatz zur Teilfolge keine Lücken enthalten. Am Beispiel von „DAVID“ / „DANIEL“ wäre der längste ge­mein­sa­me Teil­string „DA“, da „I“ durch „V“ bzw. „N“ un­ter­bro­chen werden.

Was ist ein prak­ti­sches Beispiel für das LCS-Problem?

Bedeutung hat das Longest-Common-Sub­se­quence-Problem in allen Gebieten, in denen mit von­ein­an­der ab­stam­men­den Sequenzen ge­ar­bei­tet wird. Lö­sungs­an­sät­ze zum Auffinden der LCS kommen etwa zum Einsatz, um Texte auf Ge­mein­sam­kei­ten und Un­ter­schie­de zu un­ter­su­chen – so lassen sich Plagiate aufspüren. Auch das bekannte diff-Utility, das die Ver­än­de­run­gen an Quelltext-Dateien aufzeigt, basiert auf dem LCS-Problem.

In der Bio­in­for­ma­tik findet sich das Longest-Common-Sub­se­quence-Problem bei der Analyse von DNA-Sequenzen. Durch Mu­ta­tio­nen werden über die Zeit hinweg DNA-Basen an einzelnen Po­si­tio­nen verändert. Das Vor­han­den­sein einer langen ge­mein­sa­men Teilfolge zwischen zwei Sequenzen deutet auf eine hohe ge­ne­ti­sche Ver­wandt­heit hin. So lassen sich ge­ne­ti­sche Ent­wick­lun­gen zwischen Spezies über die Evolution hinweg nach­voll­zie­hen.

Lin­gu­is­ten und Lin­gu­is­tin­nen nutzen das Longest-Common-Sub­se­quence-Problem, um die Ent­wick­lung von Sprachen über die Jahr­hun­der­te hinweg zu un­ter­su­chen. Finden sich zwei Worte aus ver­schie­de­nen Sprachen, die dieselbe Bedeutung haben und eine lange ge­mein­sa­me Teilfolge aufweisen, deutet dies auf einen ge­mein­sa­men Ursprung hin. So lässt sich aus der Über­ein­stim­mung der Buch­sta­ben auf die his­to­ri­sche Ent­wick­lung schließen.

Wie funk­tio­nie­ren Lö­sungs­an­sät­ze für das Longest-Common-Sub­se­quence-Problem?

Zunächst lässt sich das LCS-Problem mit einem „naiven“ Ansatz lösen. Dabei handelt es sich um den na­he­lie­gen­den Ansatz ohne Op­ti­mie­rung oder spezielle Her­an­ge­hens­wei­se. Man ermittelt alle Teil­fol­gen der beiden Sequenzen und findet die längste Teilfolge, die beide Sequenzen gemeinsam haben. Leider ist dieser Ansatz nicht effizient und eignet sich daher nur für kurze Sequenzen.

Wir zeigen im Folgenden drei ef­fi­zi­en­te Lö­sungs­an­sät­ze für das LCS-Problem:

  1. Re­kur­si­ver Ansatz
  2. Op­ti­mie­rung mittels Me­moi­sa­ti­on
  3. Dy­na­mi­sche Pro­gram­mie­rung

Allen Ansätzen ist gemein, dass sie in Bezug auf die beiden Sequenzen drei Fälle un­ter­schei­den:

  • Letzter Buchstabe ist gleich.
  • Letzter Buchstabe ist nicht gleich.
  • Die Länge einer der Sequenzen ist null.

Die Ansätze un­ter­schei­den sich jeweils in Zeit­kom­ple­xi­tät (asym­pto­ti­scher Laufzeit) und Platz­kom­ple­xi­tät (Spei­cher­be­darf):

Ansatz Laufzeit Spei­cher­be­darf
Naiver Ansatz O(n * n²) O(n)
Re­kur­si­ver Ansatz O(n²) O(1)
Op­ti­mie­rung mittels Me­moi­sa­ti­on O(n *m) O(n* m)
Dy­na­mi­sche Pro­gram­mie­rung O(n *m) O(n* m)
Hinweis

Die im Folgenden dar­ge­stell­ten Al­go­rith­men ermitteln jeweils die Länge der längsten ge­mein­sa­men Teilfolge. Es gibt ggf. mehrere konkrete Teil­fol­gen dieser Länge, die sich durch weitere Schritte ermitteln lassen.

Longest Common Sub­se­quence rekursiv ermitteln

Bei Be­trach­tung des LCS-Problems zeigt sich, dass dieses eine „optimal sub­s­truc­tu­re“ aufweist. Das bedeutet, dass sich das Problem auf Un­ter­pro­ble­me re­du­zie­ren lässt. Zur Lösung bietet sich ein re­kur­si­ver Ansatz an. Wir zeigen die Im­ple­men­ta­ti­on des Al­go­rith­mus in drei beliebten Pro­gram­mier­spra­chen.

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
KI-Assistent kostenlos – Ihr smarter All­tags­hel­fer
  • DSGVO-konform & sicher gehostet in Deutsch­land
  • Pro­duk­ti­vi­tät steigern – weniger Aufwand, mehr Output
  • Direkt im Browser starten – ohne In­stal­la­ti­on

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

Op­ti­mie­rung des re­kur­si­ven Ansatzes mittels Me­moi­sa­ti­on

Bei weiterer Be­trach­tung des re­kur­si­ven Ansatzes zeigt sich, dass über­lap­pen­de Teil­fol­gen berechnet werden. Diese Ei­gen­schaft, die als „over­lap­ping sub­pro­blems“ be­zeich­net wird, ist von der Fibonacci-Folge bekannt. Auch hier werden rekursiv Teile auf dem Weg zur Lösung immer wieder berechnet. Um den Prozess ef­fi­zi­en­ter zu gestalten, bietet es sich an, Me­moi­sa­ti­on zu verwenden. Anders gesagt cachen wir die bereits be­rech­ne­ten Un­ter­pro­ble­me in einer zwei­di­men­sio­na­len Matrix.

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

Dy­na­mi­sche Pro­gram­mie­rung für Longest Common Sub­se­quence

Die dy­na­mi­sche Pro­gram­mie­rung ist eine nicht­re­kur­si­ve Technik zur Lösung von Op­ti­mie­rungs­pro­ble­men, indem sie diese in kleinere Teil­pro­ble­me un­ter­teilt und im Anschluss „bottom-up“ löst. Dy­na­mi­sche Pro­gram­mie­rung wird u. a. als Lö­sungs­an­satz für Path­fin­ding-Al­go­rith­men angewandt. Das Problem der Longest Common Sub­se­quence lässt sich ebenfalls durch dy­na­mi­sche Pro­gram­mie­rung lösen, wobei eine zwei­di­men­sio­na­le Matrix zum Einsatz kommt.

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++
Zum Hauptmenü