Nejdelší společná následná sekvence: Python, C++ Příklad

Co je nejdelší společná posloupnost?

Longest Common Subsequence (LCS) znamená, že dostanete dva řetězce/vzory/sekvence objektů. Mezi těmito dvěma sekvencemi/řetězci musíte najít nejdelší podsekvenci prvků ve stejném pořadí přítomnou v obou řetězcích nebo vzorech.

Příklad

K dispozici jsou například dva řetězce.

Předpokládejme, že

Vzor_1 = „RGBGARGA“
Vzor_2 = „BGRARG“

• Ze vzoru_1 lze vytvářet sekvence jako „RGB“, „RGGA“, „RAR“. Chcete-li vytvořit sekvenci, musíte zachovat relativní polohu každého znaku v řetězci.
• Ze vzoru_2 můžeme vytvořit sekvence jako „BGR“, „BRAG“, „RARG“. Sekvence lze vytvářet, pokud zachovávají relativní polohu původní struny.

Pojem relativní pozice znamená řád.

Například „BRG“ je platná sekvence, protože v původním řetězci pattern_2 se nejprve objevilo „B“, poté „R“ a poté „G“. Pokud je však sekvence „RBRG“, není platná. Protože v původním řetězci (vzor_2) je „B“ na prvním místě.

Máme dvě možnosti, jak z daných dvou sekvencí nebo polí najít nejdelší společnou podsekvenci.

• Naivní metoda
• Řešení dynamického programování: Nejdelší společná podsekvence je také známá jako LCS.

Naivní řešení má větší časovou náročnost a není optimálním řešením. Pomocí řešení dynamického programování (DP) překonáme problém složitosti.

Naivní metoda

Naivní metoda je jednoduchý přístup k problému bez ohledu na časovou náročnost a další optimalizační faktory.

Naivní metoda sestává z „hrubé síly“, více smyček, ve většině případů rekurzivních metod.

Pojem hrubá síla znamená procházet všemi možnými vzory pro daný problém.

Příklad

Z výše uvedeného příkladu vzor1 a vzor2 předpokládejme, že vzor1 má délku m a vzor2 má délku n. Abychom zkontrolovali každý možný případ, musíme vyhodnotit každou možnou podsekvenci vzoru1 se vzorem2.

Zde je jednoduchý 4písmenný řetězec „ABCD“. Potřebujeme například vytvořit sekvenci z „ABCD“. Buď můžeme vzít postavu, nebo ne. To znamená, že pro každou postavu máme dvě možnosti.

Jedná se o:

• Postava bude přidána do podsekvence.
• Postava nebude přidána do podsekvence.

Zde obrázky ukazují všechny sekvence, které můžeme vytvořit z řetězce „ABCD“.

Sekvence s 1 znakem:

Sekvence se 2 znaky:

Sekvence se 3 znaky:

Z výše uvedeného diagramu je 14 sekvencí. Pokud nebudeme brát písmena, v podstatě prázdný řetězec, bude celkový počet sekvencí 15. Navíc samotný řetězec „ABCD“ je sekvencí. Celkový počet sekvencí je tedy 16.

Je tedy možné vygenerovat 2⁴ nebo 16 podsekvencí z „ABCD“. Poté řetězec o délce m bude muset celkově následovat 2^m.

Pro každou podsekvenci ji musíme zkontrolovat pro celý vzor2. Bude to trvat 0(n) času. 0(n) znamená funkci složitosti, která vypočítává čas potřebný k provedení.

Tím se stává celková časová složitost O(n*2^m). Pro příklad jsme výše viděli hodnotu m=8 an=5.

Zde jsou kroky naivní metody:

Krok 1) Vezměte sekvenci ze vzoru1.
Krok 2) Spojte sekvenci z kroku 1 se vzorem 2.
Krok 3) Pokud se shoduje, uložte podsekvenci.
Krok 4) Pokud ve vzoru 1 zbývá více sekvence, přejděte znovu ke kroku 1.
Krok 5) Vytiskněte nejdelší podsekvenci.

Optimální spodní konstrukce

Termín optimální substruktura znamená optimální řešení (jednoduché), které lze nalézt řešením dílčích problémů. Například ve výše uvedeném příkladu máme vzor1 a vzor2.

Krok 1) Vezměte první dva znaky z každého vzoru

Krok 2) Vezměte třetí až pátý znak z každého vzoru.

Krok 3) Podobně pokračujte se zbývajícími znaky.

Nalezneme LCS na podřetězci (řetězec vygenerovaný z původního řetězce). Poté vedeme záznam o délce LCS podřetězců.

Nyní je zde další zajímavá vlastnost překrývající se dílčí problémy. Říká se, že problém má překrývající se dílčí problémy, pokud lze příkaz problému rozdělit na malé dílčí problémy a použít jej v programu několikrát.

Níže uvedený diagram ukazuje, že rekurzivní algoritmus volal funkci se stejným parametrem několikrát.

Podívejme se například na strom rekurze.

V tmavě zbarveném poli si můžete všimnout překrývajících se dílčích problémů. („RG“, „RA“), („RG“, „R“) a další jsou volány několikrát.

Pro optimalizaci tohoto máme přístup o Dynamické programování (DP).

Rekurzivní metoda nejdelší komunikační sekvence

Výše uvedený graf je rekurzivní metodou. Každá rekurzivní funkce má základní případ pro přerušení rekurze nebo zahájení návratu ze svého zásobníku.

Pro tuto implementaci použijeme základní případ. Takže algoritmus je jako následující:

• Pokud se všechny prvky před posledním prvkem shodují, zvyšte délku o jednu a vraťte se
• Předejte funkci dva vzory a vezměte maximální hodnotu návratu
• Pokud má jeden vzor nulovou délku, pak nemáme žádnou podsekvenci, kterou bychom mohli porovnávat. V tomto případě vraťte 0. Toto je základní případ rekurze.

Pseudo kód:

def lcs:
    input: pattern_1, pattern_2, len_1, len_2
if len_1 or len_2 is zero:
    then
return 0
if pattern_1[len_1 - 1] equals pattern_2[len_2 - 1]
then
return 1 + lcs(pattern_1, pattern_2,
    len_1 - 1, len_2 - 1)
else
    max of lcs(pattern_1, pattern_2, len_1 - 1, len_2),
    lcs(pattern_1, pattern_2, len_1, len_2 - 1)

provádění C++

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int lcs(string pattern_1, string pattern_2, int len_1, int len_2) {
  if (len_1 == 0 || len_2 == 0)
    return 0;
  if (pattern_1[len_1 - 1] == pattern_2[len_2 - 1]) {
    return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1);
  } else {
    return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2), lcs(pattern_1, pattern_2, len_1, len_2 - 1));
  }
}
int main() {
  string pattern_1, pattern_2;
  pattern_1 = "RGBGARGA";
  pattern_2 = "BGRARG";
  cout<<"Length of LCS is: "<<lcs(pattern_1, pattern_2, pattern_1.size(), pattern_2.size())<<endl;
}

Výstup:

Length of LCS is: 5

Implementace v pythonu

def lcs(pattern_1, pattern_2, len_1, len_2):
    if len_1 == 0 or len_2 == 0:
    return 0
if pattern_1[len_1 - 1] == pattern_2[len_2 - 1]:
    return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1)
else :
    return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2), lcs(pattern_1, pattern_2, len_1, len_2 - 1))
pattern_1 = "RGBGARGA"
pattern_2 = "BGRARG"
print("Lenght of LCS is: ", lcs(pattern_1, pattern_2, len(pattern_1), len(pattern_2)))

Výstup:

Lenght of LCS is:  5

Metoda dynamického programování Longest Common Subsequence (LCS)

Dynamické programování znamená optimalizaci jednoduché rekurzivní metody. Pokud například vidíme graf rekurzivního nebo naivního přístupu, můžeme vidět, že existuje několik stejných volání funkcí. Metoda dynamického programování zaznamenává všechny výpočty do pole a v případě potřeby je používá.

Použijeme 2D pole s rozměry mxn, kde m a n jsou délky vzoru1 a vzoru2.

Pro 2D pole, můžeme použít datové struktury List v pythonu nebo datové struktury vector/array v C++.

Pseudokód pro LCS pomocí DP:

LCS(pattern_1, pattern_2):
    m = length of pattern_1 + 1
n = length of pattern_2 + 1
dp[n][m]
for i in range 0 to n + 1:
    for j in range 0 to m + 1:
    if i or j equals to 0:
    dp[i][j] = 0
else if pattern_1[i] == pattern_2[j]:
    dp[i]][j] = dp[i - 1][j - 1] + 1
else :
    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[n][m]

Zde je tabulka LCS, která se používá jako datová struktura 2D pole pro přístup dynamického programování.

Pojďme diskutovat o logice, kterou jsme zde použili. Kroky jsou:

Krok 1) Pokud je i nebo j nula, bereme z daných dvou řetězců prázdný řetězec a snažíme se najít společné podposloupnosti. Protože je však podřetězec, který bereme, prázdný, délka podsekvence je 0.

Krok 2) Pokud se dva znaky shodují, přiřadíme hodnotu indexu (i,j) zvýšením dříve vypočteného LCS, který je přítomen v indexu (i-1,j-1) (z předchozího řádku).

Krok 3) Pokud se neshoduje, vezmeme maximální LCS sousedních dvou indexů. A tímto způsobem musíme vyplnit všechny hodnoty ve 2D poli.

Krok 4) Nakonec vrátíme hodnotu poslední buňky 2D pole.

V podstatě všechny hodnoty ve 2D poli obsahují délku společných podsekvencí. Mezi nimi poslední buňka obsahuje délku nejdelší společné podsekvence.

provádění C++

#include<iostream>
using namespace std;
int lcs(string pattern_1, string pattern_2) {
  int m = pattern_1.size();
  int n = pattern_2.size();
  // dp will store solutions as the iteration goes on
  int dp[n + 1][m + 1];
  for (int i = 0; i & lt; n + 1; i++) {
    for (int j = 0; j & lt; m + 1; j++) {
      if (i == 0 || j == 0) {
        dp[i][j] = 0;
      } else if (pattern_2[i - 1] == pattern_1[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[n][m];
}
int main() {
  string pattern_1 = "RGBGARGA";
  string pattern_2 = "BGRARG";
  cout<<"Length of LCS: "<<lcs(pattern_1, pattern_2)<<endl;
}

Výstup:

Length of LCS: 5

provádění Python

def lcs(pattern_1, pattern_2):
    m = len(pattern_1)
n = len(pattern_2)
# dp will store solutions as the iteration goes on
dp = [
    [None] * (n + 1) for item in range(m + 1)
]
for i in range(m + 1):
    for j in range(n + 1):
    if i == 0 or j == 0:
    dp[i][j] = 0
elif pattern_1[i - 1] == pattern_2[j - 1]:
    dp[i][j] = dp[i - 1][j - 1] + 1
else :
    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
pattern_1 = "RGBGARGA"
pattern_2 = "BGRARG"
print("Length of LCS: ", lcs(pattern_1, pattern_2))

Výstup:

Length of LCS: 5

Oba řetězce tedy mají nejdelší společnou podposloupnost délky 5.

Stručně řečeno, v metodě DP v metodě DP počítáme každý úkol jednoduše jednou. V rekurzivní metodě můžeme mít překrývající se dílčí problémy.

V tomto algoritmu dynamického programování používáme 2D matici. Budou zadány dva řetězce (předpokládejme, že oba mají délku n). Potom je potřebný prostor v poli nx n. Pokud jsou řetězce dostatečně velké, budeme potřebovat paměťově optimalizovanou verzi řešení DP.

Zjednodušená logika, která byla převzata v kódu, je:

• Deklarujte 2D pole DP[m][n].
• Vyplňte první řádek a první sloupec pole DP 0.
• Vezměte i a j pro iteraci.
• Pokud se vzor1[i] rovná vzoru2[j], aktualizujte DP[i][j] = DP[i-1][j-1] + 1
• Pokud se vzor1[i] nerovná vzoru2[j], pak DP[i][j] bude maximální hodnota mezi DP[i-1][j] a DP[i][j-1].
• Pokračujte, dokud i a j nedosáhnou m an.
• Poslední prvek nebo DP[m-1][n-1] bude obsahovat délku.

Zde je adresován jako DP[m-1][n-1], protože index pole začíná od 0.

Shrnutí

• Metoda DP má nižší časovou složitost; je to O(mn), kde m a n jsou délka vstupního řetězce nebo pole.
• DP je rychlejší přístup než rekurzivní, s časovou složitostí O(n*2^m).
• Dynamické programování (DP) není paměťově optimalizované. Použili jsme 2D pole, které má délku m*n. Prostorová složitost je tedy (m*n).
• Rekurzivní metoda, v nejhorším případě bude nejvyšší paměť, kterou zabere, m+n, v podstatě celková délka zadaného řetězce.
• Dnešní moderní počítač je dostatečný pro zvládnutí tohoto množství paměti.