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

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

Longest Common Subsequence (LCS) とは、オブジェクトの XNUMX つの文字列/パターン/シーケンスが与えられることを意味します。これら XNUMX つのシーケンス/文字列のうち、両方の文字列またはパターンに存在する同じ順序で要素の最も長いサブシーケンスを見つける必要があります。

例

たとえば、XNUMX つの文字列が提供されています。

次のように仮定しましょう。

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

pattern_1からは「RGB」「RGGA」「RGAR」といったシーケンスを生成できます。シーケンスを作成するには、文字列内の各文字の相対位置を維持する必要があります。
pattern_2 からは、「BGR」、「BRAG」、「RARG」のようなシーケンスを生成できます。シーケンスは、元の文字列の相対位置を維持している限り生成できます。

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

たとえば、元の文字列 pattern_2 では「B」が最初に出現し、次に「R」、次に「G」が出現するため、「BRG」は有効なシーケンスです。ただし、シーケンスが「RBRG」の場合は無効です。元の文字列 (pattern_2) では「B」が最初に来るためです。

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

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

単純なソリューションは時間の複雑さが増し、最適なソリューションではありません。動的プログラミングソリューション (DP) を使用すると、複雑さの問題を克服できます。

素朴な方法

ナイーブな方法は、時間の複雑さやその他の最適化要因に関係なく、問題に対する単純なアプローチです。

Naive メソッドは、ほとんどの場合、「ブルートフォース」、複数のループ、再帰的メソッドで構成されます。

ブルートフォースという用語は、特定の問題に対して考えられるすべてのパターンを検討することを意味します。

例

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

ここでは単純な 4 文字の文字列「ABCD」を示します。たとえば、「ABCD」からシーケンスを作成する必要があります。キャラクターを採用できるかどうかのどちらかです。つまり、キャラクターごとに XNUMX つの選択肢があるということです。

彼らは以下のとおりです。

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

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

1 文字のシーケンス:

2 文字のシーケンス:

3 文字のシーケンス:

上の図から、14 個のシーケンスがあります。文字を使用しない場合、基本的には空の文字列で、シーケンスの合計は 15 になります。さらに、文字列「ABCD」自体もシーケンスです。したがって、合計シーケンスは 16 になります。

したがって、2を生成することが可能です⁴ または「ABCD」からの 16 個のサブシーケンス。次に、長さの文字列 m 2 の部分列を合計する必要があります^m.

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

したがって、総時間計算量は O(n*2^m). 例として、m=8 および n=5 の値を上で見てきました。

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

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

最適な下部構造

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

ステップ1） 各パターンから最初の XNUMX 文字を取得します

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

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

サブ文字列 (元の文字列から生成された文字列) で LCS を見つけます。次に、部分文字列の LCS の長さの記録を保持します。

さて、ここにもう XNUMX つの興味深いプロパティがあります。 重複する副次的な問題。問題ステートメントが小さなサブ問題に分割され、プログラム内で複数回使用される場合、問題には重複したサブ問題があると言われます。

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

たとえば、再帰ツリーを見てみましょう。

暗い色のボックスでは、重複したサブ問題に気付くでしょう。 (“RG”、“RA”)、 (“RG”、“R”) などが複数回呼び出されています。

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

最長通信シーケンスの再帰的方法

上に示したグラフは再帰的手法です。各再帰関数には、再帰を中断するか、スタックからの戻りを開始するための基本ケースがあります。

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

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

疑似コード:

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)

での実装 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("Lenght of LCS is: ", lcs(pattern_1, pattern_2, len(pattern_1), len(pattern_2)))

出力：

Lenght of LCS is:  5

最長共通部分列 (LCS) の動的計画法

動的プログラミングとは、単純な再帰的手法を最適化することを意味します。たとえば、再帰的または単純なアプローチのグラフを見ると、同じ関数呼び出しがいくつかあることがわかります。動的プログラミング手法は、すべての計算を配列に記録し、必要に応じてそれを使用します。

mxn の次元を持つ 2D 配列を使用します。ここで、m と n は pattern1 と pattern2 の長さです。

2D配列Pythonのリストデータ構造やベクトル/配列データ構造を使用することができます。 C++.

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]

これは、動的プログラミングアプローチの 2D 配列データ構造として使用されるテーブル LCS です。

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

ステップ1） i または j が 0 の場合、指定された XNUMX つの文字列から空の文字列を取り出し、共通の部分列を見つけようとします。ただし、取得している部分文字列が空であるため、部分列の長さは XNUMX です。

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

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

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

基本的に、2D 配列内のすべての値には、共通のサブシーケンスの長さが含まれます。このうち、最後のセルには最長の共通部分列の長さが含まれます。

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

出力：

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 法では各タスクを XNUMX 回ずつ計算しているだけです。再帰的手法では、重複する部分問題が発生する可能性があります。

この動的プログラミングアルゴリズムでは、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] には長さが含まれます。

ここでは、配列インデックスが 1 から始まるため、DP[m-1][n-0] としてアドレス指定されます。

まとめ

DP メソッドの時間計算量はより少なく、O(mn) です。ここで、m と n は入力文字列または配列の長さです。
DPは再帰的アプローチよりも高速であり、時間計算量は O(n*2^m).
動的プログラミング (DP) はメモリ最適化されていません。長さが m*n の 2D 配列を使用しました。したがって、空間計算量は (m*n) です。
再帰的方法では、最悪の場合、占有するメモリの最大値は m+n (基本的には入力文字列の全長) になります。
今日の最新のコンピューターは、この量のメモリを処理するのに十分です。

よろしければ：

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

例

素朴な方法

例

最適な下部構造

関連記事

最長通信シーケンスの再帰的方法

での実装 C++

Pythonでの実装

最長共通部分列 (LCS) の動的計画法

での実装 C++

での実装 Python

まとめ