JSでパブリックサブシーケンスを作成する方法

php中世界最好的语言
リリース: 2018-03-23 13:40:50
オリジナル
1562 人が閲覧しました

今回はJSでパブリックサブシーケンスを作成する方法を紹介します。JSでパブリックサブシーケンスを実装する際の注意点を実際に見てみましょう。

はじめに

最長共通部分配列 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 文字または数文字を削除することによって形成される新しいシリーズ。違いは、サブシーケンスでは途中から切り取られた文字を含めることができることです。この stringcnblog には中性子シーケンスがいくつありますか?明らかに、それらは 27 個あります。たとえば、cb、cgs などはすべてそのサブシーケンスです

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

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

問題分析

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

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

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

""AB D
C
A B

仮定しますLCS 方程式の解は数値であるため、この表には数値のみを入力できます。 2 つの空の文字列の共通領域の長さは 0.

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

0 LCS 問題はバックパック問題とは少し異なり、ナップザック問題は -1 行に設定することもでき、最長共通部分列は左空の部分列が発生するため、上辺は最初から固定されています。 次に、問題をもう少し拡大します。今回は、両方が同じである場合にのみ、空の文字列ではない共通の部分列が存在し、長さも 1 として理解できます。 。 A は "X"、Y は "BDCA" の任意の部分列ですDB00
A 0 B 0 C 0 D
A 0 B 0 x "" B
C A
A
"" 0
0 0
0

0

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

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

A 0 0 0 0 1 B
C 0 D 0 A 0 B 0
"" A 0000 1 110D0A0B0011
次に、Y にヘルパーとして追加の D を与えます。 {"",A,B,AB} vs {"",B,D,BD}、当然ながら、1 を埋め続けます。Y の 2 番目の B までは、すべて 1 です。 BDCAB に関しては、別の共通のサブシーケンス AB があるからです。 "" A 0 0 0
1 1 1
B 0
1 1
2

この時点で、いくつかのルールを要約し、計算を通じてアイデアを検証し、新しいルールや制約を追加して改善します。 01C0 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}$)。

//警告,字符串的长度一大就会爆栈
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
  }
 }
ログイン後にコピー

この記事の事例を読んだ後は、この方法を習得したと思います。さらに興味深い情報については、php 中国語 Web サイトの他の関連記事に注目してください。

推奨読書:

datepicker の使用方法

NavigatorIOSコンポーネントの使い方の詳しい説明

Vue.jsでのejsExcelテンプレートの使い方

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

以上がJSでパブリックサブシーケンスを作成する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

関連ラベル:
ソース:php.cn
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
最新の問題
人気のチュートリアル
詳細>
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート