Wat is het probleem van de langste gemeenschappelijke deelreeks?

Inhoudsopgave

Langste gemeenschappelijke subreeksen (LCS) zijn een typisch probleem in de IT. Benaderingen om het LCS-probleem op te lossen komen vaak voor in sollicitatiegesprekken voor programmeurs en algoritmecursussen.

Wat is de langste gemeenschappelijke deelreeks?

Het doel is om de langste gemeenschappelijke deelreeks in twee reeksen te vinden. Hierbij wordt een deelreeks afgeleid van een reeks. De deelreeks heeft dezelfde elementaire volgorde, in sommige gevallen wanneer elementen worden verwijderd. Laten we enkele voorbeelden bekijken om een beter beeld te krijgen van het principe:

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

Opmerking

Er is een belangrijk verschil tussen de langste gemeenschappelijke deelreeks en de langste gemeenschappelijke deelstring, namelijk dat een deelstring geen hiaten mag bevatten. In het voorbeeld van ‘DAVID’ en ‘DANIEL’ zou de langste gemeenschappelijke deelstring ‘DA’ zijn, aangezien ‘I’ wordt gescheiden door ‘V’ en ‘N’.

Zijn er praktische voorbeelden van het LCS-probleem?

Het probleem van de langste gemeenschappelijke deelreeks is een belangrijke kwestie op alle gebieden waar reeksen worden gebruikt die uit elkaar voortkomen. Er zijn bepaalde manieren om LCS te vinden om te zien of er overeenkomsten of verschillen zijn en zo eventueel plagiaat te ontdekken. Het bekende hulpprogramma ‘diff’, dat controleert op wijzigingen in brontekstbestanden, is gebaseerd op het LCS-probleem.

In de bio-informatica wordt het probleem van de langste gemeenschappelijke subreeks vaak gebruikt bij het analyseren van DNA-reeksen. DNA-basen veranderen in de loop van de tijd op bepaalde posities als gevolg van mutaties. De aanwezigheid van een lange gemeenschappelijke subreeks in twee reeksen zou wijzen op een genetische verwantschap. Hierdoor kunnen we dankzij de genetische ontwikkeling de evolutie tussen soorten terugvolgen.

Taalkundigen kunnen het probleem van de langste gemeenschappelijke deelreeks ook gebruiken om de taalkundige ontwikkeling door de eeuwen heen te onderzoeken. Als je twee woorden uit verschillende talen hebt die dezelfde betekenis hebben en een lange gemeenschappelijke deelreeks, dan suggereert dit dat ze dezelfde oorsprong en etymologie hebben. Dit zou dan worden beschouwd als een vergelijkbare historische ontwikkeling.

Wat zijn de oplossingen voor het probleem van de langste gemeenschappelijke deelreeks?

Allereerst kun je het LCS-probleem oplossen met een naïeve aanpak. Dit is een eenvoudige aanpak zonder gebruik te maken van optimalisaties of speciale methoden. Hiervoor bereken je simpelweg alle subreeksen van twee reeksen en zoek je de langste gemeenschappelijke subreeks. Helaas is deze aanpak niet erg efficiënt en daarom alleen geschikt voor korte reeksen.

Hieronder vindt u drie efficiënte oplossingen voor het LCS-probleem:

Recursieve benadering
Optimalisatie door middel van memoïzatie
Dynamisch programmeren

Wat alle benaderingen gemeen hebben, is dat ze met betrekking tot de twee reeksen in drie gevallen van elkaar verschillen:

De laatste letter is hetzelfde.
De laatste letter is niet hetzelfde.
De lengte van een van de reeksen is nul.

De benaderingen verschillen onderling in hun tijdcomplexiteit (asymptotische looptijd) en ruimtecomplexiteit (geheugengebruik):

Aanpak	Looptijd	Geheugen
Naïeve aanpak	`O(n * n²)`	`O(n)`
Recursieve benadering	`O(n²)`	`O(1)`
Optimalisatie via memoïzatie	`O(n *m)`	`O(n* m)`
Dynamisch programmeren	`O(n *m)`	`O(n* m)`

Opmerking

De hieronder beschreven algoritmen berekenen allemaal de lengte van de langste gemeenschappelijke subreeks. Er zijn, indien van toepassing, meerdere vaste subreeksen van deze lengte die met behulp van andere stappen kunnen worden bepaald.

Recursieve bepaling van de langste gemeenschappelijke deelreeks

Als je naar het LCS-probleem kijkt, zie je dat het een ‘optimale substructuur’ heeft. Dit betekent dat het probleem kan worden teruggebracht tot deelproblemen. Als oplossing kun je een recursieve benadering gebruiken. Hieronder vind je enkele voorbeelden van algoritmen om dit in drie van de meest gangbare programmeertalen te implementeren.

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

Optimaliseren van de recursieve benadering met behulp van memoisation

Als je nog eens naar de recursieve benadering kijkt, zie je dat de overlappende delen worden berekend. Deze kenmerken, ‘overlappende subproblemen’ genoemd, zijn bekend uit Fibonacci-reeksen. Ook in dit geval worden voortdurend recursieve reeksen berekend om tot een oplossing te komen. Om het proces efficiënter te maken, is het de moeite waard om memoisation te gebruiken. Met andere woorden, je kunt de subproblemen die al zijn berekend, in een tweedimensionale matrix in de cache opslaan.

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 programmering voor de langste gemeenschappelijke deelreeks

Dynamisch programmeren is een niet-recursieve manier om optimalisatieproblemen op te lossen door ze op te splitsen in kleinere deelproblemen en deze vervolgens ‘bottom-up’ op te lossen. Dynamisch programmeren wordt onder andere toegepast als oplossing voor pathfinding-algoritmen. Het probleem van de langste gemeenschappelijke deelreeks kan ook worden opgelost met behulp van dynamisch programmeren wanneer een tweedimensionale matrix wordt gebruikt.

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

Wat is het probleem van de langste ge­meen­schap­pe­lij­ke deelreeks?

Wat is de langste ge­meen­schap­pe­lij­ke deelreeks?

Zijn er prak­ti­sche voor­beel­den van het LCS-probleem?

Wat zijn de op­los­sin­gen voor het probleem van de langste ge­meen­schap­pe­lij­ke deelreeks?

Re­cur­sie­ve bepaling van de langste ge­meen­schap­pe­lij­ke deelreeks

Python

Java

C++

Op­ti­ma­li­se­ren van de re­cur­sie­ve be­na­de­ring met behulp van me­moi­sa­ti­on

Python

Java

C++

Dy­na­mi­sche pro­gram­me­ring voor de langste ge­meen­schap­pe­lij­ke deelreeks

Python

Java

C++

Wat is het probleem van de langste gemeenschappelijke deelreeks?

Wat is de langste gemeenschappelijke deelreeks?

Zijn er praktische voorbeelden van het LCS-probleem?

Wat zijn de oplossingen voor het probleem van de langste gemeenschappelijke deelreeks?

Recursieve bepaling van de langste gemeenschappelijke deelreeks

Optimaliseren van de recursieve benadering met behulp van memoisation

Dynamische programmering voor de langste gemeenschappelijke deelreeks