Nejdelší společná posloupnost

V tomto kurzu se dozvíte, jak je nalezena nejdelší běžná subsekvence. Také najdete pracovní příklady nejdelší běžné subsekvence v C, C ++, Javě a Pythonu.

Nejdelší společná posloupnost (LCS) je definována jako nejdelší posloupnost, která je společná pro všechny dané sekvence, za předpokladu, že prvky subsekvence nejsou nutné k obsazení po sobě jdoucích pozic v původních sekvencích.

Pokud jsou S1 a S2 dvě dané sekvence, pak Z je společná subsekvence S1 a S2, pokud Z je subsekvence jak S1, tak S2. Dále musí být Z přísně rostoucí posloupnost indexů jak S1, tak S2.

V přísně rostoucí sekvenci musí být indexy prvků vybraných z původních sekvencí ve vzestupném pořadí v Z.

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

Potom (A, D, B)nemůže být subsekvence S1, protože pořadí prvků není stejné (tj. Striktně nezvyšuje sekvenci).

Pochopme LCS na příkladu.

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

Pak jsou běžné subsekvence (B, C), (C, D, A, C), (D, A, C), (A, A, C), (A, C), (C, D), …

Mezi těmito subsekvencemi (C, D, A, C)je nejdelší společná posloupnost. Tuto nejdelší běžnou subsekvenci najdeme pomocí dynamického programování.

Než budete pokračovat, pokud ještě nevíte o dynamickém programování, projděte si prosím dynamické programování.

Použití dynamického programování k nalezení LCS

Vezměme si dvě sekvence:

První sekvence

Druhá sekvence

Následující kroky slouží k vyhledání nejdelší společné posloupnosti.

Vytvořte tabulku dimenzí, n+1*m+1kde n a m jsou délky X, respektive Y. První řádek a první sloupec jsou vyplněny nulami. Inicializujte tabulku
Vyplňte každou buňku tabulky pomocí následující logiky.
Pokud se znaky odpovídající aktuálnímu řádku a aktuálnímu sloupci shodují, vyplňte aktuální buňku přidáním jedné k diagonálnímu prvku. Namiřte šipku na diagonální buňku.
Jinak vezměte maximální hodnotu z předchozího sloupce a předchozího řádku pro vyplnění aktuální buňky. Nasměrujte šipku na buňku s maximální hodnotou. Pokud jsou si rovni, ukažte na někoho z nich. Vyplňte hodnoty
Krok 2 se opakuje, dokud není tabulka naplněna. Vyplňte všechny hodnoty
Hodnota v posledním řádku a posledním sloupci je délka nejdelší společné posloupnosti. Pravý dolní roh je délka LCS
Chcete-li najít nejdelší společnou posloupnost, začněte od posledního prvku a postupujte podle směru šipky. Prvky odpovídající symbolu () tvoří nejdelší společnou posloupnost. Vytvořte cestu podle šipek

Nejdelší běžnou subsekvenci je tedy CD.

LCS

Jak je algoritmus dynamického programování efektivnější než rekurzivní algoritmus při řešení problému LCS?

Metoda dynamického programování snižuje počet volání funkcí. Ukládá výsledek každého volání funkce, aby jej bylo možné použít v budoucích voláních bez nutnosti nadbytečných hovorů.

Ve výše uvedeném dynamickém algoritmu jsou výsledky získané z každého srovnání prvků X a prvků Y uloženy v tabulce, aby je bylo možné použít v budoucích výpočtech.

Čas potřebný pro dynamický přístup je tedy čas potřebný k vyplnění tabulky (tj. O (mn)). Zatímco algoritmus rekurze má složitost 2 ^{max (m, n)} .

Nejdelší běžný algoritmus následné posloupnosti

 X a Y jsou dvě dané sekvence Inicializovat tabulku LCS dimenze X.length * Y.length X.label = X Y.label = Y LCS (0) () = 0 LCS () (0) = 0 Začátek od LCS ( 1) (1) Porovnejte X (i) a Y (j) Pokud X (i) = Y (j) LCS (i) (j) = 1 + LCS (i-1, j-1) Ukažte šipkou na LCS (i) (j) Jinak LCS (i) (j) = max (LCS (i-1) (j), LCS (i) (j-1)) Nasměrujte šipku na maximum (LCS (i-1) ( j), LCS (i) (j-1))

Python, Java a C / C ++ příklady

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); )