Das Longest-Common-Subsequence-Problem

Bei Longest Common Subsequence (LCS) handelt es sich um ein klassisches Problem in der Informatik. Ansätze zur Lösung des LCS-Problems tauchen oft in Programmier-Interviews und Algorithmen-Kursen auf.

Worum handelt es sich beim Longest-Common-Subsequence-Problem?

Ziel der Aufgabe ist das Auffinden der längsten gemeinsamen Teilfolge („Longest common subsequence“) von zwei Sequenzen. Dabei ist eine Teilfolge („Subsequence“) abgeleitet aus einer Originalfolge. Die Teilfolge hat dieselbe Reihenfolge der Elemente, ggf. wurden jedoch einige Elemente entfernt. Veranschaulichen wir uns das Prinzip an ein paar Beispielen:

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

Es besteht ein wichtiger Unterschied zwischen der längsten gemeinsamen Teilfolge und dem längsten gemeinsamen Teilstring („Longest common substring“). Ein Teilstring darf im Gegensatz zur Teilfolge keine Lücken enthalten. Am Beispiel von „DAVID“ / „DANIEL“ wäre der längste gemeinsame Teilstring „DA“, da „I“ durch „V“ bzw. „N“ unterbrochen werden.

Was ist ein praktisches Beispiel für das LCS-Problem?

Bedeutung hat das Longest-Common-Subsequence-Problem in allen Gebieten, in denen mit voneinander abstammenden Sequenzen gearbeitet wird. Lösungsansätze zum Auffinden der LCS kommen etwa zum Einsatz, um Texte auf Gemeinsamkeiten und Unterschiede zu untersuchen – so lassen sich Plagiate aufspüren. Auch das bekannte diff-Utility, das die Veränderungen an Quelltext-Dateien aufzeigt, basiert auf dem LCS-Problem.

In der Bioinformatik findet sich das Longest-Common-Subsequence-Problem bei der Analyse von DNA-Sequenzen. Durch Mutationen werden über die Zeit hinweg DNA-Basen an einzelnen Positionen verändert. Das Vorhandensein einer langen gemeinsamen Teilfolge zwischen zwei Sequenzen deutet auf eine hohe genetische Verwandtheit hin. So lassen sich genetische Entwicklungen zwischen Spezies über die Evolution hinweg nachvollziehen.

Linguisten und Linguistinnen nutzen das Longest-Common-Subsequence-Problem, um die Entwicklung von Sprachen über die Jahrhunderte hinweg zu untersuchen. Finden sich zwei Worte aus verschiedenen Sprachen, die dieselbe Bedeutung haben und eine lange gemeinsame Teilfolge aufweisen, deutet dies auf einen gemeinsamen Ursprung hin. So lässt sich aus der Übereinstimmung der Buchstaben auf die historische Entwicklung schließen.

Wie funktionieren Lösungsansätze für das Longest-Common-Subsequence-Problem?

Zunächst lässt sich das LCS-Problem mit einem „naiven“ Ansatz lösen. Dabei handelt es sich um den naheliegenden Ansatz ohne Optimierung oder spezielle Herangehensweise. Man ermittelt alle Teilfolgen 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 effiziente Lösungsansätze für das LCS-Problem:

  1. Rekursiver Ansatz
  2. Optimierung mittels Memoisation
  3. Dynamische Programmierung

Allen Ansätzen ist gemein, dass sie in Bezug auf die beiden Sequenzen drei Fälle unterscheiden:

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

Die Ansätze unterscheiden sich jeweils in Zeitkomplexität (asymptotischer Laufzeit) und Platzkomplexität (Speicherbedarf):

Ansatz Laufzeit Speicherbedarf
Naiver Ansatz O(n * n²) O(n)
Rekursiver Ansatz O(n²) O(1)
Optimierung mittels Memoisation O(n *m) O(n* m)
Dynamische Programmierung O(n *m) O(n* m)
Hinweis

Die im Folgenden dargestellten Algorithmen ermitteln jeweils die Länge der längsten gemeinsamen Teilfolge. Es gibt ggf. mehrere konkrete Teilfolgen dieser Länge, die sich durch weitere Schritte ermitteln lassen.

Longest Common Subsequence rekursiv ermitteln

Bei Betrachtung des LCS-Problems zeigt sich, dass dieses eine „optimal substructure“ aufweist. Das bedeutet, dass sich das Problem auf Unterprobleme reduzieren lässt. Zur Lösung bietet sich ein rekursiver Ansatz an. Wir zeigen die Implementation des Algorithmus in drei beliebten Programmiersprachen.

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
Domain kaufen
Registrieren Sie Ihre perfekte Domain
  • Inklusive Wildcard-SSL-Zertifikat
  • Inklusive Domain Lock
  • Inklusive 2 GB E-Mail-Postfach

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

Optimierung des rekursiven Ansatzes mittels Memoisation

Bei weiterer Betrachtung des rekursiven Ansatzes zeigt sich, dass überlappende Teilfolgen berechnet werden. Diese Eigenschaft, die als „overlapping subproblems“ bezeichnet wird, ist von der Fibonacci-Folge bekannt. Auch hier werden rekursiv Teile auf dem Weg zur Lösung immer wieder berechnet. Um den Prozess effizienter zu gestalten, bietet es sich an, Memoisation zu verwenden. Anders gesagt cachen wir die bereits berechneten Unterprobleme in einer zweidimensionalen 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++

Dynamische Programmierung für Longest Common Subsequence

Die dynamische Programmierung ist eine nichtrekursive Technik zur Lösung von Optimierungsproblemen, indem sie diese in kleinere Teilprobleme unterteilt und im Anschluss „bottom-up“ löst. Dynamische Programmierung wird u. a. als Lösungsansatz für Pathfinding-Algorithmen angewandt. Das Problem der Longest Common Subsequence lässt sich ebenfalls durch dynamische Programmierung lösen, wobei eine zweidimensionale 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++
War dieser Artikel hilfreich?