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.

Inhaltsverzeichnis

Worum handelt es sich beim Longest-Common-Subsequence-Problem?
Was ist ein praktisches Beispiel für das LCS-Problem?
Wie funktionieren Lösungsansätze für das Longest-Common-Subsequence-Problem?

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`

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:

Rekursiver Ansatz
Optimierung mittels Memoisation
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)`

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

Mehr als nur eine Domain!

Hier finden Sie Ihre perfekte Domain - z.B. .de Domain + persönlicher Berater

E-Mail-Postfach

24/7 Support

Wildcard SSL

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