JavaScript の最長共通部分列の詳細な説明

最長の共通部分列は、指定された 2 つのシーケンス X と Y からできるだけ多くの文字を取り出し、それらを元のシーケンスで配置されている順序で配置することによって取得されます。 LCS 問題のアルゴリズムには幅広い用途があります。たとえば、ソフトウェアの異なるバージョンの管理では、LCS アルゴリズムはソフトウェアのテストで古いバージョンと新しいバージョンの間の類似点と相違点を見つけるために使用されます。記録された配列と再生された配列を比較するために使用されます。遺伝子工学の分野では、LCS アルゴリズムが使用されます。このアルゴリズムは、盗作防止システムで患者の DNA 鎖と結合の DNA 鎖の類似点と相違点をチェックします。論文の盗作率をチェックするために使用されます。 LCS アルゴリズムは、プログラム コードの類似性測定、人間の走行シーケンスの検索、ビデオ セグメントのマッチングなどにも使用できるため、LCS アルゴリズムの研究は高い応用価値があります。

基本概念

1. サブシーケンス: 特定のシーケンスのサブシーケンスは、指定されたシーケンスから (要素間の相対的な順序を変更せずに) 0 個以上の要素を削除した結果です。たとえば、シーケンス のサブシーケンスは、、、お待ちください。

2. 共通部分列: シーケンス X と Y が与えられた場合、シーケンス Z は X の部分列と Y の部分列であり、Z は X と Y の共通部分列になります。たとえば、X=[A,B,C,B,D,A,B]、Y=[B,D,C,A,B,A[の場合、シーケンス Z=[B,C,A] は次のようになります。 X と Y の共通部分列で、長さは 3 です。しかし、Z は X と Y の最長共通部分列ではなく、シーケンス [B, C, B, A] と [B, D, A, B] も X と Y の最長共通部分列であり、長さは4 、X と Y には 5 以上の長さの共通のサブシーケンスがありません。シーケンス [A、B、C] とシーケンス [E、F、G] の共通部分シーケンスには、空のシーケンス [] のみが存在します。

3. 最長共通部分列: シーケンス X と Y が与えられた場合、すべての共通部分列から最長の長さを持つ 1 つまたは複数を選択します。

4. 部分文字列: 先頭、最後、または両方から 0 文字または複数の文字を同時に削除することによって形成される新しいシリーズ。違いは、サブシーケンスでは途中から切り取られた文字を含めることができることです。文字列 cnblogs にはサブシーケンスがいくつありますか?明らかに 27 個あり、cb、cgs などはすべてそのサブシーケンスです

説明するために画像を与えてください:

サブシーケンスが必ずしも連続しているわけではない、または連続していることがわかります。部分文字列。

問題分析

やはり行列から分析を開始し、状態遷移方程式を自分たちで導き出します。

まず、問題を順番に呼び出すのではなく、配列または文字列として考えることができる、フロントエンドにとって十分馴染みのある概念に変換します。話を簡単にするために、2 つの文字列が比較されていると仮定します。

私たちは、複数またはゼロ、あるいはすべてを削除できる「サブシーケンス」の概念に焦点を当てています。現時点では、最初のサブシーケンスは 空の文字列 です (シーケンスが文字列でない場合でも、文字列にすることができます)。これは本当に注意が必要なことです！ 『アルゴリズム入門』のチャートを理解できない人も多いし、分かったふりをしないブロガーも多い。常に左から右に比較します。もちろん、最初の文字列は行列の高さであるため、垂直に配置されます。

"" CABABCDA

									A	B			D
												false order X = "ABCDAB"、Y = "BDCABA"、それぞれが最短のシーケンスを取り出します。つまり、空の文字列と空の文字列を比較します。 LCS 方程式の解は数値であるため、この表には数値のみを入力できます。 2 つの空の文字列の共通領域の長さは 0 です。

B

次に、X を移動せずに空の文字列を配列から取り出し続け、Y で「B」を配列から取り出します。明らかに、それらの共通領域の長さは 0 です。Y は他の文字に置き換えられます。 、D、C、またはそれらの連続性 DC と DDC を組み合わせても、状況は変わらず、0 のままです。したがって、最初の行はすべて 0 になります。その場合、Y は移動せず、Y は空の文字列のみを生成します。は上記の分析と同じで、両方とも 0 で、最初の列はすべて 0 です。

000000B 0C0D0AB次に、問題をもう少し拡大します。今回は、両方が同じである場合にのみ、空の文字列ではない共通の部分列が存在し、長さも 1 として理解できます。 。 x""BDCABA

												A	0
								0		0		LCS この問題はナップサック問題とは少し異なります。ナップザック問題は -1 行に設定することもでき、空の部分列が存在するため、最長の共通部分列の左辺と上辺が最初から固定されます。	A は "X"、Y は "BDCA" の任意の部分列です

""

0

0000 000001引き続き右側の空白を埋めてください。空白を埋めるにはどうすればよいですか?明らかに、LCS は X の長さを超えることはできません。B の A シーケンスと比較して、A 文字列から始まる Y の部分シーケンスが 1 に等しくなるのはなぜでしょうか。 ""0000A 0000111

												A	0
								B	1
										0	0	0

BC If That が "" である場合、4 つの組み合わせ "A"、"B"、および "AB" のうちの最初の 2 つはすでに説明されています。次に、最初に B を見てみましょう。${X_1} == ${Y_0}、新しいパブリック部分文字列が得られるので、1 を追加する必要があります。なぜ？なぜなら、私たちの行列は状態テーブルであり、状態の移行プロセスを左から右、上から下に記述しており、これらの状態は既存の状態 ""0000 0A 00001B01C0D0A0

								0		に基づいて蓄積されるからです。 ここで確認する必要があるのは、埋めたいグリッドの値と、その周囲にすでに埋められているグリッドの値との関係です。現状では情報が少なすぎて孤立点になっているので、1だけ埋めておきます。
								0	0
								1	1

B0

次に、Y にヘルパーとして追加の D を与えます。{"",A,B,AB} 対 {"",B,D,BD} 明らかに、1 を入力し続けます。次の B まで入力します。 Y 、両方とも 1 です。 BDCAB に関しては、別の共通のサブシーケンス AB があるからです。

""00A 001B01C0D 000Y が大きい場合は、それと Y の B 部分列セットの方が大きくなります。たとえ大きくなくても、元の文字より小さくすることはできません。明らかに、新たに追加された C は戦闘力にはなり得ず、両者に共通のキャラクターではないため、値は AB の部分列セットに等しいはずです。

								0	0	0	0	0
								0	0	1	1
								1	1	1	2
											A		B
	このステップでは、いくつかのルールを要約することができます。その後、計算を通じてアイデアを検証し、新しいルールを追加します。それらを改善するために条件を制限します。

""

0

0

00 001B11CD0A0

0	0	0									A	0	0
1	1										0	1	1
2	2										0	1
					B	0		そして、2 つの文字列間で比較される文字が異なる場合、塗りつぶされるグリッドは左辺または上辺に関連しており、大きい方の辺が使用されることは確実です。 比較される文字が同じ場合でも、心配する必要はありません。X の C は Y の C、つまり ABC {"",A,B,C, の部分シーケンス セットと比較する必要があることが起こります。 AB,BC,ABC} および BDC 部分列セット {"",B,D,C,BD,DC,BDC} を比較すると、得られる共通部分文字列は "",B,D です。この時点でも結論は前と同じで、文字が等しい場合、対応するグリッドの値は左隅、右隅、左上隅の値に等しく、左辺、上辺、左上辺は次のようになります。常に平等です。これらの謎を証明するには、より厳密な数学的知識が必要です。 假设有两个数组，A和B。A[i]为A的第i个元素，A(i)为由A的第一个元素到第i个元素所组成的前缀。m(i, j)为A(i)和B(j)的最长公共子序列长度。 由于算法本身的递推性质，其实只要证明，对于某个i和j：   m(i, j) = m(i-1, j-1) + 1 （当A[i] = B[j]时）   m(i, j) = max( m(i-1, j), m(i, j-1) ) （当A[i] != B[j]时） 第一个式子很好证明，即当A[i] = B[j]时。可以用反证，假设m(i, j) > m(i-1, j-1) + 1 （m(i, j)不可能小于m(i-1, j-1) + 1，原因很明显），那么可以推出m(i-1, j-1)不是最长的这一矛盾结果。 第二个有些trick。当A[i] != B[j]时，还是反证，假设m(i, j) > max( m(i-1, j), m(i, j-1) )。 由反证假设，可得m(i, j) > m(i-1, j)。这个可以推出A[i]一定在m(i, j)对应的LCS序列中（反证可得）。而由于A[i] != B[j]，故B[j]一定不在m(i, j)对应的LCS序列中。所以可推出m(i, j) = m(i, j-1)。这就推出了与反正假设矛盾的结果。 得证。 次に、以下の方程式を使用して表への入力を続けます。 プログラムの実装 //by 司徒正美 function LCS(str1, str2){         var rows =  str1.split("")         rows.unshift("")         var cols =  str2.split("")         cols.unshift("")         var m = rows.length          var n = cols.length          var dp = []         for(var i = 0; i <p></p><p>LCSは、位置を移動するだけでさらに簡素化でき、新しい配列を生成する必要がなくなります</p><pre class="brush:php;toolbar:false">//by司徒正美 function LCS(str1, str2){     var m = str1.length      var n = str2.length     var dp = [new Array(n+1).fill(0)] //第一行全是0     for(var i = 1; i <p></p><h2 id="LCSを印刷します">LCSを印刷します</h2><p>印刷機能を与えますので、やってみましょうまず、印刷する方法を見てください。右下隅から見て一番上の行で終わります。したがって、ターゲット文字列は逆の順序で構築されます。 stringBuffer などの面倒な中間量の使用を避けるために、プログラムが実行されるたびに 1 つの文字列のみが返され、それ以外の場合は printLCS(x,y,...) + を使用して空の文字列が返されます。 str[ i] は、必要な文字列を取得するために追加されます。 </p><p>取得した文字列が実際の LCS 文字列であるかどうかを確認する別のメソッドを作成しましょう。すでに働いている人間として、学校の学生のようにコードを書いて、他の人がテストできるように単体テストを行わずにそれをオンラインに公開することはできません。 </p><pre class="brush:php;toolbar:false">//by 司徒正美，打印一个LCS function printLCS(dp, str1, str2, i, j){     if (i == 0 || j == 0){         return "";     }     if( str1[i-1] == str2[j-1] ){         return printLCS(dp, str1, str2, i-1, j-1) + str1[i-1];     }else{         if (dp[i][j-1] > dp[i-1][j]){             return printLCS(dp, str1, str2, i, j-1);         }else{             return printLCS(dp, str1, str2, i-1, j);         }     } } //by司徒正美， 将目标字符串转换成正则，验证是否为之前两个字符串的LCS function validateLCS(el, str1, str2){    var re =  new RegExp( el.split("").join(".*") )    console.log(el, re.test(str1),re.test(str2))    return re.test(str1) && re.test(str2) } 使用: function LCS(str1, str2){     var m = str1.length      var n = str2.length     //....略，自行补充     var s = printLCS(dp, str1, str2, m, n)     validateLCS(s, str1, str2)     return dp[m][n] } var c1 = LCS( "ABCBDAB","BDCABA"); console.log(c1) //4 BCBA、BCAB、BDAB var c2 = LCS("13456778" , "357486782" ); console.log(c2) //5 34678  var c3 = LCS("ACCGGTCGAGTGCGCGGAAGCCGGCCGAA" ,"GTCGTTCGGAATGCCGTTGCTCTGTAAA" ); console.log(c3) //20 GTCGTCGGAAGCCGGCCGAA すべての LCS を出力する この考え方は、LCS メソッドに Math.max 値があることに注意してください。これは、実際には 3 つの状況を統合します。したがって、3本の弦をフォークすることができます。このメソッドは、自動削除のために es6 コレクション オブジェクトを返します。その後、毎回新しいセットを使用して古いセットの文字列がマージされます。 //by 司徒正美 打印所有LCS function printAllLCS(dp, str1, str2, i, j){     if (i == 0 || j == 0){         return new Set([""])     }else if(str1[i-1] == str2[j-1]){         var newSet = new Set()         printAllLCS(dp, str1, str2, i-1, j-1).forEach(function(el){             newSet.add(el + str1[i-1])         })         return newSet     }else{         var set = new Set()         if (dp[i][j-1] >= dp[i-1][j]){             printAllLCS(dp, str1, str2, i, j-1).forEach(function(el){               set.add(el)             })         }         if (dp[i-1][j] >= dp[i][j-1]){//必须用>=，不能简单一个else搞定             printAllLCS(dp, str1, str2, i-1, j).forEach(function(el){               set.add(el)             })         }            return set     }   } 使用: function LCS(str1, str2){     var m = str1.length      var n = str2.length     //....略，自行补充     var s =  printAllLCS(dp, str1, str2, m, n)     console.log(s)     s.forEach(function(el){         validateLCS(el,str1, str2)         console.log("输出LCS",el)     })     return dp[m][n] } var c1 = LCS( "ABCBDAB","BDCABA"); console.log(c1) //4 BCBA、BCAB、BDAB var c2 = LCS("13456778" , "357486782" ); console.log(c2) //5 34678  var c3 = LCS("ACCGGTCGAGTGCGCGGAAGCCGGCCGAA" ,"GTCGTTCGGAATGCCGTTGCTCTGTAAA" ); console.log(c3) //20 GTCGTCGGAAGCCGGCCGAA 空間最適化 ローリング配列を使用: function LCS(str1, str2){     var m = str1.length      var n = str2.length     var dp = [new Array(n+1).fill(0)],now = 1，row //第一行全是0     for(var i = 1; i 0;1-0=>1; 1-1=>0 ...     }      return row ? row[n]: 0 } 危険な再帰的解決策 str1の部分列は添字シーケンスに対応します{1、2、…、aしたがって、str1 には合計 ${2^m}$ 個の異なる部分列があり (${2^n}$ などの str2 にも同じことが当てはまります)、そのため複雑度は驚くべき指数関数的時間 ($) に達します。 { 2^m * 2^n}$)。 //警告，字符串的长度一大就会爆栈 function LCS(str1, str2, a, b) {       if(a === void 0){           a = str1.length - 1       }       if(b === void 0){           b = str2.length - 1       }       if(a == -1 || b == -1){           return 0       }        if(str1[a] == str2[b]) {          return LCS(str1, str2,  a-1, b-1)+1;       }       if(str1[a] != str2[b]) {          var x =  LCS(str1, str2, a, b-1)          var y =  LCS(str1, str2, a-1, b)          return x >= y ? x : y       }   } 関連する推奨事項: Python 言語で最大連続部分列和を説明する 最大連続部分列和問題 最大部分列和のための PHP アルゴリズムの実装_PHP チュートリアル

以上がJavaScript の最長共通部分列の詳細な説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。