Subsequência comum mais longa: Python, C++ Exemplo

Qual é a subsequência comum mais longa?

Longest Common Subsequence (LCS) significa que você receberá duas strings/padrões/sequências de objetos. Entre essas duas sequências/strings, você precisa encontrar a maior subsequência de elementos na mesma ordem presente em ambas as strings ou padrões.

Exemplo

Por exemplo, existem duas strings fornecidas.

Vamos supor que,

Padrão_1 = “RGBGARGA”
Padrão_2 = “BGRARG”

• A partir do padrão_1, sequências podem ser produzidas como “RGB”, “RGGA”, ”RGAR”. Para criar uma sequência, você precisa manter a posição relativa de cada caractere na string.
• A partir do padrão_2, podemos produzir sequências como “BGR”, ”BRAG”, ”RARG”. As sequências podem ser produzidas desde que mantenham a posição relativa da string original.

O termo posição relativa significa ordem.

Por exemplo, “BRG” é uma sequência válida porque “B” apareceu primeiro, depois “R” e depois “G” na string original pattern_2. Porém, se uma sequência for “RBRG”, ela não é válida. Porque na string original (pattern_2), “B” vem primeiro.

Temos duas opções para encontrar a maior subsequência comum das duas sequências ou matrizes fornecidas.

• Método ingênuo
• Solução de programação dinâmica: a maior subsequência comum também é conhecida como LCS.

Uma solução ingênua tem maior complexidade de tempo e não é a solução ideal. Usando a Solução de Programação Dinâmica (DP), superamos o problema de complexidade.

Método Ingênuo

O método ingênuo é uma abordagem simples para o problema, independentemente da complexidade do tempo e de outros fatores de otimização.

O método Naive consiste em “Força Bruta”, múltiplos loops, métodos recursivos na maioria dos casos.

O termo força bruta significa passar por todos os padrões possíveis para um determinado problema.

Exemplo

A partir do exemplo acima de padrão1 e padrão2, vamos supor que o padrão1 tenha um comprimento m e o padrão2 tenha um comprimento n. Para verificar todos os casos possíveis, precisamos avaliar todas as subsequências possíveis do padrão1 com o padrão2.

Aqui está uma string simples de 4 letras “ABCD”. Por exemplo, precisamos criar uma sequência de “ABCD”. Podemos pegar um personagem ou não. Isso significa que, para cada personagem, temos duas opções.

Eles são:

• O personagem será adicionado à subsequência.
• O caractere não será adicionado à subsequência.

Aqui, as imagens mostram todas as sequências que podemos fazer a partir da string “ABCD”.

Sequência com 1 caractere:

Sequências com 2 caracteres:

Sequências com 3 caracteres:

No diagrama acima, existem 14 sequências. Se não pegarmos letras, basicamente uma string vazia, o total de sequências será 15. Além disso, a própria string “ABCD” é uma sequência. Portanto, o total de sequências é 16.

Então, é possível gerar 2⁴ ou 16 subsequências de “ABCD”. Então, uma corda com comprimento de m terá que totalizar a subsequência de 2^m.

Para cada subsequência, precisamos verificá-la para todo o padrão2. Levará 0(n) tempo. 0(n) significa a função de complexidade que calcula o tempo necessário para execução.

Então, a complexidade total do tempo torna-se O(n*2^m). Por exemplo, vimos acima o valor de m=8 e n=5.

Aqui estão as etapas do Método Ingênuo:

Passo 1) Pegue uma sequência do padrão1.
Passo 2) Combine a sequência da etapa 1 com o padrão 2.
Passo 3) Se corresponder, salve a subsequência.
Passo 4) Se sobrar mais sequência no padrão1, vá para a etapa 1 novamente.
Passo 5) Imprima a subsequência mais longa.

Subestrutura Ótima

O termo subestrutura ótima significa que uma solução ótima (simples) pode ser encontrada resolvendo os subproblemas. Por exemplo, no exemplo acima, temos padrão1 e padrão2.

Passo 1) Pegue os dois primeiros caracteres de cada padrão

Passo 2) Pegue o terceiro ao quinto caracteres de cada padrão.

Passo 3) Continue da mesma forma com os caracteres restantes.

Encontramos o LCS na substring (string gerada a partir de uma string original). Em seguida, mantemos o registro do comprimento do LCS das substrings.

Agora, aqui está outra propriedade interessante que é subproblemas sobrepostos. Diz-se que um problema tem subproblemas sobrepostos se a definição do problema puder ser dividida em pequenos subproblemas e usada várias vezes no programa.

O diagrama abaixo mostra que o algoritmo recursivo chamou a função com o mesmo parâmetro várias vezes.

Por exemplo, vamos ver a árvore de recursão.

Na caixa escura, você pode notar subproblemas sobrepostos. (“RG”, “RA”), (“RG”,”R”) e outros são chamados diversas vezes.

Para otimizar isso, temos a abordagem de Programaçao dinamica (DP).

Método recursivo de sequência de comunicação mais longa

O gráfico mostrado acima é o método recursivo. Cada função recursiva possui um caso base para quebrar a recursão ou começar a retornar de sua pilha.

Para esta implementação, usaremos um caso base. Então o algoritmo é como o seguinte:

• Se todos os elementos antes do último elemento corresponderem, aumente o comprimento em um e retorne
• Passe dois padrões para a função e obtenha o valor máximo do retorno
• Se um padrão tiver comprimento zero, não teremos subsequência para comparar. Retorne 0 neste caso. Este é o caso base da recursão.

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)

Implementação em 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;
}

Saída:

Length of LCS is: 5

Implementação em 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)))

Saída:

Lenght of LCS is:  5

Método de programação dinâmica de maior subsequência comum (LCS)

Programação dinâmica significa otimizar o método recursivo simples. Por exemplo, se observarmos o gráfico de abordagem recursiva ou ingênua, podemos ver que existem várias chamadas de função iguais. O método de Programação Dinâmica registra todos os cálculos em um array e o utiliza quando necessário.

Usaremos um array 2D com dimensões de mxn, onde m e n são comprimentos de padrão1 e padrão2.

Para Matriz 2D, podemos usar estruturas de dados de lista em python ou estruturas de dados de vetor/matriz em 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]

Aqui está a tabela LCS que é usada como uma estrutura de dados de array 2D para a abordagem de programação dinâmica.

Vamos discutir a lógica que usamos aqui. As etapas são:

Passo 1) Se i ou j for zero, estamos pegando uma string vazia das duas strings fornecidas e tentando encontrar as subsequências comuns. No entanto, como a substring que estamos pegando está vazia, o comprimento da subsequência é 0.

Passo 2) Se dois caracteres corresponderem, atribuiremos o valor ao índice (i,j) incrementando o LCS calculado anteriormente, que está presente no índice (i-1,j-1) (da linha anterior).

Passo 3) Se não corresponder, pegaremos o LCS máximo dos dois índices adjacentes. E desta forma, precisamos preencher todos os valores do array 2D.

Passo 4) Por fim, retornaremos o valor da última célula do array 2D.

Basicamente, todo o valor na matriz 2D contém o comprimento das subsequências comuns. Entre estas, a última célula contém o comprimento da subsequência comum mais longa.

Implementação em 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;
}

Saída:

Length of LCS: 5

Implementação em 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))

Saída:

Length of LCS: 5

Portanto, ambas as strings têm a subsequência comum mais longa de comprimento 5.

Resumindo, estamos simplesmente calculando cada tarefa uma vez no método DP. No método recursivo, podemos ter subproblemas sobrepostos.

Neste algoritmo de programação dinâmica, estamos usando uma matriz 2D. Serão fornecidas duas strings (suponha que ambas tenham comprimento n). Então o espaço necessário no array é nx n. Se as strings forem grandes o suficiente, precisaremos de uma versão da solução DP com otimização de memória.

A lógica simplificada que foi usada no código é:

• Declare uma matriz 2D DP[m][n].
• Preencha a primeira linha e a primeira coluna da matriz DP com 0.
• Pegue i e j para a iteração.
• Se padrão1[i] for igual a padrão2[j], então atualize DP[i][j] = DP[i-1][j-1] + 1
• Se padrão1[i] não for igual a padrão2[j], então DP[i][j] será o valor máximo entre DP[i-1][j] e DP[i][j-1].
• Continue até que i e j alcancem m e n.
• O último elemento ou DP[m-1][n-1], conterá o comprimento.

Aqui, é endereçado como DP[m-1][n-1], porque o índice do array começa em 0.

Resumo

• O método DP possui menor complexidade de tempo; é O (mn), onde m e n são o comprimento da string ou matriz de entrada.
• DP é uma abordagem mais rápida que a recursiva, com a complexidade de tempo de O(n*2^m).
• A programação dinâmica (DP) não é otimizada para memória. Usamos um array 2D com comprimento m*n. Portanto, a complexidade do espaço é (m*n).
• Método recursivo, na pior das hipóteses, a maior memória que ocupará será m+n, basicamente o comprimento total da string inserida.
• O computador moderno de hoje é suficiente para lidar com essa quantidade de memória.