最長共通部分列: Python, C++ 例:

最長共通部分列とは何ですか?

最長共通部分列（LCS）とは、2つの文字列、パターン、またはオブジェクトのシーケンスが与えられたときに、それらの文字列またはシーケンスの中から、両方の文字列またはパターンに同じ順序で存在する要素の最長部分列を見つける問題です。

例:

例えば、2つの文字列が与えられているとします。以下のように仮定しましょう。

パターン_1 = 「RGBGARGA」
パターン_2 = 「BGRARG」

• パターン1から、「RGB」、「RGGA」、「RGAR」などのシーケンスを生成できます。シーケンスを作成するには、文字列内の各文字の相対位置を維持する必要があります。
• パターン2からは、「BGR」、「BRAG」、「RARG」のようなシーケンスを生成できます。元の文字列の相対位置を維持する限り、シーケンスを生成できます。

相対位置という用語は順序を意味します。

例えば、「BRG」は有効なシーケンスです。なぜなら、元の文字列パターン2では「B」が最初に現れ、「R」が次に現れ、「G」が次に現れるからです。しかし、「RBRG」というシーケンスは無効です。なぜなら、元の文字列（パターン2）では「B」が最初に現れるからです。

指定された XNUMX つのシーケンスまたは配列から最長共通部分シーケンスを見つけるには XNUMX つのオプションがあります。

• 素朴な方法
• 動的プログラミング ソリューション: 最長共通部分列は LCS とも呼ばれます。

単純な解法は時間計算量が大きく、最適解ではありません。動的計画法（DP）を用いることで、この計算量の問題を克服できます。

素朴な方法

ナイーブ法は、時間計算量やその他の最適化要因に関係なく、問題に対する単純なアプローチです。ほとんどの場合、「総当たり」、複数のループ、および再帰呼び出しで構成されます。総当たりとは、与えられた問題に対して考えられるすべてのパターンを網羅的に調べることを意味します。

例:

上記のパターン 1 とパターン 2 の例から、パターン 1 の長さが m、パターン 2 の長さが n であると仮定します。 考えられるすべてのケースをチェックするには、パターン 1 の考えられるすべてのサブシーケンスをパターン 2 で評価する必要があります。

ここに「ABCD」という4文字の文字列があります。例えば、「ABCD」からシーケンスを作成する必要があります。文字を選択するかしないかのどちらかです。つまり、各文字に対して2つの選択肢があります。

• 文字がサブシーケンスに追加されます。
• 文字はサブシーケンスには追加されません。

ここで、画像は文字列「ABCD」から作成できるすべてのシーケンスを示しています。

1 文字のシーケンス:

2 文字のシーケンス:

3 文字のシーケンス:

上記の図から、14個のシーケンスが確認できます。文字を一切使用しない場合、つまり空の文字列の場合、シーケンスの総数は15個になります。さらに、「ABCD」という文字列自体もシーケンスです。したがって、シーケンスの総数は16個になります。

したがって、「ABCD」から 2^4 または 16 個の部分列を生成することが可能です。次に、長さが m 合計で 2^m 個の部分列を持つことになります。

各部分シーケンスについて、パターン2全体をチェックする必要があります。これにはO(n)の時間がかかります。O(n)とは、実行にかかる時間を計算する複雑度関数を意味します。

したがって、総時間計算量は O(n*2^m)。 上記の例では、m=8、n=5 となります。

Naive Method の手順は次のとおりです。

ステップ1） パターン1からシーケンスを取得します。
ステップ2） ステップ1のシーケンスをパターン2と照合してください。
ステップ3） 一致する場合は、サブシーケンスを保存します。
ステップ4） パターン1にまだシーケンスが残っている場合は、ステップ1に戻ります。
ステップ5） 最長のサブシーケンスを出力します。

最適な下部構造

最適部分構造という用語は、部分問題を解くことによって最適解を見つけることができることを意味します。例えば、上記の例では、パターン1とパターン2があります。

ステップ1） それぞれのパターンから最初の2文字を取り出します。

ステップ2） 各パターンから XNUMX 番目から XNUMX 番目の文字を取り出します。

ステップ3） 残りの文字も同様に続けます。

LCS問題の再帰構造

部分文字列（元の文字列から生成された文字列）の最長共通部分文字列（LCS）を求めます。そして、部分文字列のLCSの長さを記録します。

さて、ここにもう XNUMX つの興味深いプロパティがあります。 オーバーラップping サブ問題問題には重複があると言われますping 問題文を小さなサブ問題に分割し、プログラム内で複数回使用できる場合は、サブ問題と呼びます。

以下の図は、再帰アルゴリズムが同じパラメーターを持つ関数を複数回呼び出したことを示しています。

例えば、再帰ツリーを見てください。濃い色の枠内には、重なりが見られます。ping 部分問題。（「RG」、「RA」）、（「RG」、「R」）などが複数回呼び出されます。

これを最適化するには、次のようなアプローチがあります。 動的計画法 （DP）。

最長共通部分列の再帰的方法

上記のグラフは再帰的なメソッドを示しています。各再帰関数には、再帰を中断したり、スタックから戻り始めるための基本ケースがあります。

この実装では、基本ケースを使用します。 アルゴリズム は次のようになります。

• 最後の要素より前のすべての要素に一致するものがあれば、長さを1つ増やして返す。
• 関数に2つのパターンを渡し、戻り値の最大値を取得します。
• 0 つのパターンの長さがゼロの場合、比較するサブシーケンスはありません。 この場合は XNUMX を返します。 これは再帰の基本的なケースです。

ニックネーム 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))

での実装 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;
}

出力：

Length of LCS is: 5

での実装 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)))

出力：

Length of LCS is:  5

最長共通部分列（LCS）の動的計画法

動的計画法とは、単純な再帰的手法を最適化することです。例えば、再帰的または単純なアプローチのグラフを見ると、複数の同一の関数呼び出しが存在することがわかります。動的計画法では、すべての計算結果を配列に記録し、必要に応じて再利用します。

m×nの次元を持つ2次元配列を使用します。ここで、mとnはパターン1とパターン2の長さです。 2D配列リストデータ構造は Python またはベクトル/配列データ構造 C++.

ニックネーム Code DPを使用したLCSの場合：

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]

以下に、動的計画法のアプローチにおける2次元配列データ構造として使用される表LCSを示します。

ここで使用したロジックについて説明します。手順は次のとおりです。

ステップ1） iまたはjがゼロの場合、与えられた2つの文字列から空の文字列を取り出し、共通の部分列を見つけようとします。しかし、取り出した部分文字列は空なので、部分列の長さは0になります。

ステップ2） 2 つの文字が一致する場合、前の行の (i-1,j-1) インデックスに存在する、以前に計算された LCS をインクリメントすることにより、(i,j) インデックスに値を割り当てます。

ステップ3） 一致しない場合は、隣接する2つのインデックスの最小共通部分列（LCS）の最大値を取得します。このようにして、2次元配列内のすべての値を埋める必要があります。

ステップ4） 最後に、2D 配列の最後のセルの値を返します。

基本的に、2次元配列のすべての値は共通部分列の長さを表しています。その中で、最後のセルには最長の共通部分列の長さが格納されています。

での実装 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;
}

出力：

Length of LCS: 5

での実装 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))

出力：

Length of LCS: 5

したがって、両方の文字列には長さ 5 の最長共通部分列があります。

要するに、DP法では各タスクを一度だけ計算します。再帰法では、重複が発生する可能性があります。ping 部分問題。

この動的プログラミング アルゴリズムでは、2D マトリックスを使用しています。 XNUMX つの文字列が指定されます (両方とも長さが n であると仮定します)。 この場合、配列に必要なスペースは nx n です。 文字列が十分に大きい場合は、メモリ最適化バージョンの DP ソリューションが必要になります。

コードに組み込まれた簡略化されたロジックは次のとおりです。

• 2D 配列 DP[m][n] を宣言します。
• DP 配列の最初の行と最初の列を 0 で埋めます。
• 反復のために i と j を考えます。
• pattern1[i]がpattern2[j]と等しい場合、DP[i][j] = DP[i-1][j-1] + 1に更新します。
• pattern1[i]がpattern2[j]と等しくない場合、DP[i][j]はDP[i-1][j]とDP[i][j-1]の間の最大値になります。
• i と j が m と n に達するまで続けます。
• 最後の要素である DP[m-1][n-1] には長さが含まれます。

ここでは、配列のインデックスが0から始まるため、DP[m-1][n-1]と表記されます。

よくあるご質問