Subsecuencia común más larga: Python, C++ Ejemplo

¿Cuál es la subsecuencia común más larga?

La subsecuencia común más larga (LCS) significa que se le darán dos cadenas/patrones/secuencias de objetos. Entre estas dos secuencias/cadenas, necesita encontrar la subsecuencia más larga de elementos en el mismo orden presentes en ambas cadenas o patrones.

Ejemplo

Por ejemplo, se proporcionan dos cadenas.

Supongamos que,

Patrón_1 = “RGBGARGA”
Patrón_2 = “BGRARG”

• A partir del patrón_1, se pueden producir secuencias como “RGB”, “RGGA”, “RGAR”. Para crear una secuencia, es necesario mantener la posición relativa de cada carácter en la cadena.
• Desde patrón_2, podemos producir secuencias como “BGR”, “BRAG”, “RARG”. Se pueden producir secuencias siempre que mantengan la posición relativa de la cadena original.

El término posición relativa significa orden.

Por ejemplo, "BRG" es una secuencia válida porque "B" apareció primero, luego "R" y luego "G" en el patrón de cadena original_2. Sin embargo, si una secuencia es "RBRG", no es válida. Porque en la cadena original (patrón_2), "B" viene primero.

Tenemos dos opciones para encontrar la subsecuencia común más larga de las dos secuencias o matrices dadas.

• método ingenuo
• Solución de programación dinámica: la subsecuencia común más larga también se conoce como LCS.

Una solución ingenua tiene una complejidad temporal mayor y no es la solución óptima. Mediante la solución de programación dinámica (PD), superamos el problema de la complejidad.

Método ingenuo

El método ingenuo es un enfoque simple del problema independientemente de la complejidad del tiempo y otros factores de optimización.

El método Naive consta de "fuerza bruta", múltiples bucles y métodos recursivos en la mayoría de los casos.

El término fuerza bruta significa recorrer todos los patrones posibles para un problema determinado.

Ejemplo

Del ejemplo anterior de patrón1 y patrón2, supongamos que el patrón1 tiene una longitud de my el patrón2 tiene una longitud de n. Para comprobar todos los casos posibles, necesitamos evaluar todas las subsecuencias posibles del patrón1 con el patrón2.

Aquí hay una cadena simple de 4 letras "ABCD". Por ejemplo, necesitamos crear una secuencia a partir de "ABCD". O podemos tomar un personaje o no. Eso significa que, para cada personaje, tenemos dos opciones.

Ellos son:

• El personaje se agregará a la subsecuencia.
• El personaje no se agregará a la subsecuencia.

Aquí las imágenes muestran todas las secuencias que podemos hacer a partir de la cadena “ABCD”.

Secuencia con 1 carácter:

Secuencias con 2 personajes:

Secuencias con 3 personajes:

Del diagrama anterior, hay 14 secuencias. Si no tomamos letras, básicamente una cadena vacía, las secuencias totales serán 15. Además, la cadena “ABCD” en sí es una secuencia. Entonces, las secuencias totales son 16.

Entonces, es posible generar 2⁴ o 16 subsecuencias de “ABCD”. Luego, una cuerda con una longitud de m tendrá que totalizar la subsecuencia de 2^m.

Para cada subsecuencia, debemos comprobar el patrón completo2. Esto llevará 0(n) tiempo. 0(n) significa la función de complejidad que calcula el tiempo que lleva la ejecución.

Por lo tanto, la complejidad temporal total se convierte en En 2^m). Para el ejemplo, hemos visto arriba el valor de m=8 y n=5.

Estos son los pasos del método ingenuo:

Paso 1) Tome una secuencia del patrón1.
Paso 2) Haga coincidir la secuencia del paso 1 con el patrón 2.
Paso 3) Si coincide, guarde la subsecuencia.
Paso 4) Si queda más secuencia en el patrón 1, vaya al paso 1 nuevamente.
Paso 5) Imprime la subsecuencia más larga.

Subestructura óptima

El término subestructura óptima significa que se puede encontrar una solución óptima (simple) resolviendo los subproblemas. Por ejemplo, en el ejemplo anterior, tenemos patrón1 y patrón2.

Paso 1) Toma los dos primeros caracteres de cada patrón.

Paso 2) Tome del tercero al quinto carácter de cada patrón.

Paso 3) Continúe de manera similar con los personajes restantes.

Encontramos el LCS en la subcadena (cadena generada a partir de una cadena original). Luego mantenemos el registro de la longitud del LCS de las subcadenas.

Ahora, aquí hay otra propiedad interesante que es subproblemas superpuestos. Se dice que un problema tiene subproblemas superpuestos si el planteamiento del problema puede dividirse en pequeños subproblemas y usarse varias veces en el programa.

El siguiente diagrama muestra que el algoritmo recursivo llamó a la función con el mismo parámetro varias veces.

Por ejemplo, veamos el árbol de recursividad.

En el cuadro de color oscuro, se pueden observar subproblemas superpuestos. (“RG”, “RA”), (“RG”, “R”) y otros se mencionan varias veces.

Para optimizar esto, tenemos el enfoque de Programación dinámica (PD).

Método recursivo de secuencia de comunicación más larga

El gráfico que se muestra arriba es el método recursivo. Cada función recursiva tiene un caso base para romper la recursividad o comenzar a regresar desde su pila.

Para esta implementación, usaremos un caso base. Entonces el algoritmo Es como lo siguiente:

• Si todos los elementos antes del último elemento coinciden, aumente la longitud en uno y regrese
• Pase dos patrones a la función y tome el valor máximo del retorno
• Si un patrón tiene longitud cero, entonces no tenemos ninguna subsecuencia para comparar. Devuelve 0 en este caso. Este es el caso base de la recursividad.

Pseudo código:

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)

Implementación en 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;
}

Salida:

Length of LCS is: 5

Implementación en 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("Lenght of LCS is: ", lcs(pattern_1, pattern_2, len(pattern_1), len(pattern_2)))

Salida:

Lenght of LCS is:  5

Método de programación dinámica de la subsecuencia común más larga (LCS)

La programación dinámica significa optimizar el método recursivo simple. Por ejemplo, si vemos el gráfico de enfoque recursivo o ingenuo, podemos ver que hay varias llamadas a funciones iguales. El método de programación dinámica registra todos los cálculos en una matriz y la utiliza cuando es necesario.

Usaremos una matriz 2D con dimensiones de m x n, donde myn son longitudes de patrón1 y patrón2.

Para los ensayos clínicos de CRISPR, Matriz 2DPodemos usar estructuras de datos de lista en Python o estructuras de datos vectoriales/matrices en C++.

Pseudocódigo para LCS usando 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]

Aquí está la tabla LCS que se utiliza como estructura de datos de matriz 2D para el enfoque de programación dinámica.

Analicemos la lógica que utilizamos aquí. Los pasos son:

Paso 1) Si i o j es cero, estamos tomando una cadena vacía de las dos cadenas dadas y tratando de encontrar las subsecuencias comunes. Sin embargo, como la subcadena que estamos tomando está vacía, la longitud de la subsecuencia es 0.

Paso 2) Si dos caracteres coinciden, asignaremos el valor al índice (i,j) incrementando el LCS previamente calculado, que está presente en el índice (i-1,j-1) (de la fila anterior).

Paso 3) Si no coincide, tomaremos el LCS máximo de los dos índices adyacentes. Y de esta manera, necesitamos completar todos los valores en la matriz 2D.

Paso 4) Finalmente, devolveremos el valor de la última celda del array 2D.

Básicamente, todos los valores de la matriz 2D contienen la longitud de subsecuencias comunes. Entre ellas, la última celda contiene la longitud de la subsecuencia común más larga.

Implementación en 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;
}

Salida:

Length of LCS: 5

Implementación en 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))

Salida:

Length of LCS: 5

Entonces, ambas cadenas tienen la subsecuencia común más larga de longitud 5.

En pocas palabras, simplemente calculamos cada tarea una vez en el método DP. En el método recursivo, es posible que tengamos subproblemas superpuestos.

En este algoritmo de programación dinámica, utilizamos una matriz 2D. Se proporcionarán dos cadenas (supongamos que ambas tienen longitud n). Entonces el espacio necesario en la matriz es n x n. Si las cadenas son lo suficientemente grandes, necesitaremos una versión optimizada para memoria de la solución DP.

La lógica simplificada que se adoptó en el código es:

• Declare una matriz 2D DP[m][n].
• Complete la primera fila y la primera columna de la matriz DP con 0.
• Tome i y j para la iteración.
• Si el patrón1[i] es igual al patrón2[j], actualice DP[i][j] = DP[i-1][j-1] + 1
• Si el patrón1[i] no es igual al patrón2[j], entonces DP[i][j] será el valor máximo entre DP[i-1][j] y DP[i][j-1].
• Continúe hasta que i y j lleguen a my n.
• El último elemento o DP[m-1][n-1], contendrá la longitud.

Aquí, se denomina DP[m-1][n-1], porque el índice de la matriz comienza desde 0.

Resumen

• El método DP tiene una complejidad temporal menor; es O(mn), donde m y n son la longitud de la cadena o matriz de entrada.
• DP es un enfoque más rápido que el recursivo, con la complejidad temporal de En 2^m).
• La programación dinámica (PD) no está optimizada para la memoria. Usamos una matriz 2D que tiene una longitud de m*n. Por lo tanto, la complejidad espacial es (m*n).
• Método recursivo, en el peor de los casos, la memoria más alta que ocupará será m+n, básicamente la longitud total de la cadena ingresada.
• La computadora moderna actual es suficiente para manejar esta cantidad de memoria.