수색…


가장 긴 공통 서브 시퀀스 설명

동적 프로그래밍의 가장 중요한 구현 중 하나는 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를 넘으면 문제를 푸는 데 수 년이 걸릴 것입니다.

동적 프로그래밍 방법 :

예제를 통해 우리의 방법에 접근 해 봅시다. 우리는 abcdafacbcf라는 두 개의 문자열을 가지고 있다고 가정합니다. 이것들을 s1s2로 나타냅니다. 따라서이 두 문자열의 가장 긴 공통 하위 시퀀스는 길이가 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]에 대해 우리는 문자열 abac를 가지고 있습니다. cb 는 같지 않으므로 여기에 위쪽이나 왼쪽의 최대 값을 둡니다. 이 경우, 그것은 다시 1입니다. 그 후, 테이블 [2] [3]에 대해 우리는 문자열 abcac를가 집니다. 이번에는 행과 열 모두의 현재 값이 동일합니다. 이제 LCS의 길이는 지금까지의 LCS의 최대 길이와 같습니다. 지금까지 LCS의 최대 길이는 어떻게 얻습니까? 대각선 값을 확인합니다.이 값은 aba 가 가장 잘 일치 합니다 . 이 상태에서 현재 값에 대해 s1s2에 한 문자 더 추가했습니다. 따라서 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  |
     +-----+-----+-----+-----+-----+-----+-----+-----+

s1s2 사이의 LCS의 길이는 Table [5] [6] = 4 가 될 것이다. 여기서 5와 6은 각각 s2s1 의 길이입니다. 우리의 의사 코드는 다음과 같습니다.

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) 여기서 mn 은 각 문자열의 길이를 나타냅니다.

가장 긴 공통 부분 시퀀스를 어떻게 찾을 수 있습니까? 우린 오른쪽 하단부터 시작하겠습니다. 우리는 가치가 어디에서오고 있는지 확인합니다. 테이블 [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)) 입니다.



Modified text is an extract of the original Stack Overflow Documentation
아래 라이선스 CC BY-SA 3.0
와 제휴하지 않음 Stack Overflow