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/objektumsorozatot kap. E két sorozat/karakterlánc között meg kell találnia az elemek leghosszabb részsorozatát, azonos sorrendben mindkét karakterláncban vagy mintában.
Példa
Például két karakterlánc van megadva.
Tegyük fel,
Pattern_1 = "RGBGARGA"
Pattern_2 = "BGRARG"
- A minta_1-ből olyan sorozatok állíthatók elő, mint az „RGB”, „RGGA”, „RGAR”. Egy sorozat létrehozásához meg kell őriznie az egyes karakterek relatív pozícióját a karakterláncban.
- A minta_2-ből olyan sorozatokat állíthatunk elő, mint a „BGR”, „BRAG”, „RARG”. Szekvenciák hozhatók létre mindaddig, amíg megtartják az eredeti karakterlánc relatív pozícióját.
A relatív pozíció kifejezés rendet jelent.
Például a „BRG” egy érvényes sorozat, mert az eredeti karakterlánc-mintában először „B”, majd „R”, majd „G” jelent meg_2. Ha azonban egy sorozat „RBRG”, akkor nem érvényes. Mert az eredeti karakterláncban (minta_2) a „B” az első.
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.
A naiv megoldásnak nagyobb az időbonyolítása, és nem az optimális megoldás. A Dynamic Programming Solution (DP) segítségével megoldjuk a bonyolultsági problémát.
Naiv módszer
A naiv módszer a probléma egyszerű megközelítése, függetlenül az idő bonyolultságától és egyéb optimalizálási tényezőktől.
A naiv módszer a legtöbb esetben „Brute Force”-ból, több hurokból és rekurzív metódusokból áll.
A nyers erő kifejezés azt jelenti, hogy egy adott probléma összes lehetséges mintáján végig kell menni.
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 „ABCD” karakterlánc. Például létre kell hoznunk egy sorozatot az „ABCD”-ből. Vagy vehetünk egy karaktert, vagy nem. Ez azt jelenti, hogy minden karakter esetében két választásunk van.
Ők:
- 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 diagramból 14 sorozat van. Ha nem veszünk betűket, alapvetően egy üres karakterláncot, akkor az összes sorozat 15 lesz. Ráadásul maga az „ABCD” karakterlánc egy sorozat. Tehát az összes sorozat 16.
Tehát lehetséges a 24 vagy 16 részsorozat az „ABCD”-ből. Ezután egy karakterlánc hosszúságú m összesen 2-nek kell lenniem.
Minden részsorozatnál ellenőriznünk kell azt a teljes mintára2. 0(n) időt vesz igénybe. A 0(n) azt a bonyolultsági függvényt jelenti, amely a végrehajtáshoz szükséges időt számítja ki.
Tehát a teljes időbonyolítás válik O(n*2m). A példában fentebb láttuk az m=8 és n=5 értékeket.
Íme a naiv módszer lépései:
Step 1) Vegyünk egy sorozatot a mintából1.
Step 2) Párosítsa az 1. lépés sorozatát a 2. mintával.
Step 3) Ha egyezik, mentse el a részsorozatot.
Step 4) Ha több sorozat maradt a mintában1, akkor folytassa újra az 1. lépéssel.
Step 5) Nyomtassa ki a leghosszabb sorozatot.
Optimális alépítmény
Az optimális alépítmény kifejezés azt jelenti, hogy a részproblémák megoldásával optimális (egyszerű) megoldást találhatunk. Például a fenti példában minta1 és minta2 van.
Step 1) Vegyük 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-t az al-karakterláncon találjuk (egy eredeti karakterláncból generált karakterlánc). Ezután vezetjük az alsztringek LCS hosszának nyilvántartását.
Itt van egy másik érdekes ingatlan átfedő részproblémák. Egy problémáról azt mondjuk, hogy átfedő részproblémák vannak, ha a problémafelvetés kis 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.
Lássuk például a rekurziós fát.
A sötét színű mezőben átfedő részproblémákat észlelhet. ("RG", "RA"), ("RG", "R") és másokat többször hívnak.
Ennek optimalizálására a következő megközelítést alkalmazzuk Dinamikus programozás (DP).
A leghosszabb kommunikációs sorozat rekurzív módszere
A fenti grafikon a rekurzív módszer. Minden rekurzív függvény rendelkezik egy alapesettel, amely megszakítja a rekurziót, vagy elkezd visszatérni a veremből.
Ehhez a megvalósításhoz alapesetet fogunk használni. Így 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
- Adjon át két mintát a függvénynek, és vegye fel a visszatérés 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.
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)
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
Megvalósítás pythonban
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)))
output:
Lenght of LCS is: 5
A leghosszabb közös részsorozat dinamikus programozási módszere (LCS)
A dinamikus programozás a sima rekurzív módszer optimalizálását jelenti. Például, ha látjuk a rekurzív vagy naiv megközelítésű gráfot, láthatjuk, hogy több azonos függvényhívás létezik. A dinamikus programozási módszer az összes számítást egy tömbben rögzíti, és szükség esetén használja.
2D tömböt fogunk használni mxn mérettel, ahol m és n a minta1 és minta2 hossza.
Minden 2D tömb, használhatunk List adatstruktúrákat a pythonban vagy vektor/tömb adatstruktúrákat C++.
Pszeudo kód a DP-t használó LCS-hez:
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]
Íme az LCS táblázat, amelyet 2D tömb adatstruktúraként használnak a dinamikus programozási megközelítéshez.
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áncból veszünk egy üres karakterláncot, és megpróbáljuk megtalálni a közös részsorozatokat. Mivel azonban az általunk vett részkarakterlánc üres, a részsorozat hossza 0.
Step 2) Ha két karakter egyezik, akkor az (i,j) indexhez rendeljük az értéket a korábban kiszámított LCS növelésével, amely az (i-1,j-1) indexben található (az előző sorból).
Step 3) Ha nem egyezik, akkor a szomszédos két index max. LCS-ét vesszük. És í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 & 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; }
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, egyszerűen csak egyszer számítunk ki minden feladatot a DP módszerben a DP módszerben. A rekurzív módszerben átfedő részproblémák lehetnek.
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 minta1[i] egyenlő minta2[j]-vel, akkor frissítse a DP[i][j] = DP[i-1][j-1] + 1
- Ha a minta1[i] nem egyenlő a 2[j] mintával, akkor DP[i][j] lesz a maximális érték DP[i-1][j] és DP[i][j-1] között.
- Folytassa addig, amíg i és j el nem éri m és n értékét.
- Az utolsó elem vagy DP[m-1][n-1] tartalmazza a hosszt.
Itt a címe DP[m-1][n-1], mivel a tömb indexe 0-tól kezdődik.
Összegzésként
- A DP módszer alacsonyabb időbonyolultságú; ez O(mn), ahol m és n a bemeneti karakterlánc vagy tömb hossza.
- A DP gyorsabb megközelítés, mint a rekurzív, időbonyolultságával O(n*2m).
- A dinamikus programozás (DP) nem memóriaoptimalizált. 2D tömböt használtunk, amelynek hossza m*n. Tehát a tér összetettsége (m*n).
- Rekurzív módszer, legrosszabb forgatókönyv esetén az általa elfoglalt legnagyobb memória m+n, lényegében a bevitt karakterlánc teljes hossza.
- A mai modern számítógépek elegendőek ilyen mennyiségű memória kezelésére.