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

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

El problema de la subsecuencia común más larga (LCS, por sus siglas en inglés) consiste en darte dos cadenas, patrones o secuencias de objetos. Entre estas dos secuencias o cadenas, debes encontrar la subsecuencia más larga de elementos que se encuentren en el mismo orden en ambas cadenas o patrones.

Ejemplo

Por ejemplo, se proporcionan dos cadenas de texto. Supongamos que:

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

• A partir del patrón 1, se pueden generar secuencias como “RGB”, “RGGA” y “RGAR”. Para crear una secuencia, es necesario mantener la posición relativa de cada carácter en la cadena.
• A partir del patrón 2, podemos generar secuencias como "BGR", "BRAG" y "RARG". Estas secuencias se pueden generar 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 después “G” en el patrón de cadena original pattern_2. Sin embargo, si la secuencia es “RBRG”, no es válida, porque en la cadena original (pattern_2), “B” aparece 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 mayor complejidad temporal y no es la solución óptima. Mediante la programación dinámica (PD), superamos el problema de la complejidad.

Método ingenuo

El método ingenuo es una solución sencilla al problema, independientemente de la complejidad temporal y otros factores de optimización. Consiste en un método de "fuerza bruta", con múltiples bucles y, en la mayoría de los casos, llamadas recursivas. El término "fuerza bruta" se refiere a probar todos los patrones posibles para un problema dado.

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í tenemos una cadena simple de 4 letras: “ABCD”. Por ejemplo, necesitamos crear una secuencia a partir de “ABCD”. Podemos tomar un carácter o no. Esto significa que, para cada carácter, tenemos dos opciones:

• 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:

En el diagrama anterior, hay 14 secuencias. Si no consideramos ninguna letra, es decir, una cadena vacía, el total de secuencias sería 15. Además, la cadena "ABCD" es una secuencia en sí misma, por lo que el total de secuencias sería 16.

Entonces, es posible generar 2^4 o 16 subsecuencias a partir de “ABCD”. Luego, una cadena con una longitud de m tendrá una subsecuencia total de 2^m.

Para cada subsecuencia, debemos verificarla para todo el patrón2. Esto tomará un tiempo O(n). O(n) representa la función de complejidad que calcula el tiempo de ejecución.

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

Estos son los pasos del método ingenuo:

Paso 1) Toma una secuencia del patrón1.
Paso 2) Relaciona la secuencia del paso 1 con el patrón 2.
Paso 3) Si coincide, guarde la subsecuencia.
Paso 4) Si quedan más secuencias en el patrón1, vuelva al paso 1.
Paso 5) Imprime la subsecuencia más larga.

Subestructura óptima

El término subestructura óptima significa que se puede encontrar una solución óptima 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.

Estructura recursiva del problema LCS

Calculamos la LCS (compartición común más larga) de la subcadena (una cadena generada a partir de la cadena original). Luego, registramos la longitud de la LCS de las subcadenas.

Ahora, aquí hay otra propiedad interesante que es superposiciónping subproblemasSe dice que un problema tiene superposición.ping subproblemas si el enunciado del problema se puede dividir en subproblemas más pequeños y utilizarse 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, observe el árbol de recursión. En el recuadro oscuro, puede notar la superposición.ping subproblemas. (“RG”, “RA”), (“RG”, “R”) y otros se llaman varias veces.

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

Método recursivo de la subsecuencia común más larga

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

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

• Si todos los elementos anteriores al último elemento coinciden, entonces aumenta la longitud en uno y regresa.
• Pasa dos patrones a la función y toma el valor máximo del resultado.
• 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.

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

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

Salida:

Length 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 consiste en optimizar el método recursivo simple. Por ejemplo, si observamos el grafo del enfoque recursivo o ingenuo, podemos ver que hay varias llamadas a funciones idénticas. El método de programación dinámica registra todos los cálculos en un array y los reutiliza cuando es necesario.

Usaremos una matriz 2D con dimensiones de mxn, donde m y n son las longitudes de patrón1 y patrón2. Para un Matriz 2D, podemos usar estructuras de datos de lista en Python o estructuras de datos vectoriales/de matriz en C++.

Apodo Code 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, tomamos una cadena vacía de las dos cadenas dadas e intentamos encontrar las subsecuencias comunes. Sin embargo, como la subcadena que tomamos 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 calculado previamente, que está presente en el índice (i-1,j-1) (de la fila anterior).

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

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

Básicamente, todos los valores de la matriz bidimensional 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 < 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;
}

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 resumen, en el método DP simplemente calculamos cada tarea una vez. En el método recursivo, podríamos tener superposición.ping subproblemas.

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 pattern1[i] es igual a pattern2[j], entonces actualiza DP[i][j] = DP[i-1][j-1] + 1.
• Si pattern1[i] no es igual a pattern2[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, DP[m-1][n-1], contendrá la longitud.

Aquí se le denomina DP[m-1][n-1] porque el índice del array comienza desde 0.

Preguntas Frecuentes