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

Qual é a subsequência comum mais longa?

A Maior Subsequência Comum (LCS, na sigla em inglês) consiste em encontrar a maior subsequência de elementos presentes em ambas as strings, padrões ou sequências de objetos, na mesma ordem em que aparecem em cada uma delas.

Exemplo

Por exemplo, são fornecidas duas strings. Suponhamos que:

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

• A partir do padrão 1, podem ser produzidas sequências como “RGB”, “RGGA”, “RGAR”. Para criar uma sequência, é necessário manter a posição relativa de cada caractere na string.
• A partir do padrão 2, podemos produzir sequências como “BGR”, “BRAG”, “RARG”. 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” aparece primeiro, depois “R” e, por fim, “G” na string original pattern_2. No entanto, se a 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 apresenta maior complexidade temporal e não é a solução ótima. Utilizando a Programação Dinâmica (PD), superamos o problema da complexidade.

Método Ingênuo

O método ingênuo é uma abordagem simples para o problema, independentemente da complexidade temporal e de outros fatores de otimização. Consiste em "força bruta", múltiplos loops e chamadas recursivas na maioria dos casos. O termo força bruta significa percorrer 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 sequência simples de 4 letras: “ABCD”. Por exemplo, precisamos criar uma sequência a partir de “ABCD”. Podemos usar um caractere ou não. Isso significa que, para cada caractere, temos duas opções:

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

A partir do diagrama acima, existem 14 sequências. Se não considerarmos nenhuma letra, ou seja, uma sequência vazia, o total de sequências será 15. Além disso, a própria sequência “ABCD” é uma sequência. Portanto, o total de sequências é 16.

Portanto, é possível gerar 2^4 ou 16 subsequências a partir de “ABCD”. Em seguida, uma string com comprimento de m terá uma subsequência total de 2^m.

Para cada subsequência, precisamos verificar todo o padrão2. Isso levará um tempo O(n). O(n) significa a função de complexidade que calcula o tempo necessário para a execução.

Então, a complexidade total do tempo torna-se O(n*2^m). No exemplo que 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ão 1.
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 ainda houver sequências restantes no padrão 1, volte ao passo 1.
Passo 5) Imprima a subsequência mais longa.

Subestrutura Ótima

O termo subestrutura ótima significa que uma solução ótima pode ser encontrada resolvendo os subproblemas. Por exemplo, no exemplo acima, temos o padrão 1 e o padrão 2.

Passo 1) Selecione 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.

Estrutura recursiva do problema LCS

Encontramos a LCS (menor cadeia de caracteres) na subcadeia (uma cadeia gerada a partir de uma cadeia original). Em seguida, armazenamos o comprimento da LCS das subcadeias.

Agora, aqui está outra propriedade interessante que é sobreposiçãoping subproblemasDiz-se que um problema tem sobreposição.ping subproblemas se o enunciado do problema puder ser dividido em pequenos subproblemas e usados ​​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, observe a árvore de recursão. Na caixa escura, você pode notar sobreposições.ping subproblemas. (“RG”, “RA”), (“RG”, “R”), e outros são chamados várias vezes.

Para otimizar isso, adotamos a seguinte abordagem: Programaçao dinamica (DP).

Método recursivo da maior subsequência comum

O gráfico acima representa o método recursivo. Cada função recursiva possui um caso base para interromper a recursão ou iniciar o retorno a partir de sua pilha.

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

• Se todos os elementos anteriores ao último elemento tiverem uma correspondência, aumente o comprimento em um e retorne.
• Passe dois padrões para a função e pegue 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.

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

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

Saída:

Length of LCS is:  5

Método de Programação Dinâmica da Maior Subsequência Comum (LCS)

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

Usaremos uma matriz 2D com dimensões m x n, onde m e n são os comprimentos de pattern1 e pattern2. Para um Matriz 2D, podemos usar estruturas de dados de lista em Python ou estruturas de dados vetoriais/de matriz em C++.

Apelido 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]

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

Vamos discutir a lógica que usamos aqui. Os passos são:

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

Passo 2) Se dois caracteres coincidirem, 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) Caso não haja correspondência, utilizaremos o menor múltiplo comum (MMC) dos dois índices adjacentes. Dessa forma, precisamos preencher todos os valores na matriz bidimensional.

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

Basicamente, todos os valores na matriz 2D contêm o comprimento de subsequências comuns. Dentre elas, 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 < 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;
}

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.

Em resumo, no método de programação dinâmica, calculamos cada tarefa apenas uma vez. No método recursivo, poderíamos ter sobreposição de tarefas.ping subproblemas.

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 pattern1[i] for igual a pattern2[j], então atualize DP[i][j] = DP[i-1][j-1] + 1.
• Se pattern1[i] não for igual a pattern2[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, DP[m-1][n-1], conterá o comprimento.

Aqui, é referido como DP[m-1][n-1] porque o índice da matriz começa em 0.

Perguntas Frequentes