자바스크립트에서 가장 긴 공통 하위 시퀀스를 구현하는 방법

가장 긴 공통 부분 문자열(longest common substring)과 가장 긴 공통 부분 문자열(longest common substring)은 같은 것이 아닙니다. 다음 글은 JavaScript에서 가장 긴 공통 부분 순서의 구현에 대한 관련 정보를 주로 소개합니다. 참고할 수 있습니다.

소개

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

기본 개념

하위 시퀀스: 특정 시퀀스의 하위 시퀀스는 주어진 시퀀스에서 0개 이상의 요소를 제거한 결과입니다(요소 간의 상대적 순서를 변경하지 않고). 예를 들어, 시퀀스 23195a5eab8013c21303d3d24e81fe27의 하위 시퀀스는 4e2154b1242725e74a11c55ea3967ed3, 2cf3a2d5a55d4ffa7aceebabd439c436, 99080602b5459d7a05dfb3b86d5155dc잠깐만요.

공통 부분 수열: 수열 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개 또는 여러 문자를 삭제하여 형성된 새로운 시리즈입니다. 차이점은 하위 시퀀스의 문자가 중간에서 잘려질 수 있다는 것입니다. cnblogs 문자열에는 몇 개의 하위 시퀀스가 ​​있습니까? 확실히 cb, cgs 등 27개가 하위 시퀀스입니다.

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

하위 시퀀스가 ​​반드시 연속적인 것은 아니며, 연속적인 것은 문자열이라는 것을 알 수 있습니다.

Problem Analysis

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

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

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

CFake X="ABCDAB", Y="BDCABA", 각각은 가장 짧은 시퀀스를 꺼냅니다. 즉, 빈 문자열과 빈 문자열을 비교합니다. LCS 방정식의 해는 숫자이기 때문에 이 표는 숫자로만 채워질 수 있습니다. 두 개의 빈 문자열의 공통 영역의 길이는 0.A BCDA B

	D		A		B
""											0

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

000LCS 문제는 Backpack 문제와 조금 다르며, Backpack 문제는 괜찮습니다. -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을 입력합니다. 의 두 번째 B까지 입력합니다. 네, 둘 다 1입니다. BDCAB의 경우 또 다른 공통 하위 시퀀스인 AB가 있기 때문입니다. ㅋㅋㅋ

11B0이 시점에서는 몇 가지 규칙을 요약한 다음 계산을 통해 아이디어를 검증하고 이를 개선하기 위한 새로운 규칙이나 제약 조건을 추가할 수 있습니다. 11B0111 122 1

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

비교된 문자가 동일한 경우 걱정하지 마세요. 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
  }
 }

위 내용은 모두를 위해 제가 정리한 내용입니다. 앞으로 모든 사람에게 도움이 되기를 바랍니다.

관련 기사:

vue를 사용하여 보조 경로 설정 방법 구현

react 프로젝트 개발

Vue-Router2.X에서 다중 라우팅 구현 구현

				ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ	C	0		D	0		A	0
				Y는 모든 문자를 위로 보냅니다. 더 크면 Y의 B 하위 시퀀스 집합이 더 커집니다. 비록 크지 않더라도 원본보다 작을 수는 없습니다. 분명히 새로 추가된 C는 전투력이 될 수 없고 둘 사이의 공통 문자가 아니므로 그 값은 AB의 하위 시퀀스 집합과 동일해야 합니다. ㅋㅋㅋ
												C	0
		D	0		A	0					B	0

위 내용은 자바스크립트에서 가장 긴 공통 하위 시퀀스를 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!