Mis on pikim ühine alajada probleem?

Contents

Pikimad ühised alajadad (LCS) on IT-valdkonnas tüüpiline probleem. LCS-probleemi lahendamise lähenemisviisid esinevad sageli programmeerijate tööintervjuudes ja algoritmide kursustel.

Mis on pikim ühine alajada?

Eesmärk on leida kahe jada pikim ühine alajada. Siin on alajada tuletatud jadast. Alajadal on sama elementide järjekord, mõnel juhul, kui elemente on eemaldatud. Vaadakem mõningaid näiteid, et saada parem ülevaade põhimõttest:

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

Note

Pikima ühise alajada ja pikima ühise alamjada vahel on oluline erinevus, sest alamjada ei tohi sisaldada lünki. Näites „DAVID” ja „DANIEL” oleks pikim ühine alamjada „DA”, kuna „I” on eraldatud tähtedega „V” ja „N”.

Kas on olemas praktilisi näiteid LCS-probleemi kohta?

Pikima ühise alajada probleem on oluline küsimus kõikides valdkondades, kus kasutatakse üksteisest tulenevaid jadasid. On olemas teatud viisid LCS-i leidmiseks, et näha, kas on sarnasusi või erinevusi, ja omakorda avastada võimalikku plagieerimist. Tuntud utiliit „diff”, mis kontrollib muudatusi allikatekstifailides, põhineb LCS-probleemil.

Bioinformaatikas kasutatakse DNA järjestuste analüüsimisel sageli pikima ühise alajärjestuse probleemi. DNA alused muutuvad aja jooksul mutatsioonide tõttu teatud kohtades. Kahe järjestuse pika ühise alajärjestuse olemasolu viitab geneetilisele sugulusele. See võimaldab meil geneetilise arengu abil jälgida liikidevahelist evolutsiooni.

Keeleteadlased võivad kasutada pikima ühise alajada probleemi ka keelelise arengu uurimiseks läbi sajandite. Kui teil on kaks erinevast keelest pärit sõna, millel on sama tähendus ja pikk ühine alajada, viitab see sellele, et neil on sama juur ja etümoloogia. Seda võiks seega pidada sarnaseks ajalooliseks arenguks.

Millised on lahendused pikima ühise alajada probleemile?

Esiteks võite LCS-probleemi lahendada naiivse lähenemisviisiga. See on lihtne lähenemisviis, mis ei kasuta optimeerimist ega spetsiaalseid meetodeid. Selleks arvutate lihtsalt välja kõik kahe jada alajadad ja leiate pikima ühise alajada. Kahjuks ei ole see lähenemisviis väga efektiivne ja sobib seetõttu ainult lühikeste jadade puhul.

Allpool leiate kolm tõhusat lahendust LCS-probleemile:

Rekursiivne lähenemine
Optimeerimine memoisatsiooni abil
Dünaamiline programmeerimine

Kõikidel lähenemisviisidel on ühine see, et kahe järjestuse puhul erinevad need kolmel juhul:

Viimane täht on sama.
Viimane täht ei ole sama.
Ühe järjestuse pikkus on null.

Need lähenemisviisid erinevad üksteisest ajalise keerukuse (asümptootiline tööaeg) ja ruumilise keerukuse (mälu kasutamine) poolest:

Lähenemisviis	Kestus	Mälu
Naivne lähenemisviis	`O(n * n²)`	`O(n)`
Rekursiivne lähenemine	`O(n²)`	`O(1)`
Optimeerimine memoisatsiooni abil	`O(n *m)`	`O(n* m)`
Dünaamiline programmeerimine	`O(n *m)`	`O(n* m)`

Note

Allpool esitatud algoritmid arvutavad kõik pikima ühise alajada pikkuse. Vajaduse korral on olemas mitu sellise pikkusega alajada, mis saab määrata teiste sammude abil.

Pikima ühise alajada rekursiivne määramine

LCS-probleemi vaadates võib näha, et sellel on „optimaalne alusstruktuur”. See tähendab, et probleemi saab jagada alamprobleemideks. Lahendusena võib kasutada rekursiivset lähenemist. Allpool on toodud mõned näited algoritmidest, millega seda kolme levinuimas programmeerimiskeeles rakendada.

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

Rekursiivse lähenemise optimeerimine memoisatsiooni abil

Kui vaadata uuesti rekursiivset lähenemist, näete, et arvutatakse kattuvad osad. Need omadused, mida nimetatakse „kattuvateks alamprobleemideks”, on tuntud Fibonacci jadas. Ka sel juhul arvutatakse lahenduse leidmiseks pidevalt rekursiivseid jadasid. Protsessi tõhustamiseks tasub kasutada memoisatsiooni. Teisisõnu, võite juba arvutatud alamprobleemid salvestada kahemõõtmelisse maatriksi.

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

Dynaamiline programmeerimine pikima ühise alajada jaoks

Dünaamiline programmeerimine on mittesüstemaatiline viis optimeerimisülesannete lahendamiseks, jagades need väiksemateks alamprobleemideks ja lahendades need seejärel „alt ülespoole”. Muu hulgas kasutatakse dünaamilist programmeerimist lahendusena teedeotsingu algoritmide jaoks. Ka pikima ühise alajada probleemi saab lahendada dünaamilise programmeerimise abil, kasutades kahemõõtmelist maatriksit.

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

Mis on pikim ühine alajada probleem?

Mis on pikim ühine alajada?

Kas on olemas prak­tilisi näiteid LCS-probleemi kohta?

Millised on la­hen­dused pikima ühise alajada prob­lee­mile?

Pikima ühise alajada re­kur­siivne määramine

Python

Java

C++

Re­kur­siivse lä­he­ne­mise op­ti­mee­ri­mine me­moi­sat­siooni abil

Python

Java

C++

Dy­naa­mi­line prog­ram­mee­ri­mine pikima ühise alajada jaoks

Python

Java

C++

Kas on olemas praktilisi näiteid LCS-probleemi kohta?

Millised on lahendused pikima ühise alajada probleemile?

Pikima ühise alajada rekursiivne määramine

Rekursiivse lähenemise optimeerimine memoisatsiooni abil

Dynaamiline programmeerimine pikima ühise alajada jaoks