Mikä on pisin yhteinen alijono-ongelma?

Sisällys

Pisin yhteinen osajono (LCS) on tyypillinen ongelma tietotekniikassa. LCS-ongelman ratkaisutapoja kysytään usein ohjelmoijien haastatteluissa ja algoritmikursseilla.

Mikä on pisin yhteinen alijono?

Tavoitteena on löytää kahden sekvenssin pisin yhteinen alisekvenssi. Alisekvenssi on johdettu sekvenssistä. Alisekvenssillä on sama elementtien järjestys, joissakin tapauksissa elementtejä poistetaan. Katsotaanpa muutamia esimerkkejä, jotta ymmärrämme periaatetta paremmin:

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

Huomio

Pisin yhteinen alijono ja pisin yhteinen osajono eroavat toisistaan merkittävästi, sillä osajonossa ei saa olla aukkoja. Esimerkissä ”DAVID” ja ”DANIEL” pisin yhteinen osajono olisi ”DA”, koska ”I” on erotettu ”V”:llä ja ”N”:llä.

Onko LCS-ongelmasta käytännön esimerkkejä?

Pisin yhteinen osajono -ongelma on tärkeä kysymys kaikilla aloilla, joilla käytetään toisistaan johtuvia jonoja. On olemassa tiettyjä tapoja löytää LCS, jotta voidaan selvittää, onko jonoissa yhtäläisyyksiä tai eroja, ja siten havaita mahdolliset plagioinnit. Tunnettu diff-apuohjelma, joka tarkistaa lähdetekstitiedostojen muutokset, perustuu LCS-ongelmaan.

Bioinformatiikassa pisin yhteinen alijono-ongelma käytetään usein DNA-sekvenssien analysoinnissa. DNA-emäkset muuttuvat ajan myötä tietyissä kohdissa mutaatioiden vuoksi. Pitkän yhteisen alijonon esiintyminen kahdessa sekvenssissä viittaa geneettiseen sukulaisuuteen. Tämän avulla voimme jäljittää lajien välisen evoluution geneettisen kehityksen ansiosta.

Kielitieteilijät voivat myös käyttää pisimmän yhteisen osajonon ongelmaa tutkiakseen kielten kehitystä vuosisatojen ajan. Jos sinulla on kaksi eri kielistä peräisin olevaa sanaa, joilla on sama merkitys ja pitkä yhteinen osajono, se viittaa siihen, että niillä on sama juuri ja etymologia. Tätä voitaisiin sitten pitää samanlaisena historiallisena kehityksenä.

Mitkä ovat ratkaisut pisimpään yhteiseen alijono-ongelmaan?

Ensinnäkin voit ratkaista LCS-ongelman naiivilla lähestymistavalla. Tämä on yksinkertainen lähestymistapa, jossa ei käytetä optimointeja tai erityisiä menetelmiä. Tätä varten lasket vain kaikki kahden sekvenssin alisekvenssit ja etsit pisimmän yhteisen alisekvenssin. Valitettavasti tämä lähestymistapa ei ole kovin tehokas, joten se sopii vain lyhyille sekvensseille.

Alla on kolme tehokasta ratkaisua LCS-ongelmaan:

Rekursiivinen lähestymistapa
Optimointi muistamisen avulla
Dynaaminen ohjelmointi

Kaikille lähestymistavoille on yhteistä, että ne eroavat toisistaan kolmessa tapauksessa näiden kahden sekvenssin osalta:

Viimeinen kirjain on sama.
Viimeinen kirjain ei ole sama.
Toisen merkkijonon pituus on nolla.

Lähestymistavat eroavat toisistaan ajankäytön monimutkaisuuden (asymptotinen suoritusaika) ja tilankäytön monimutkaisuuden (muistin käyttö) suhteen:

Lähestymistapa	Kesto	Muisti
Naiivi lähestymistapa	`O(n * n²)`	`O(n)`
Rekursiivinen lähestymistapa	`O(n²)`	`O(1)`
Optimointi muistamisen avulla	`O(n *m)`	`O(n* m)`
Dynaaminen ohjelmointi	`O(n *m)`	`O(n* m)`

Huomio

Alla esitetyt algoritmit laskevat kaikki pisimmän yhteisen osajonon pituuden. Tarvittaessa on olemassa useita tämän pituisia osajonoja, jotka voidaan määrittää muiden vaiheiden avulla.

Pisin yhteinen alijonojen rekursiivinen määrittäminen

Jos tarkastellaan LCS-ongelmaa, voidaan havaita, että sillä on ”optimaalinen alirakenne”. Tämä tarkoittaa, että ongelma voidaan jakaa osiongelmiin. Ratkaisuna voidaan käyttää rekursiivista lähestymistapaa. Alla on esimerkkejä algoritmeista, joilla tämä voidaan toteuttaa kolmella yleisimmällä ohjelmointikielellä.

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

Rekursiivisen lähestymistavan optimointi muistitoiminnon avulla

Kun tarkastellaan uudelleen rekursiivista lähestymistapaa, voidaan nähdä, että päällekkäiset osat lasketaan. Nämä ominaisuudet, joita kutsutaan ”päällekkäisiksi osaprobleemiksi”, tunnetaan Fibonacci-jonoista. Tässäkin tapauksessa rekursiivisia jonoja lasketaan jatkuvasti ratkaisun löytämiseksi. Prosessin tehostamiseksi kannattaa käyttää muistia. Toisin sanoen, jo lasketut osaprobleemit voidaan tallentaa välimuistiin kaksiulotteisessa matriisissa.

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

Dynaaminen ohjelmointi pisimmälle yhteiselle alijonolle

Dynaaminen ohjelmointi on ei-rekursiivinen tapa ratkaista optimointiongelmia jakamalla ne pienempiin osiongelmiin ja ratkaisemalla ne sitten “alhaalta ylöspäin”. Dynaamista ohjelmointia sovelletaan muun muassa reitinetsintäalgoritmien ratkaisuna. Pisin yhteinen alijono -ongelma voidaan myös ratkaista dynaamisella ohjelmoinnilla, kun käytetään kaksiulotteista matriisia.

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

Mikä on pisin yhteinen alijono-ongelma?

Mikä on pisin yhteinen alijono?

Onko LCS-on­gel­mas­ta käytännön esi­merk­ke­jä?

Mitkä ovat ratkaisut pisimpään yhteiseen alijono-ongelmaan?

Pisin yhteinen ali­jo­no­jen re­kur­sii­vi­nen mää­rit­tä­mi­nen

Python

Java

C++

Re­kur­sii­vi­sen lä­hes­ty­mis­ta­van op­ti­moin­ti muis­ti­toi­min­non avulla

Python

Java

C++

Dy­naa­mi­nen oh­jel­moin­ti pi­sim­mäl­le yh­tei­sel­le ali­jo­nol­le

Python

Java

C++

Onko LCS-ongelmasta käytännön esimerkkejä?

Pisin yhteinen alijonojen rekursiivinen määrittäminen

Rekursiivisen lähestymistavan optimointi muistitoiminnon avulla

Dynaaminen ohjelmointi pisimmälle yhteiselle alijonolle