algorithm
가장 긴 공통 서브 시퀀스
수색…
가장 긴 공통 서브 시퀀스 설명
동적 프로그래밍의 가장 중요한 구현 중 하나는 Longest Common Subsequence를 찾는 것입니다. 먼저 기본 용어 몇 가지를 정의 해 봅시다.
하위 시퀀스 :
서브 시퀀스는 나머지 요소의 순서를 변경하지 않고 일부 요소를 삭제하여 다른 시퀀스에서 파생 될 수있는 시퀀스입니다. ABC 라는 문자열이 있다고 가정 해 봅시다. 이 문자열에서 0 개 또는 하나 이상의 문자를 지우면이 문자열의 하위 문자열을 얻습니다. 따라서 문자열 ABC의 서브 시퀀스는 { "A" , "B" , "C" , "AB" , "AC" , "BC" , "ABC" , " }}가됩니다. 모든 문자를 제거하더라도 빈 문자열은 하위 시퀀스가됩니다. 문자열의 각 문자에 대해 하위 시퀀스를 찾으려면 두 가지 옵션이 있습니다. 하나는 문자를 사용하거나 그렇지 않습니다. 따라서 문자열의 길이가 n 인 경우 해당 문자열의 2 n 개의 하위 시퀀스가 있습니다.
가장 긴 공통 서브 시퀀스 :
이름에서 알 수 있듯이 두 문자열 사이의 모든 공통 부분 시퀀스 중에서 가장 긴 공통 부분 시퀀스 (LSC)는 최대 길이를 갖는 것입니다. 예 : "HELLOM" 과 "HMLD" 사이의 일반적인 하위 시퀀스는 "H" , "HL" , "HM" 등입니다. 여기에서 "HLL" 은 길이가 3 인 가장 긴 공통 하위 시퀀스입니다.
무차별 공격 방법 :
역 추적을 사용하여 두 문자열의 모든 하위 시퀀스를 생성 할 수 있습니다. 그런 다음이를 비교하여 공통 하위 시퀀스를 찾습니다. 최대 길이를 찾아야합니다. 우리는 이미 길이 n 의 문자열의 2 n 개의 서브 시퀀스가 있음을 보았습니다. 우리의 n이 20-25를 넘으면 문제를 푸는 데 수 년이 걸릴 것입니다.
동적 프로그래밍 방법 :
예제를 통해 우리의 방법에 접근 해 봅시다. 우리는 abcdaf 와 acbcf라는 두 개의 문자열을 가지고 있다고 가정합니다. 이것들을 s1 과 s2로 나타냅니다. 따라서이 두 문자열의 가장 긴 공통 하위 시퀀스는 길이가 4 인 "abcf"입니다 . 다시 말하지만 하위 시퀀스는 문자열에서 연속적 일 필요는 없습니다. "abcf"를 구축하기 위해, 우리는 S1과 S2에 "C"에서 "다"를 무시했다. 동적 프로그래밍을 사용하여이를 어떻게 찾을 수 있습니까?
s1의 모든 문자를 한 행에, s2의 모든 문자를 열로 갖는 테이블 (2D 배열)부터 시작하겠습니다. 여기에 테이블은 0으로 인덱싱되고 우리는 1에서부터 앞으로 문자를 넣습니다. 각 행에 대해 왼쪽에서 오른쪽으로 테이블을 탐색합니다. 우리의 테이블은 다음과 같습니다.
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
여기서 각 행과 열은 두 열 사이의 가장 긴 공통 부분 시퀀스의 길이를 나타내며 그 행과 열의 문자를 취하여 앞에있는 접두어에 추가합니다. 예를 들어 Table [2] [3] 은 "ac" 와 "abc" 사이에서 가장 긴 공통 부분 시퀀스의 길이를 나타냅니다.
0 번째 열은 s1 의 빈 서브 시퀀스를 나타냅니다. 마찬가지로 0 번째 행은 s2 의 빈 서브 시퀀스를 나타냅니다. 문자열의 빈 하위 시퀀스를 가져 와서 다른 문자열과 일치 시키려고하면 두 번째 하위 문자열의 길이가 아무리 길어도 공통 하위 시퀀스의 길이는 0입니다. 따라서 우리는 0 번째 행과 0 번째 열을 0으로 채울 수 있습니다. 우리는 얻는다 :
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
의 시작하자. 우리가 표 [1] [1]을 채울 때, 우리는 문자열 a 와 다른 문자열 a 가 있고 다른 것이 없다면, 여기서 가장 긴 공통 부분 시퀀스는 무엇이 될 것인가? 여기 LCS의 길이는 1이 될 것입니다. 이제 Table [1] [2]를 보겠습니다. 문자열 ab 와 문자열 a가 있습니다. LCS의 길이는 1이 될 것입니다. 알 수 있듯이 abcd , abcda , abcdaf 와 함께 문자열 a 만 고려하기 때문에 나머지 값도 첫 번째 행에 대해 1이됩니다. 그래서 우리 테이블은 다음과 같이 보일 것입니다 :
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 행에는 c 가 포함됩니다. 테이블 [2] [1]은 다른 쪽의 한쪽에 교류하고있다. 그래서 LCS의 길이는 1입니다. 우리는 어디에서 1을 얻었습니까? 맨 위에서 두 하위 문자열 사이의 LCS a 를 나타냅니다. 그래서 우리가 말하고있는 것은 s1 [2] 와 s2 [1] 가 같지 않다면 LCS의 길이는 맨 위나 왼쪽 에있는 LCS의 길이의 최대 값이 될 것입니다. 상단에있는 LCS의 길이를 취하는 것은 s2 에서 현재의 문자를 취하지 않음을 나타냅니다. 마찬가지로 LCS의 길이를 왼쪽으로하면 LCS를 만들기 위해 s1 에서 현재 문자를 취하지 않는다는 것을 나타냅니다. 우리는 얻는다 :
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
따라서 첫 번째 수식은 다음과 같습니다.
if s2[i] is not equal to s1[j]
Table[i][j] = max(Table[i-1][j], Table[i][j-1]
endif
Table [2] [2]에 대해 우리는 문자열 ab 와 ac를 가지고 있습니다. c 와 b 는 같지 않으므로 여기에 위쪽이나 왼쪽의 최대 값을 둡니다. 이 경우, 그것은 다시 1입니다. 그 후, 테이블 [2] [3]에 대해 우리는 문자열 abc 와 ac를가 집니다. 이번에는 행과 열 모두의 현재 값이 동일합니다. 이제 LCS의 길이는 지금까지의 LCS의 최대 길이와 같습니다. 지금까지 LCS의 최대 길이는 어떻게 얻습니까? 대각선 값을 확인합니다.이 값은 ab 와 a 가 가장 잘 일치 합니다 . 이 상태에서 현재 값에 대해 s1 과 s2에 한 문자 더 추가했습니다. 따라서 LCS의 길이는 물론 증가 할 것입니다. 표 [2] [3] 에 1 + 1 = 2 를 넣을 것입니다. 우리는,
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | 1 | 2 | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
따라서 두 번째 공식은 다음과 같습니다.
if s2[i] equals to s1[j]
Table[i][j] = Table[i-1][j-1] + 1
endif
우리는 두 경우를 모두 정의했습니다. 이 두 수식을 사용하여 전체 표를 채울 수 있습니다. 테이블을 채우면 다음과 같이 보입니다.
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | 1 | 2 | 2 | 2 | 2 |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | 1 | 2 | 2 | 2 | 2 | 2 |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | 1 | 2 | 3 | 3 | 3 | 3 |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | 1 | 2 | 3 | 3 | 3 | 4 |
+-----+-----+-----+-----+-----+-----+-----+-----+
s1 과 s2 사이의 LCS의 길이는 Table [5] [6] = 4 가 될 것이다. 여기서 5와 6은 각각 s2 와 s1 의 길이입니다. 우리의 의사 코드는 다음과 같습니다.
Procedure LCSlength(s1, s2):
Table[0][0] = 0
for i from 1 to s1.length
Table[0][i] = 0
endfor
for i from 1 to s2.length
Table[i][0] = 0
endfor
for i from 1 to s2.length
for j from 1 to s1.length
if s2[i] equals to s1[j]
Table[i][j] = Table[i-1][j-1] + 1
else
Table[i][j] = max(Table[i-1][j], Table[i][j-1])
endif
endfor
endfor
Return Table[s2.length][s1.length]
이 알고리즘의 시간 복잡도는 다음과 같습니다. O (mn) 여기서 m 및 n 은 각 문자열의 길이를 나타냅니다.
가장 긴 공통 부분 시퀀스를 어떻게 찾을 수 있습니까? 우린 오른쪽 하단부터 시작하겠습니다. 우리는 가치가 어디에서오고 있는지 확인합니다. 테이블 [i-1] [j-1] 이 Table [i] [j] - 1 과 같을 때 값이 대각선에서 오는 경우, 우리는 s2 [i] 또는 s1 [j] (둘 모두 똑같습니다) 대각선으로 이동하십시오. 값이 위로부터 오는 경우, 즉 Table [i-1] [j] 가 Table [i] [j] 와 같으면 맨 위로 이동합니다. 값이 왼쪽에서 오는 경우 즉, Table [i] [j-1] 이 Table [i] [j] 와 같으면 왼쪽으로 이동합니다. 맨 왼쪽 열 또는 맨 위 열에 도달하면 검색이 종료됩니다. 그런 다음 스택에서 값을 팝어 프린트합니다. 의사 코드 :
Procedure PrintLCS(LCSlength, s1, s2)
temp := LCSlength
S = stack()
i := s2.length
j := s1.length
while i is not equal to 0 and j is not equal to 0
if Table[i-1][j-1] == Table[i][j] - 1 and s1[j]==s2[i]
S.push(s1[j]) //or S.push(s2[i])
i := i - 1
j := j - 1
else if Table[i-1][j] == Table[i][j]
i := i-1
else
j := j-1
endif
endwhile
while S is not empty
print(S.pop)
endwhile
주의해야 할 점은 표 [i-1] [j] 와 표 [i] [j-1] 가 표 [i] [j] 및 표 [i-1] [j-1] Table [i] [j] - 1 과 같으면 그 순간에 두 개의 LCS가있을 수 있습니다. 이 의사 코드는이 상황을 고려하지 않습니다. 여러 LCS를 찾으려면이 문제를 재귀 적으로 풀어야합니다.
이 알고리즘의 시간 복잡도는 O (max (m, n)) 입니다.
