JS에서 공개 하위 시퀀스를 만드는 방법

php中世界最好的语言
풀어 주다: 2018-03-23 13:40:50
원래의
1562명이 탐색했습니다.

이번에는 JS에서 public subsequence를 만드는 방법을 보여드리겠습니다. JS에서 public subsequence를 구현하기 위한 notes가 무엇인지 살펴보겠습니다.

소개

가장 긴 공통 부분 시퀀스 LCS는 주어진 두 시퀀스 X와 Y에서 가능한 한 많은 문자를 가져와 원래 시퀀스에 배열된 순서대로 배열하여 얻습니다. LCS 문제에 대한 알고리즘은 다양한 용도로 사용됩니다. 예를 들어, 다양한 버전의 소프트웨어를 관리할 때 LCS 알고리즘은 소프트웨어 테스트에서 이전 버전과 새 버전 간의 유사점과 차이점을 찾는 데 사용됩니다. 기록된 서열과 재생된 서열을 비교하는 데 사용되며, 유전 공학 분야에서는 LCS 알고리즘이 사용됩니다. 이 알고리즘은 표절 방지 시스템에서 환자의 DNA 가닥과 본드의 DNA 가닥 사이의 유사점과 차이점을 확인합니다. 논문의 표절률을 확인하는데 사용됩니다. LCS 알고리즘은 프로그램 코드 유사성 측정, 인간의 실행 시퀀스 검색, 비디오 세그먼트 매칭 등에 사용될 수 있으므로 LCS 알고리즘에 대한 연구는 응용 가치가 높습니다.

기본 개념

하위 시퀀스(subsequence): 특정 시퀀스의 하위 시퀀스는 주어진 시퀀스에서 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 수열이 주어지면 모든 공통 부분 수열 중에서 길이가 가장 긴 하나 또는 여러 개를 선택하세요.
하위 문자열: 시퀀스의 앞, 마지막 또는 둘 다에서 0개 또는 여러 문자를 삭제하여 형성된 새로운 시리즈입니다. 차이점은 하위 시퀀스의 문자가 중간에서 잘려질 수 있다는 것입니다. 이 stringcn블로그에는 중성자 시퀀스가 ​​몇 개 있나요? 분명히 27개가 있습니다. 예를 들어, cb, cgs 등은 모두 하위 시퀀스입니다.

설명할 그림을 보여주세요.

하위 시퀀스가 ​​반드시 연속적인 것은 아니며 연속적인 시퀀스는 다음과 같습니다. 하위 시퀀스.

Problem Analysis

우리는 여전히 행렬에서 분석을 시작하고 상태 전이 방정식을 직접 도출합니다.

먼저 문제를 프론트 엔드에 충분히 친숙한 개념으로 변환합니다. 순차적으로 호출하는 대신 배열이나 문자열로 생각하면 됩니다. 일을 단순하게 유지하기 위해 두 문자열이 비교되고 있다고 가정해 보겠습니다.

여러 개, 0개 또는 모두를 삭제할 수 있는 "하위 시퀀스" 개념에 중점을 둡니다. 현재 첫 번째 하위 시퀀스는 빈 문자열입니다(시퀀스가 문자열이 아닌 경우에도 여전히 가능합니다)! 정말 주목하셔야 할 부분이에요! 많은 사람들이 "알고리즘 입문"의 차트를 이해하지 못하고, 이해하는 척하지 않는 블로거들도 많습니다. 우리는 항상 왼쪽에서 오른쪽으로 비교하며, 물론 첫 번째 문자열은 행렬의 높이이므로 수직으로 배치됩니다. ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

C
D A

가정 LCS 방정식의 해는 숫자이기 때문에 이 표는 숫자로만 채워질 수 있습니다. 두 개의 빈 문자열의 공통 영역의 길이는 0.

C B 그런 다음 X를 움직이지 않고 계속해서 빈 문자열이 나타나도록 하고 Y에서는 "B"가 나타나도록 합니다. 분명히 공통 영역의 길이는 0입니다. Y는 다른 문자인 D, C, 또는 DC와 DDC의 연속 조합으로 대체되며 상황은 변경되지 않았으며 여전히 0입니다. 따라서 첫 번째 행은 0입니다. Y를 이동하지 않고 Y는 빈 문자열만 생성합니다. 그러면 위의 분석과 동일하며 둘 다 0이고 첫 번째 열은 모두 0입니다.""D AA
"" 0 A B
D A
x
B
C
B

000 LCS 문제는 배낭 문제와 조금 다르며, 배낭 문제도 -1 행으로 설정할 수 있으며, 가장 긴 공통 부분 수열은 왼쪽에 있습니다. 빈 하위 시퀀스가 ​​발생하기 때문에 위쪽이 처음부터 고정됩니다. 그러면 문제를 더 확대해 보겠습니다. 이번에는 양쪽이 모두 동일한 경우에만 빈 문자열이 아닌 공통 부분 수열이 있을 수 있으며 길이도 1로 이해될 수 있습니다. A는 "X"이고 Y는 "BDCA"BA
"" 0 0 0 0 0 0 0
A 0 B 0 C 0 D
A
B
x ""
D C
B

A

A00001B0 C0D0A0B0D0A 0 B0

만약 그런 다음 먼저 B(${X_1} == ${Y_0})를 살펴보고 새로운 공개 하위 문자열을 얻으며 1을 추가해야 합니다. 왜? 우리 매트릭스는 상태 테이블이기 때문에 왼쪽에서 오른쪽, 위에서 아래로 상태 마이그레이션 과정을 설명하고 이러한 상태는 기존 상태를 기반으로 누적됩니다. 이제 확인해야 할 것은 우리가 채우려는 그리드의 값과 이미 채워져 있는 그 주변의 그리드 값 사이의 관계입니다. 현재는 정보가 너무 적어서 고립된 지점일 뿐입니다. 1개만 채워주세요. ㅋㅋㅋ

1
"" 0 0 0 0 0 0
계속해서 오른쪽 빈칸을 채워가는데, 빈칸은 어떻게 채워야하나요? 분명히 LCS는 X의 길이보다 클 수 없습니다. 어떻게 A 문자열에서 시작하는 Y의 하위 시퀀스가 ​​B의 A 시퀀스와 비교하여 1과 같을 수 있습니까? ㅋㅋㅋ
1그런 다음 Y에게 도우미로 D를 추가로 제공하고 {"",A,B,AB} 대 {"",B,D,BD}, 분명히 계속해서 1을 채웁니다. Y의 두 번째 B까지는 모두 1입니다. BDCAB의 경우 또 다른 공통 하위 시퀀스인 AB가 있기 때문입니다. ㅋㅋㅋ 0이 시점에서는 몇 가지 규칙을 요약한 다음 계산을 통해 아이디어를 검증하고 이를 개선하기 위한 새로운 규칙이나 제약 조건을 추가할 수 있습니다. 11B0111 1220
ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 1 1 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ C
D 0 A 0 B 0 Y는 모든 문자를 보냅니다. 이 경우 Y의 B 하위 시퀀스 집합은 더 커집니다. 비록 크지 않더라도 원본보다 작을 수는 없습니다. 분명히 새로 추가된 C는 전투력이 될 수 없고 둘 사이의 공통 문자가 아니므로 그 값은 AB의 하위 시퀀스 집합과 동일해야 합니다. ㅋㅋㅋ
C
1
D 0
A 0
B

0

그리고 두 문자열 사이에서 비교할 문자가 다른 경우 채워질 그리드는 왼쪽 또는 위쪽에 관련되며 더 큰 쪽이 사용된다는 것을 확신할 수 있습니다.

비교된 문자가 동일한 경우 걱정하지 마세요. 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)이 가장 길지 않다는 모순된 결과를 추론할 수 있습니다.

두 번째는 좀 까다롭습니다. 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와 같은 번거로운 중간 수량의 사용을 피하기 위해 프로그램이 실행될 때마다 하나의 문자열만 반환하고 그렇지 않으면 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
로그인 후 복사

모든 LCS 인쇄

아이디어는 위와 유사합니다. LCS 방법에는 Math.max 값이 있습니다. 이는 실제로 세 가지 상황을 통합합니다. 그래서 세 개의 문자열을 분기할 수 있습니다. 우리의 메소드는 자동 제거를 위해 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 중국어 웹사이트의 다른 관련 기사를 주목하세요!

추천 도서:

datepicker 사용 방법

NavigatorIOS 컴포넌트 사용에 대한 자세한 설명

Vue.js에서 ejsExcel 템플릿 사용

위 내용은 JS에서 공개 하위 시퀀스를 만드는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

관련 라벨:
원천:php.cn
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
인기 튜토리얼
더>
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿