Najdlhšia spoločná následnosť

V tomto tutoriále sa dozviete, ako sa nachádza najdlhšia bežná subsekvencia. Nájdete tiež pracovné príklady najdlhšej bežnej subsekvencie v jazykoch C, C ++, Java a Python.

Najdlhšia spoločná subsekvencia (LCS) je definovaná ako najdlhšia subsekvencia, ktorá je spoločná pre všetky dané sekvencie, za predpokladu, že prvky subsekvencie nie sú povinné na obsadenie po sebe nasledujúcich pozícií v pôvodných sekvenciách.

Ak S1 a S2 sú dve dané sekvencie, potom Z je spoločná subsekvencia S1 a S2, ak Z je subsekvencia oboch S1 a S2. Ďalej musí byť Z striktne rastúcou postupnosťou indexov tak S1, ako aj S2.

V striktne rastúcej sekvencii musia byť indexy prvkov vybraných z pôvodných sekvencií vzostupne v Z.

 S1 = (B, C, D, A, A, C, D)

Potom (A, D, B)nemôže byť subsekvencia S1, pretože poradie prvkov nie je rovnaké (tj. Striktne nezvyšuje postupnosť).

Pochopme LCS na príklade.

 S1 = (B, C, D, A, A, C, D) S2 = (A, C, D, B, A, C)

Potom sú spoločné subsekvencie (B, C), (C, D, A, C), (D, A, C), (A, A, C), (A, C), (C, D), …

Medzi týmito subsekvenciami (C, D, A, C)je najdlhšia spoločná subsekvencia. Túto najdlhšiu bežnú subsekvenciu nájdeme pomocou dynamického programovania.

Predtým, ako budete pokračovať, ak ešte neviete o dynamickom programovaní, prečítajte si prosím dynamické programovanie.

Použitie dynamického programovania na nájdenie LCS

Zoberme si dve sekvencie:

Prvá sekvencia

Druhá sekvencia

Nasledujú nasledujúce kroky na vyhľadanie najdlhšej bežnej subsekvencie.

Vytvorte rozmerovú tabuľku, n+1*m+1kde n a m sú dĺžky X a Y. Prvý riadok a prvý stĺpec sú vyplnené nulami. Inicializujte tabuľku
Vyplňte každú bunku tabuľky pomocou nasledujúcej logiky.
Ak sa znaky zodpovedajúce aktuálnemu riadku a aktuálnemu stĺpcu zhodujú, vyplňte aktuálnu bunku tak, že do diagonálneho prvku pridáte jednu. Nasmerujte šípku na diagonálnu bunku.
Inak vezmite maximálnu hodnotu z predchádzajúceho stĺpca a prvku predchádzajúceho riadku na vyplnenie aktuálnej bunky. Nasmerujte šípku na bunku s maximálnou hodnotou. Ak sú si rovní, ukážte na niektorého z nich. Vyplňte hodnoty
Krok 2 sa opakuje, kým sa tabuľka nezaplní. Vyplňte všetky hodnoty
Hodnota v poslednom riadku a poslednom stĺpci je dĺžka najdlhšej spoločnej subsekvencie. Pravý dolný roh je dĺžka LCS
Ak chcete nájsť najdlhšiu spoločnú subsekvenciu, začnite od posledného prvku a postupujte podľa smeru šípky. Prvky zodpovedajúce symbolu () tvoria najdlhšiu spoločnú podsekvenciu. Vytvorte cestu podľa šípok

Najdlhšou spoločnou subsekvenciou je teda CD.

LCS

Ako je algoritmus dynamického programovania efektívnejší ako rekurzívny algoritmus pri riešení problému s LCS?

Metóda dynamického programovania znižuje počet volaní funkcií. Ukladá výsledok každého volania funkcie, aby ho bolo možné použiť v budúcich hovoroch bez potreby nadbytočných hovorov.

Vo vyššie uvedenom dynamickom algoritme sú výsledky získané z každého porovnania prvkov X a prvkov Y uložené v tabuľke, aby ich bolo možné použiť v budúcich výpočtoch.

Takže čas potrebný na dynamický prístup je čas potrebný na vyplnenie tabuľky (tj. O (mn)). Zatiaľ čo algoritmus rekurzie má zložitosť 2 ^{max (m, n)} .

Algoritmus najdlhšej bežnej následnosti

 X a Y sú dve dané sekvencie Inicializujte tabuľku LCS s rozmerom X.length * Y.length X.label = X Y.label = Y LCS (0) () = 0 LCS () (0) = 0 Začať od LCS ( 1) (1) Porovnajte X (i) a Y (j) Ak X (i) = Y (j) LCS (i) (j) = 1 + LCS (i-1, j-1) Ukážte šípkou na LCS (i) (j) Iné LCS (i) (j) = max (LCS (i-1) (j), LCS (i) (j-1)) Nasmerujte šípku na maximum (LCS (i-1) ( j), LCS (i) (j-1))

Príklady jazyka Python, Java a C / C ++

Python Java C C ++

 # The longest common subsequence in Python # Function to find lcs_algo def lcs_algo(S1, S2, m, n): L = ((0 for x in range(n+1)) for x in range(m+1)) # Building the mtrix in bottom-up way for i in range(m+1): for j in range(n+1): if i == 0 or j == 0: L(i)(j) = 0 elif S1(i-1) == S2(j-1): L(i)(j) = L(i-1)(j-1) + 1 else: L(i)(j) = max(L(i-1)(j), L(i)(j-1)) index = L(m)(n) lcs_algo = ("") * (index+1) lcs_algo(index) = "" i = m j = n while i> 0 and j> 0: if S1(i-1) == S2(j-1): lcs_algo(index-1) = S1(i-1) i -= 1 j -= 1 index -= 1 elif L(i-1)(j)> L(i)(j-1): i -= 1 else: j -= 1 # Printing the sub sequences print("S1 : " + S1 + "S2 : " + S2) print("LCS: " + "".join(lcs_algo)) S1 = "ACADB" S2 = "CBDA" m = len(S1) n = len(S2) lcs_algo(S1, S2, m, n)

 // The longest common subsequence in Java class LCS_ALGO ( static void lcs(String S1, String S2, int m, int n) ( int()() LCS_table = new int(m + 1)(n + 1); // Building the mtrix in bottom-up way for (int i = 0; i <= m; i++) ( for (int j = 0; j <= n; j++) ( if (i == 0 || j == 0) LCS_table(i)(j) = 0; else if (S1.charAt(i - 1) == S2.charAt(j - 1)) LCS_table(i)(j) = LCS_table(i - 1)(j - 1) + 1; else LCS_table(i)(j) = Math.max(LCS_table(i - 1)(j), LCS_table(i)(j - 1)); ) ) int index = LCS_table(m)(n); int temp = index; char() lcs = new char(index + 1); lcs(index) = ''; int i = m, j = n; while (i> 0 && j> 0) ( if (S1.charAt(i - 1) == S2.charAt(j - 1)) ( lcs(index - 1) = S1.charAt(i - 1); i--; j--; index--; ) else if (LCS_table(i - 1)(j)> LCS_table(i)(j - 1)) i--; else j--; ) // Printing the sub sequences System.out.print("S1 : " + S1 + "S2 : " + S2 + "LCS: "); for (int k = 0; k <= temp; k++) System.out.print(lcs(k)); System.out.println(""); ) public static void main(String() args) ( String S1 = "ACADB"; String S2 = "CBDA"; int m = S1.length(); int n = S2.length(); lcs(S1, S2, m, n); ) )

 // The longest common subsequence in C #include #include int i, j, m, n, LCS_table(20)(20); char S1(20) = "ACADB", S2(20) = "CBDA", b(20)(20); void lcsAlgo() ( m = strlen(S1); n = strlen(S2); // Filling 0's in the matrix for (i = 0; i <= m; i++) LCS_table(i)(0) = 0; for (i = 0; i <= n; i++) LCS_table(0)(i) = 0; // Building the mtrix in bottom-up way for (i = 1; i <= m; i++) for (j = 1; j = LCS_table(i)(j - 1)) ( LCS_table(i)(j) = LCS_table(i - 1)(j); ) else ( LCS_table(i)(j) = LCS_table(i)(j - 1); ) ) int index = LCS_table(m)(n); char lcsAlgo(index + 1); lcsAlgo(index) = ''; int i = m, j = n; while (i> 0 && j> 0) ( if (S1(i - 1) == S2(j - 1)) ( lcsAlgo(index - 1) = S1(i - 1); i--; j--; index--; ) else if (LCS_table(i - 1)(j)> LCS_table(i)(j - 1)) i--; else j--; ) // Printing the sub sequences printf("S1 : %s S2 : %s ", S1, S2); printf("LCS: %s", lcsAlgo); ) int main() ( lcsAlgo(); printf(""); )

 // The longest common subsequence in C++ #include using namespace std; void lcsAlgo(char *S1, char *S2, int m, int n) ( int LCS_table(m + 1)(n + 1); // Building the mtrix in bottom-up way for (int i = 0; i <= m; i++) ( for (int j = 0; j <= n; j++) ( if (i == 0 || j == 0) LCS_table(i)(j) = 0; else if (S1(i - 1) == S2(j - 1)) LCS_table(i)(j) = LCS_table(i - 1)(j - 1) + 1; else LCS_table(i)(j) = max(LCS_table(i - 1)(j), LCS_table(i)(j - 1)); ) ) int index = LCS_table(m)(n); char lcsAlgo(index + 1); lcsAlgo(index) = ''; int i = m, j = n; while (i> 0 && j> 0) ( if (S1(i - 1) == S2(j - 1)) ( lcsAlgo(index - 1) = S1(i - 1); i--; j--; index--; ) else if (LCS_table(i - 1)(j)> LCS_table(i)(j - 1)) i--; else j--; ) // Printing the sub sequences cout << "S1 : " << S1 << "S2 : " << S2 << "LCS: " << lcsAlgo << ""; ) int main() ( char S1() = "ACADB"; char S2() = "CBDA"; int m = strlen(S1); int n = strlen(S2); lcsAlgo(S1, S2, m, n); )