JavaScriptで最長の共通部分列を実装する方法

最長共通シーケンス (最長共通シーケンス) と最長共通部分文字列 (最長共通部分文字列) は同じものではありません。次の記事では、JavaScript での最長共通部分シーケンスの実装に関する関連情報を主に紹介します。それを参照できます。

はじめに

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

基本概念

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

共通部分列: シーケンス 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] の共通部分シーケンスには、空のシーケンス [] のみが存在します。

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

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

サブシーケンスは必ずしも連続しているわけではなく、連続したものであることがわかります。サブシーケンス。

問題分析

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

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

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

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

													C
											A		B
0

A

B

C

D

A

B

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

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

		"
	LCS問題はバックパック問題とは少し異なります、バックパック問題は問題ありません -1行と最長共通部分列を設定します空部分列が発生するため、左辺と上辺は最初から固定されています。
A は "X"、Y は "BDCA" の任意の部分列です

""000000A00001B0C0D0A0B000DA

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

0

BIf 2 つはすでに説明されています。次に、最初に B を見てみましょう。${X_1} == ${Y_0}、新しいパブリック部分文字列が得られるので、1 を追加する必要があります。なぜ？なぜなら、私たちのマトリックスは左から右、上から下への状態移行プロセスを記述する状態テーブルであり、これらの状態は既存の状態に基づいて蓄積されるからです。 ここで確認する必要があるのは、埋めたいグリッドの値と、その周囲にすでに埋められているグリッドの値との関係です。現状では情報が少なすぎて孤立点になっているだけです。 "" A 0000 1110D0A0B0

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

0

"" A 0000 111B011112C0D0A0B0この時点で、いくつかのルールを要約し、計算を通じてアイデアを検証し、新しいルールや制約を追加して改善します。 Y が大きい場合は、それと Y の B 部分列セットの方が大きくなります。たとえ大きくなくても、元の文字より小さくすることはできません。明らかに、新たに追加された C は戦闘力にはなり得ず、両者に共通のキャラクターではないため、値は AB の部分列セットに等しいはずです。 "" A 0000 111

B

0

1

1

11C0 1D0A0B0

そして、2 つの文字列間で比較される文字が異なる場合、塗りつぶされるグリッドは左辺または上辺に関連しており、大きい方の辺が使用されることは確実です。

比較される文字が同じ場合でも、心配する必要はありません。X の C は Y の C、つまり ABC {"",A,B,C, の部分シーケンス セットと比較する必要があることが起こります。 AB,BC,ABC} および BDC 部分列セット {"",B,D,C,BD,DC,BDC} を比較すると、得られる共通部分文字列は "",B,D です。この時点でも結論は前と同じで、文字が等しい場合、対応するグリッドの値は左隅、右隅、左上隅の値に等しく、左辺、上辺、左上辺は次のようになります。常に平等です。これらの謎を証明するには、より厳密な数学的知識が必要です。

A と B という 2 つの配列があるとします。 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) が最長ではないという矛盾した結果が推測できます。

2つ目は少し難しいです。 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 < m; i++){ 
   dp[i] = []
   for(var j = 0; j < n; j++){ 
    if(i === 0 || j === 0){
     dp[i][j] = 0
     continue
    }
    
    if(rows[i] === cols[j]){ 
     dp[i][j] = dp[i-1][j-1] + 1 //对角＋1
    }else{
     dp[i][j] = Math.max( dp[i-1][j], dp[i][j-1]) //对左边，上边取最大
    }
   }
   console.log(dp[i].join(""))//调试
  } 
  return dp[i-1][j-1]
 }

LCSは、位置を移動するだけでさらに簡素化でき、新しい配列を生成する必要がなくなります

//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 <= m; i++){ //一共有m+1行
  dp[i] = [0] //第一列全是0
  for(var j = 1; j <= n; j++){//一共有n+1列
   if(str1[i-1] === str2[j-1]){ 
    //注意这里，str1的第一个字符是在第二列中，因此要减1，str2同理
    dp[i][j] = dp[i-1][j-1] + 1 //对角＋1
   } else {
     dp[i][j] = Math.max( dp[i-1][j], dp[i][j-1]) 
   }
  }
 } 
 return dp[m][n];
}

LCSを印刷します

印刷機能を与えますので、やってみましょうまず、印刷する方法を見てください。右下隅から見て一番上の行で終わります。したがって、ターゲット文字列は逆の順序で構築されます。 stringBuffer などの面倒な中間量の使用を避けるために、プログラムが実行されるたびに 1 つの文字列のみが返され、それ以外の場合は printLCS(x,y,...) + を使用して空の文字列が返されます。 str[ i] は、必要な文字列を取得するために追加されます。

取得した文字列が実際の LCS 文字列かどうかを確認する別のメソッドを作成しましょう。すでに働いている人間として、学校の学生のようにコードを書いて、他の人がテストできるように単体テストを行わずにそれをオンラインに公開することはできません。

//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

Print all 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 <= m; i++){ //一共有2行
  row = dp[now] = [0] //第一列全是0
  for(var j = 1; j <= n; j++){//一共有n+1列
   if(str1[i-1] === str2[j-1]){ 
    //注意这里，str1的第一个字符是在第二列中，因此要减1，str2同理
    dp[now][j] = dp[i-now][j-1] + 1 //对角＋1
   } else {
    dp[now][j] = Math.max( dp[i-now][j], dp[now][j-1]) 
   }
  }
  now = 1- now; //1-1=>0;1-0=>1; 1-1=>0 ...
 } 
 return row ? row[n]: 0
}

危険な再帰的解決策

str1のサブシーケンスは添字シーケンス {1, 2 , ... に対応します。 .., m} の部分列 したがって、str1 には合計 ${2^m}$ 個の異なる部分列があり (${2^n}$ などの str2 にも同じことが当てはまります)、その複雑さは驚くべきものに達します。指数時間 (${2^m * 2^n}$)。

rreee

以上が皆さんのためにまとめたもので、今後皆さんのお役に立てれば幸いです。

関連記事:

vueを使ってセカンダリルート設定方法を実装

reactプロジェクト開発

Vue-Router2.Xで複数のルーティング実装を実装

2	2

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