最長共通部分列問題
最長共通部分列(LCS)の問題は、指定された2つのシーケンスに同じ順序で存在する最長のサブシーケンスを見つけることです。つまり、いくつかの項目を削除することで最初の元のシーケンスから、削除することで2番目の元のシーケンスから取得できる最長のシーケンスを見つけることです。他の項目。
問題は、を見つける問題とは異なります 最長の一般的な部分文字列。部分文字列とは異なり、 サブシーケンス 元の文字列内で連続した位置を占める必要はありません。
たとえば、次の2つのシーケンスについて考えてみます。 X と Y:
Y: BDCABA
The length of the LCS is 4
LCS are BDAB, BCAB, and BCBA
素朴な解決策は、のすべてのサブシーケンスが X[1…m] それがのサブシーケンスでもあるかどうかを確認する Y[1…n]。あるので 2m 可能なサブシーケンス X、このソリューションの時間計算量は次のようになります O(n.2m)、 どこ m 最初の文字列の長さであり、 n 2番目の文字列の長さです。
LCS問題には 最適な下部構造。つまり、問題はより小さく単純な「サブ問題」に分解でき、それはさらに単純なサブ問題に分解できるなど、最終的に解決策が簡単になるまで続きます。
1.2つのシーケンスを考えてみましょう。 X と Y、長さ m と n 両方が同じ要素で終わること。
それらのLCSを見つけるには、最後の要素を削除して各シーケンスを短縮し、短縮されたシーケンスのLCSを見つけ、そのLCSが削除された要素を追加します。だから、私たちはそれを言うことができます。
2.2つのシーケンスが同じシンボルで終わっていないとします。
次に、のLCS X と Y 2つのシーケンスのうち長い方です LCS(X[1…m-1], Y[1…n]) と LCS(X[1…m], Y[1…n-1])。このプロパティを理解するために、次の2つのシーケンスを考えてみましょう。
Y: BDCABA (m elements)
これら2つのシーケンスのLCSは、次のいずれかで終了します。 B (シーケンスの最後の要素 X)またはしません。
B、それからそれはで終わることはできません A、削除できます A シーケンスから Y、および問題はに減少します LCS(X[1…m], Y[1…n-1]).
ケース2： LCSがで終わらない場合 B、その後削除できます B シーケンスから X そして問題はに減少します LCS(X[1…m-1], Y[1…n])。例えば、
LCS(ABCBDA, BDCABA) = LCS(ABCBD, BDCAB) + A
LCS(ABCBDAB, BDCAB) = LCS(ABCBDA, BDCA) + B
LCS(ABCBD, BDCAB) = maximum (LCS(ABCB, BDCAB), LCS(ABCBD, BDCA))
LCS(ABCBDA, BDCA) = LCS(ABCBD, BDC) + A
And so on…
C++、Java、およびPythonの次のソリューションは、シーケンスのLCSの長さを検出します X[0…m-1] と Y[0…n-1] LCS問題の最適部分構造特性を再帰的にに使用します。
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include <iostream> #include <string> using namespace std; //最長共通部分列の長さを見つける関数 //シーケンス`X[0…m-1]`と`Y[0…n-1]` int LCSLength(string X, string Y, int m, int n) { //いずれかのシーケンスの終わりに達した場合に戻ります if (m == 0 || n == 0) { return 0; } //`X`と`Y`の最後の文字が一致する場合 if (X[m - 1] == Y[n - 1]) { return LCSLength(X, Y, m - 1, n - 1) + 1; } //それ以外の場合、`X`と`Y`の最後の文字が一致しない場合 return max(LCSLength(X, Y, m, n - 1), LCSLength(X, Y, m - 1, n)); } int main() { string X = "ABCBDAB", Y = "BDCABA"; cout << "The length of the LCS is " << LCSLength(X, Y, X.length(), Y.length()); return 0; } |
出力:
The length of the LCS is 4
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
class Main { //最長共通部分列の長さを見つける関数 //シーケンス`X[0…m-1]`と`Y[0…n-1]` public static int LCSLength(String X, String Y, int m, int n) { //いずれかのシーケンスの終わりに達した場合に戻ります if (m == 0 || n == 0) { return 0; } //`X`と`Y`の最後の文字が一致する場合 if (X.charAt(m - 1) == Y.charAt(n - 1)) { return LCSLength(X, Y, m - 1, n - 1) + 1; } //それ以外の場合、`X`と`Y`の最後の文字が一致しない場合 return Integer.max(LCSLength(X, Y, m, n - 1), LCSLength(X, Y, m - 1, n)); } public static void main(String[] args) { String X = "ABCBDAB", Y = "BDCABA"; System.out.println("The length of the LCS is " + LCSLength(X, Y, X.length(), Y.length())); } } |
出力:
The length of the LCS is 4
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#の最長共通部分列の長さを見つける関数 #シーケンス`X[0…m-1]`および`Y[0…n-1]` def LCSLength(X, Y, m, n): #は、いずれかのシーケンスの終わりに達した場合に戻ります if m == 0 or n == 0: return 0 # `X`と`Y`の最後の文字が一致する場合は if X[m - 1] == Y[n - 1]: return LCSLength(X, Y, m - 1, n - 1) + 1 #それ以外の場合、`X`と`Y`の最後の文字が一致しない場合 return max(LCSLength(X, Y, m, n - 1), LCSLength(X, Y, m - 1, n)) if __name__ == '__main__': X = 'ABCBDAB' Y = 'BDCABA' print('The length of the LCS is', LCSLength(X, Y, len(X), len(Y))) |
出力:
The length of the LCS is 4
上記のソリューションの最悪の場合の時間計算量は O(2(m+n)) コールスタックのスペースを占有します。 m と n 文字列の長さです X と Y。最悪のケースは、に共通のサブシーケンスが存在しない場合に発生します X と Y (つまり、LCSは0です)、各再帰的呼び出しは2つの再帰的呼び出しになります。
LCS問題は 重複するサブ問題。問題の再帰的的アルゴリズムが新しいサブ問題を生成するのではなく、同じサブ問題を繰り返し解決する場合、問題には重複するサブ問題があると言われます。
LCSが0である長さ6と8の2つのシーケンスの再帰ツリーを考えてみましょう。
ご覧のとおり、同じサブ問題(同じ色で強調表示されている)が繰り返し計算されています。最適な部分構造と重複する部分問題を持つ問題は、動的プログラミングによって解決できることがわかっています。動的プログラミングでは、部分問題の解が繰り返し計算されるのではなく、メモ化されます。このメソッドは、C++、Java、およびPythonで以下に示されています。
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include <iostream> #include <string> #include <unordered_map> using namespace std; //部分文字列の最長共通部分列の長さを見つける関数 //`X[0…m-1]`と`Y[0…n-1]` int LCSLength(string X, string Y, int m, int n, auto &lookup) { //いずれかの文字列の終わりに達した場合に返します if (m == 0 || n == 0) { return 0; } //入力の動的要素から一意のマップキーを作成します string key = to_string(m) + "|" + to_string(n); //サブ問題が初めて発生した場合は、それを解決して //結果をマップに保存します if (lookup.find(key) == lookup.end()) { //`X`と`Y`の最後の文字が一致する場合 if (X[m - 1] == Y[n - 1]) { lookup[key] = LCSLength(X, Y, m - 1, n - 1, lookup) + 1; } else { //それ以外の場合、`X`と`Y`の最後の文字が一致しない場合 lookup[key] = max(LCSLength(X, Y, m, n - 1, lookup), LCSLength(X, Y, m - 1, n, lookup)); } } //マップからサブ問題の解決策を返します return lookup[key]; } int main() { string X = "ABCBDAB", Y = "BDCABA"; //サブ問題の解決策を保存するためのマップを作成します unordered_map<string, int> lookup; cout << "The length of the LCS is " << LCSLength(X, Y, X.length(), Y.length(), lookup); return 0; } |
出力:
The length of the LCS is 4
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
import java.util.HashMap; import java.util.Map; class Main { //部分文字列の最長共通部分列の長さを見つける関数 //`X[0…m-1]`と`Y[0…n-1]` public static int LCSLength(String X, String Y, int m, int n, Map<String, Integer> lookup) { //いずれかの文字列の終わりに達した場合に返します if (m == 0 || n == 0) { return 0; } //入力の動的要素から一意のマップキーを作成します String key = m + "|" + n; //サブ問題が初めて発生した場合は、それを解決して //結果をマップに保存します if (!lookup.containsKey(key)) { //`X`と`Y`の最後の文字が一致する場合 if (X.charAt(m - 1) == Y.charAt(n - 1)) { lookup.put(key, LCSLength(X, Y, m - 1, n - 1, lookup) + 1); } else { //それ以外の場合、`X`と`Y`の最後の文字が一致しない場合 lookup.put(key, Integer.max(LCSLength(X, Y, m, n-1, lookup), LCSLength(X, Y, m - 1, n, lookup))); } } //マップからサブ問題の解決策を返します return lookup.get(key); } public static void main(String[] args) { String X = "ABCBDAB", Y = "BDCABA"; //サブ問題の解決策を保存するためのマップを作成します Map<String, Integer> lookup = new HashMap<>(); System.out.println("The length of the LCS is " + LCSLength(X, Y, X.length(), Y.length(), lookup)); } } |
出力:
The length of the LCS is 4
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
#サブストリングの最長共通部分列の長さを見つける関数 #`X[0…m-1]`および`Y[0…n-1]` def LCSLength(X, Y, m, n, lookup): #は、いずれかの文字列の終わりに達した場合に戻ります if m == 0 or n == 0: return 0 #は、入力の動的要素から一意のキーを作成します key = (m, n) #サブ問題が初めて発生した場合は、それを解決して #はその結果を辞書に保存します if key not in lookup: # `X`と`Y`の最後の文字が一致する場合は if X[m - 1] == Y[n - 1]: lookup[key] = LCSLength(X, Y, m - 1, n - 1, lookup) + 1 else: #それ以外の場合、`X`と`Y`の最後の文字が一致しない場合 lookup[key] = max(LCSLength(X, Y, m, n - 1, lookup), LCSLength(X, Y, m - 1, n, lookup)) #は、辞書からサブ問題の解決策を返します return lookup[key] if __name__ == '__main__': X = 'ABCBDAB' Y = 'BDCABA' #は、サブ問題の解決策を保存するための辞書を作成します lookup = {} print('The length of the LCS is', LCSLength(X, Y, len(X), len(Y), lookup)) |
出力:
The length of the LCS is 4
上記のトップダウンソリューションの時間計算量は次のとおりです。 O(m.n) とが必要です O(m.n) 余分なスペース、ここで m と n 文字列の長さです X と Y。マップの代わりにアレイを使用することもできることに注意してください。実装を確認する ここ.
上記 メモ最初に問題をサブ問題に分割し、次に値を計算して保存するため、化されたバージョンはトップダウンアプローチに従います。この問題はボトムアップで解決することもできます。ボトムアップアプローチでは、の小さい方の値を計算します LCS(i, j) まず、それらからより大きな値を構築します。
LCS[i][j] = | LCS[i – 1][j – 1] + 1 if X[i-1] == Y[j-1]
| longest(LCS[i – 1][j], LCS[i][j – 1]) if X[i-1] != Y[j-1]
させて X なれ XMJYAUZ、 と Y なれ MZJAWXU。間の最長共通部分列 X と Y は MJAU。次の表は、関数によって生成されます LCSLength()、のプレフィックス間のLCSの長さを示します X と Y。 The i'th 行と j'th 列はLCSの部分文字列の長さを示します X[0…i-1] と Y[0…j-1].
これは、C++、Java、およびPythonで以下に示されています。
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
#include <iostream> #include <string> using namespace std; //部分文字列の最長共通部分列の長さを見つける関数 //`X[0…m-1]`と`Y[0…n-1]` int LCSLength(string X, string Y) { int m = X.length(), n = Y.length(); //ルックアップテーブルは、すでに計算されたサブ問題の解を格納します。 //つまり、 `lookup[i][j]`は部分文字列のLCSの長さを格納します //`X[0…i-1]`と`Y[0…j-1]` int lookup[m + 1][n + 1]; //ルックアップテーブルの最初の列はすべて0になります for (int i = 0; i <= m; i++) { lookup[i][0] = 0; } //ルックアップテーブルの最初の行はすべて0になります for (int j = 0; j <= n; j++) { lookup[0][j] = 0; } //ルックアップテーブルをボトムアップ方式で入力します for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { //`X`と`Y`の現在の文字が一致する場合 if (X[i - 1] == Y[j - 1]) { lookup[i][j] = lookup[i - 1][j - 1] + 1; } //それ以外の場合、`X`と`Y`の現在の文字が一致しない場合 else { lookup[i][j] = max(lookup[i - 1][j], lookup[i][j - 1]); } } } //LCSはルックアップテーブルの最後のエントリになります return lookup[m][n]; } int main() { string X = "XMJYAUZ", Y = "MZJAWXU"; cout << "The length of the LCS is " << LCSLength(X, Y); return 0; } |
出力:
The length of the LCS is 4
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
class Main { //部分文字列の最長共通部分列の長さを見つける関数 //`X[0…m-1]`と`Y[0…n-1]` public static int LCSLength(String X, String Y) { int m = X.length(), n = Y.length(); //ルックアップテーブルは、すでに計算されたサブ問題の解を格納します。 //つまり、 `T[i][j]`は部分文字列のLCSの長さを格納します //`X[0…i-1]`と`Y[0…j-1]` int[][] T = new int[m + 1][n + 1]; //ルックアップテーブルをボトムアップ方式で入力します for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { //`X`と`Y`の現在の文字が一致する場合 if (X.charAt(i - 1) == Y.charAt(j - 1)) { T[i][j] = T[i - 1][j - 1] + 1; } //それ以外の場合、`X`と`Y`の現在の文字が一致しない場合 else { T[i][j] = Integer.max(T[i - 1][j], T[i][j - 1]); } } } //LCSはルックアップテーブルの最後のエントリになります return T[m][n]; } public static void main(String[] args) { String X = "XMJYAUZ", Y = "MZJAWXU"; System.out.println("The length of the LCS is " + LCSLength(X, Y)); } } |
出力:
The length of the LCS is 4
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
#サブストリングの最長共通部分列の長さを見つける関数 #`X[0…m-1]`および`Y[0…n-1]` def LCSLength(X, Y): m = len(X) n = len(Y) #ルックアップテーブルは、すでに計算されたサブ問題の解決策を格納します。 #、つまり、 `T[i][j]`は部分文字列のLCSの長さを格納します #`X[0…i-1]`および`Y[0…j-1]` T = [[0 for x in range(n + 1)] for y in range(m + 1)] #はボトムアップ方式でルックアップテーブルを埋めます for i in range(1, m + 1): for j in range(1, n + 1): # `X`と`Y`の現在の文字が一致する場合は if X[i - 1] == Y[j - 1]: T[i][j] = T[i - 1][j - 1] + 1 #それ以外の場合、`X`と`Y`の現在の文字が一致しない場合 else: T[i][j] = max(T[i - 1][j], T[i][j - 1]) # LCSは、ルックアップテーブルの最後のエントリになります return T[m][n] if __name__ == '__main__': X = 'XMJYAUZ' Y = 'MZJAWXU' print('The length of the LCS is', LCSLength(X, Y)) |
出力:
The length of the LCS is 4
上記のボトムアップソリューションの時間計算量は次のとおりです。 O(m.n) とが必要です O(m.n) 余分なスペース、ここで m と n 文字列の長さです X と Y。上記のソリューションのスペースの複雑さは、次のように改善できます。 O(n) LCSテーブルの行のLCSを計算するには、現在の行と前の行の解のみが必要です。
LCS問題の応用
最長共通部分列問題は、次のようなデータ比較プログラムの基礎を形成します diffユーティリティ バイオインフォマティクスの分野での使用。また、Gitなどのリビジョン管理システムでも広く使用されています。
こちらも参照:
参照： https://en.wikipedia.org/wiki/Longest_common_subsequence_problem