Leghosszabb közös sorozat: Python, C++ Példa

Mi a leghosszabb közös utósorozat?

A leghosszabb közös részsorozat (LCS) azt jelenti, hogy két karakterláncot, mintát vagy objektumsorozatot kapsz. E két sorozat vagy karakterlánc közül meg kell találnod a leghosszabb, azonos sorrendben előforduló elemekből álló részsorozatot, amely mindkét karakterláncban vagy mintában megtalálható.

Példa

Például két karakterlánc van megadva. Tegyük fel, hogy:

Pattern_1 = "RGBGARGA"
Pattern_2 = "BGRARG"

• A pattern_1-ből olyan szekvenciák hozhatók létre, mint az „RGB”, „RGGA”, „RGAR”. Szekvencia létrehozásához meg kell őrizni az egyes karakterek relatív pozícióját a karakterláncban.
• A pattern_2 alapján olyan szekvenciákat hozhatunk létre, mint a „BGR”, „BRAG”, „RARG”. Szekvenciák akkor hozhatók létre, ha megőrzik az eredeti karakterlánc relatív pozícióját.

A relatív pozíció kifejezés rendet jelent.

Például a „BRG” érvényes szekvencia, mivel az eredeti pattern_2 karakterláncban először a „B”, majd az „R”, végül pedig a „G” szerepelt. Azonban, ha egy szekvencia „RBRG”, akkor nem érvényes, mert az eredeti pattern_2 karakterláncban a „B” szerepel először.

Két lehetőségünk van a leghosszabb közös részsorozat megkeresésére az adott két sorozatból vagy tömbből.

• Naiv módszer
• Dinamikus programozási megoldás: A leghosszabb közös részsorozatot LCS-nek is nevezik.

Egy naiv megoldás nagyobb időbonyolultsággal jár, és nem optimális megoldás. A dinamikus programozási megoldás (DP) segítségével leküzdjük a bonyolultsági problémát.

Naiv módszer

A Naiv módszer egy egyszerű megközelítés a problémára, függetlenül az időbeli komplexitástól és egyéb optimalizálási tényezőktől. A legtöbb esetben „nyers erőből”, több ciklusból és rekurzív hívásokból áll. A nyers erő kifejezés azt jelenti, hogy egy adott probléma összes lehetséges mintáján végigmegyünk.

Példa

A minta1 és minta2 fenti példájából tegyük fel, hogy a minta 1 hossza m, a minta2 pedig n. Az összes lehetséges eset ellenőrzéséhez ki kell értékelnünk a minta1 és minta2 minden lehetséges részsorozatát.

Íme egy egyszerű, négybetűs karakterlánc, az „ABCD”. Például az „ABCD”-ből kell létrehoznunk egy sorozatot. Vagy veszünk fel egy karaktert, vagy nem. Ez azt jelenti, hogy minden karakter esetében két lehetőségünk van:

• A karakter hozzáadódik a sorozathoz.
• A karakter nem lesz hozzáadva az alsorozathoz.

Itt a képeken látható az összes szekvencia, amit az „ABCD” karakterláncból készíthetünk.

Sorozat 1 karakterből:

2 karakteres sorozatok:

3 karakteres sorozatok:

A fenti ábrán 14 sorozat látható. Ha nem veszünk ki betűket, alapvetően egy üres karakterláncot, az összes sorozat 15 lesz. Sőt, maga az „ABCD” karakterlánc is egy sorozat. Tehát az összes sorozat 16.

Tehát az „ABCD”-ből 2^4 vagy 16 részsorozat generálható. Ezután egy m teljes részsorozata 2^m lesz.

Minden egyes részszekvenciát a teljes mintára ellenőriznünk kell2. Ez O(n) időt vesz igénybe. Az O(n) a végrehajtáshoz szükséges időt kiszámító komplexitásfüggvényt jelenti.

Tehát a teljes időbonyolítás válik O(n*2^m). A fenti példában m=8 és n=5 értéket láttunk.

Íme a naiv módszer lépései:

Step 1) Vegyünk egy szekvenciát az 1. mintából.
Step 2) Párosítsd az 1. lépésben található sorozatot a 2. mintával.
Step 3) Ha egyezik, mentse el a részsorozatot.
Step 4) Ha további sorozatok maradtak az 1. mintában, akkor folytassa az 1. lépéssel.
Step 5) Nyomtassa ki a leghosszabb sorozatot.

Optimális alépítmény

Az optimális alstruktúra kifejezés azt jelenti, hogy az optimális megoldás a részproblémák megoldásával található. Például a fenti példában a minta1 és a minta2 szerepel.

Step 1) Vedd ki az első két karaktert minden mintából.

Step 2) Vegyük a harmadik-ötödik karaktert minden mintából.

Step 3) Hasonló módon folytassa a többi karakterrel.

Az LCS probléma rekurzív szerkezete

Megkeressük az LCS-t az alkarakterláncon (egy eredeti karakterláncból generált karakterláncon). Ezután rögzítjük az alkarakterláncok LCS-jének hosszát.

Itt van egy másik érdekes ingatlan átfedésping részproblémákEgy problémáról azt mondják, hogy átfedés van benne.ping részproblémák, ha a problémameghatározás kisebb részproblémákra bontható, és többször felhasználható a programban.

Az alábbi diagramon látható, hogy a rekurzív algoritmus többször is meghívta a függvényt ugyanazzal a paraméterrel.

Például, nézzük meg a rekurziós fát. A sötét színű mezőben átfedést láthatunk.ping részproblémák. („RG”, „RA”), („RG”, „R”) és mások többször is meghívódnak.

Ennek optimalizálására a következő megközelítést alkalmazzuk: Dinamikus programozás (DP).

Leghosszabb közös részsorozat rekurzív módszere

A fenti gráf a rekurzív metódus. Minden rekurzív függvénynek van egy alapesete a rekurzió megszakítására vagy a veremből való visszatérés megkezdésére.

Ehhez a megvalósításhoz egy alapesetet fogunk használni. Tehát a algoritmus a következőhöz hasonló:

• Ha az utolsó elem előtti összes elem egyezik, akkor növelje a hosszt eggyel, és térjen vissza az értékre.
• Adj át két mintát a függvénynek, és vedd a visszatérési érték maximális értékét.
• Ha egy mintának nulla a hossza, akkor nincs összehasonlítható részsorozatunk. Ebben az esetben adjon vissza 0-t. Ez a rekurzió alapesete.

Pszeudo Code:

def lcs:
    input: pattern_1, pattern_2, len_1, len_2
    if len_1 or len_2 is zero:
        return 0
    if pattern_1[len_1 - 1] equals 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))

Végrehajtás 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;
}

output:

Length of LCS is: 5

Végrehajtás Python

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("Length of LCS is: ", lcs(pattern_1, pattern_2, len(pattern_1), len(pattern_2)))

output:

Length of LCS is:  5

Leghosszabb közös részsorozat (LCS) dinamikus programozási módszere

A dinamikus programozás a sima rekurzív módszer optimalizálását jelenti. Például, ha megnézzük a rekurzív vagy naiv megközelítésű gráfot, láthatjuk, hogy több azonos függvényhívás van. A dinamikus programozási módszer az összes számítást egy tömbben rögzíti, és szükség esetén újra felhasználja azokat.

Egy mxn dimenziójú 2D tömböt fogunk használni, ahol m és n a minta1 és minta2 hossza. Egy 2D tömb, használhatunk List adatszerkezeteket a Python vagy vektor/tömb adatszerkezetekben C++.

Pszeudo Code DP-t használó LCS esetén:

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]

Itt látható az LCS tábla, amelyet 2D tömb adatstruktúraként használnak a dinamikus programozási megközelítésben.

Beszéljük meg az itt használt logikát. A lépések a következők:

Step 1) Ha i vagy j nulla, akkor a megadott két karakterlánc közül egy üres karakterláncot veszünk, és megpróbáljuk megtalálni a közös részsorozatokat. Mivel azonban a vett részsorozat üres, az részsorozat hossza 0.

Step 2) Ha két karakter egyezik, akkor az (i,j) indexhez rendeljük az értéket az előzőleg kiszámított LCS növelésével, amely az (i-1,j-1) indexben szerepel (az előző sorból).

Step 3) Ha nem egyezik, akkor a két szomszédos index maximális LCS-ét vesszük. Így ki kell töltenünk a 2D tömb összes értékét.

Step 4) Végül a 2D tömb utolsó cellájának értékét adjuk vissza.

Alapvetően a 2D tömb összes értéke tartalmazza a közös részsorozatok hosszát. Ezek közül az utolsó cella tartalmazza a leghosszabb közös részsorozat hosszát.

Végrehajtás 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 < n + 1; i++) {
    for (int j = 0; j < 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;
}

output:

Length of LCS: 5

Végrehajtás 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))

output:

Length of LCS: 5

Tehát mindkét karakterláncnak van a leghosszabb közös 5-ös részsorozata.

Dióhéjban, a DP módszerben minden feladatot egyszer számolunk ki. A rekurzív módszerben átfedés lehet.ping részproblémák.

Ebben a dinamikus programozási algoritmusban 2D mátrixot használunk. Két karakterlánc lesz megadva (feltételezzük, hogy mindkettő n hosszúságú). Ekkor a tömbben szükséges hely nx n. Ha a karakterláncok elég nagyok, akkor szükségünk lesz a DP megoldás memóriára optimalizált változatára.

A kódban szereplő egyszerűsített logika a következő:

• DP[m][n] 2D tömb deklarálása.
• Töltse ki a DP tömb első sorát és első oszlopát 0-val.
• Vegyük az i-t és a j-t az iterációhoz.
• Ha a minta1[i] egyenlő a minta2[j]-vel, akkor frissítse a DP[i][j] = DP[i-1][j-1] + 1 értéket.
• Ha a pattern1[i] nem egyenlő a pattern2[j]-vel, akkor a DP[i][j] lesz a DP[i-1][j] és DP[i][j-1] közötti maximális érték.
• Folytassa addig, amíg i és j el nem éri m és n értékét.
• Az utolsó elem, a DP[m-1][n-1], a hosszt fogja tartalmazni.

Itt DP[m-1][n-1] címmel van ellátva, mivel a tömbindex 0-tól kezdődik.

GYIK