Subsequência comum mais longa: exemplo de Python, C++

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.

Subsequência Comum Mais Longa

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 tempo maiorplexe não é a solução ideal. Usando a Solução de Programação Dinâmica (DP), superamos o complexproblema da cidade.

Método Ingênuo

O método ingênuo é uma abordagem simples para o problema, independentemente do momento.plexqualidade e 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”.

Método Ingênuo

Sequência com 1 caractere:

Método Ingênuo

Sequências com 2 caracteres:

Método Ingênuo

Sequências com 3 caracteres:

Método Ingênuo

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 24 ou 16 subsequências de “ABCD”. Então, uma corda com comprimento de m terá que totalizar a subsequência de 2m.

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

Então, tempo total complextorna-se O(n*2m). 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.

Subestrutura Ótima
Estrutura recursiva do problema LCS

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.

Subestrutura Ótima

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

Na cor escura box, 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 seguintewing:

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

Escolha Matriz 2D, podemos usar estruturas de dados List em python ou estruturas de dados vetoriais/array 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.

Método de programação dinâmica de LCS

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 tempo complexcidade; é 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 o tempo chegandoplexcidade de O(n*2m).
  • A programação dinâmica (DP) não é otimizada para memória. Usamos um array 2D com comprimento m*n. Então, o espaço complexidade é (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.