最長共通部分列: 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 とも呼ばれます。

単純なソリューションでは、より長い時間がかかりますplex最適な解決策ではありません。 ダイナミック プログラミング ソリューション (DP) を使用して、com を克服します。plex問題。

素朴な方法

単純な方法は、時間に関係なく問題に対するシンプルなアプローチです。plex性やその他の最適化要素。

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

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

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

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

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

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

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

素朴な方法

1 文字のシーケンス:

素朴な方法

2 文字のシーケンス:

素朴な方法

3 文字のシーケンス:

素朴な方法

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

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

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

ということで、トータルタイムコムplexになる O(n*2m). 例として、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 を見つけます。 次に、部分文字列の LCS の長さの記録を保持します。

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

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

最適な下部構造

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

濃い色の中で box、サブ問題が重複していることに気づくことができます。 ("RG"、"RA")、("RG"、"R") などが複数回呼び出されます。

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

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

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

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

  • 最後の要素より前のすべての要素が一致する場合、長さを 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 の List データ構造または 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 です。

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 方式の方が時間は短くなります。plex性。 これは O(mn) です。ここで、m と n は入力文字列または配列の長さです。
  • DP は再帰的アプローチよりも高速なアプローチであり、plexの程度 O(n*2m).
  • ダイナミック プログラミング (DP) はメモリが最適化されていません。 m*n の長さの 2D 配列を使用しました。 ということで、スペースコムplexシティは (m*n) です。
  • 再帰的方法では、最悪の場合、占有するメモリの最大値は m+n (基本的には入力文字列の全長) になります。
  • 今日の最新のコンピューターは、この量のメモリを処理するのに十分です。