LCS (Longest Common Subsequence)

 

LCS란 Longest Common Subsequence의 줄임말로 최장 공통 부분수열을 뜻합니다.

최장 공통 부분수열은 공통 부분 문자열 중 가장 길이가 긴 문자열을 말합니다. 앞으로 알아볼 LCS 알고리즘은 LCS에 부합하는 문자열을 찾기 위한 알고리즘입니다.

 

LCS는 최장 공통 부분수열만이 아니라 최장 공통 문자열(Longest Common Substring)을 말하기도 하는데, 두 알고리즘의 차이점을 알아보겠습니다.

 

아래 그림으로 알아보자면

출처 -  [알고리즘] 그림으로 알아보는 LCS 알고리즘

 

ABCDEF 와 GBCDFE 두 문자열을 비교해보겠습니다.

왼쪽의 최장 공통 부분수열은 BCDF, BCDE 두 개의 결과를 얻을 수 있고, 오른쪽의 최장 공통 문자열은 BCD의 결과만 얻었습니다.

최장 공통 부분수열은 부분수열이기 때문에 문자와 문자를 건너뛰어가며 공통된 문자열을 찾습니다.

최장 공통 문자열은 부분문자열을 찾는 것이 아니기 때문에 연속된 문자열만 인정합니다.

정리하자면 이렇게 차이점을 정리할 수 있습니다.

 

차이점

• Substring : 전체 문자열에서 연속된 부분 문자열
• Subsequence : 전체 문자열에서 연속된 문자열이 아니어도 공통된 순서인 부분 문자열

 

---

 

LCS - Substring 구현

LCS 알고리즘은 다이나믹 프로그래밍 방식으로 구현됩니다.

 

먼저 최장 공통 문자열을 구하는 알고리즘부터 살펴봅시다. 최장 공통 부분수열을 구하는 알고리즘과 공통적인 부분이 있기 때문에 먼저 보겠습니다!

 

부분 코드

if i == 0 or j == 0:    # 맨 앞 0번째 인덱스는 0으로 비워둡니다.
    LCS[i][j] = 0
elif string_A[i] == string_[j]:    # 비교할 두 문자열의 각 i번째, j번째 값이 같으면
    LCS[i][j] = LCS[i-1][j-1] + 1
else:
    LCS[i][j] = 0

코드 출처 - [알고리즘] 그림으로 알아보는 LCS 알고리즘

 

LCS 2차원 배열을 통해 문자열을 비교하고 값을 저장합니다.

1. 문자열을 한 글자씩 비교한다.
2. 두 문자가 다르다면 LCS[i][ j]에 0을 저장한다.
3. 두 문자가 같다면 LCS[i-1][ j-1]의 값에 1을 더해 저장한다.

이 3단계 과정을 반복합니다.

 

최장 공통 문자열은 공통된 문자열이 연속되어야 하기 때문에 앞 글자의 공통 여부에 따라 공통 문자열을 이어갈지, 본인부터 새로 문자열을 만들어갈지 판단하게 됩니다.

 

행과 열의 0번째 인덱스를 비워주는 이유는 편의적인 부분도 있지만, 

맨 앞 글자끼리 같은 값일 경우에 [i-1][ j-1]에 접근해야 하는데 0 인덱스부터 문자열이 시작하면 음수 인덱스로 배열을 참조하게 되어 오류가 발생하기 때문입니다.

 

문자열 ABCDEFG와 BDEFHGI를 예시로 비교해보겠습니다.

 

첫 번째 열과 행은 0으로 초기화 하겠습니다.

	0	A	B	C	D	E	F	G
0	0	0	0	0	0	0	0	0

 

이제 ABCDEFG와 두 번째 문자열의 첫 번째 글자 B를 비교합니다.

 

(1)  A와 B를 비교

A != B 이기 때문에 0을 넣어줍니다.

	0	A	B	C	D	E	F	G
0	0	0	0	0	0	0	0	0
B	0	0

 

(2) B와 B를 비교

첫 번째 문자열의 [AB]와 두 번째 문자열의 [B]를 비교해줍니다.

동일한 문자열이므로 해당 자리에 1을 넣어줍니다.

이때 왼쪽 대각선의 값에 1을 더한 값임을 알아야합니다.

코드로 작성하면 LCS[i][ j ] = LCS[i-1][ j-1] + 1 입니다.

	0	A	B	C	D	E	F	G
0	0	0	0	0	0	0	0	0
B	0	0	1

 

(3) 이후 나머지 문자열과 B를 비교

남은 CDEFG는 B와 같은 값이 없으므로 모두 0을 입력합니다.

	0	A	B	C	D	E	F	G
0	0	0	0	0	0	0	0	0
B	0	0	1	0	0	0	0	0

 

이런 식으로 표를 끝까지 작성하면 

(4) ABCDEFG와 D를 비교

	0	A	B	C	D	E	F	G
0	0	0	0	0	0	0	0	0
B	0	0	1	0	0	0	0	0
D	0	0	0	0	1	0	0	0

 

(5) ABCDEFG와 E를 비교

여기서 같은 문자를 발견했을 때,

LCS[i][ j ]는 LCS[i-1][ j-1]의 값에 더해주기 때문에 1이 아닌 2를 입력해줍니다.

	0	A	B	C	D	E	F	G
0	0	0	0	0	0	0	0	0
B	0	0	1	0	0	0	0	0
D	0	0	0	0	1	0	0	0
E	0	0	0	0	0	2	0	0

 

(6) ABCDEFG와 F를 비교

(5)와 같은 과정으로 3을 입력합니다.

	0	A	B	C	D	E	F	G
0	0	0	0	0	0	0	0	0
B	0	0	1	0	0	0	0	0
D	0	0	0	0	1	0	0	0
E	0	0	0	0	0	2	0	0
F	0	0	0	0	0	0	3	0

 

(7) ABCDEFG와 H

	0	A	B	C	D	E	F	G
0	0	0	0	0	0	0	0	0
B	0	0	1	0	0	0	0	0
D	0	0	0	0	1	0	0	0
E	0	0	0	0	0	2	0	0
F	0	0	0	0	0	0	3	0
H	0	0	0	0	0	0	0	0

 

(8) ABCDEFG와 G

	0	A	B	C	D	E	F	G
0	0	0	0	0	0	0	0	0
B	0	0	1	0	0	0	0	0
D	0	0	0	0	1	0	0	0
E	0	0	0	0	0	2	0	0
F	0	0	0	0	0	0	3	0
H	0	0	0	0	0	0	0	0
G	0	0	0	0	0	0	0	1

 

(9) ABCDEFG와 I 

두 문자열을 모두 비교한 최종 결과입니다.

	0	A	B	C	D	E	F	G
0	0	0	0	0	0	0	0	0
B	0	0	1	0	0	0	0	0
D	0	0	0	0	1	0	0	0
E	0	0	0	0	0	2	0	0
F	0	0	0	0	0	0	3	0
H	0	0	0	0	0	0	0	0
G	0	0	0	0	0	0	0	1
I	0	0	0	0	0	0	0	0

 

최장 공통 문자열은 {DEF}이며, 위 배열에서 가장 Max 값을 찾으면 공통 문자열의 가장 긴 길이입니다.

 

---

LCS - Subsequence 구현

이번엔 최장 공통 부분수열의 탐색 과정과 구현에 대해 알아보겠습니다.

 

부분 코드

if i == 0 or j == 0:    # 맨 앞을 0으로 비워줌
    LCS[i][j] = 0
elif string_A[i] == string_B[j]:
    LCS[i][j] = LCS[i-1][j-1] + 1
else:
    LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1]) # ! substring 구현 방법과 달라진 점 !

코드 출처 - [알고리즘] 그림으로 알아보는 LCS 알고리즘

 

마찬가지로 LCS 2차원 배열을 사용합니다.

1. 두 문자열을 한 글자씩 비교합니다.
2. 두 문자가 다르다면 LCS[i-1][ j ]와 LCS[i][ j-1] 중에 큰 값을 표시합니다.
3. 두 문자가 같다면 LCS[i-1][j-1]의 값에 1을 더해 입력합니다.

앞선 최장 공통 문자열을 구하는 방법과 다른 점은 2번째 과정입니다.

공통 문자열을 구할 때는 서로 다른 값이라면 그냥 0을 입력했습니다. 공통 부분수열을 구하는 경우에는 다른 값이라면 배열의 왼쪽이나 위쪽 중 큰 값을 입력합니다.

 

 

왜 과정이 달라지는가?

 

1. 다른 값이 나왔을 경우

 먼저, 공통 부분수열은 같은 문자가 연속할 필요가 없습니다.

 그래서 현재의 인덱스가 서로 다른 값이어도 이전의 최장 공통 부분수열은 유지됩니다.

 이전의 최장 공통 부분수열 -> 왼쪽과 위쪽의 값인 겁니다.

 

 아래 이미지로 예시를 들어보겠습니다.

출처 -  [알고리즘] 그림으로 알아보는 LCS 알고리즘

 

 위 그림의 초록색 부분을 보면 AB와 GBC를 비교한 결과인데요.

 AB와 C는 값이 겹치지 않지만, AB와 GB를 비교했을 때의 1이라는 값을 AB, GBC 비교에도 계속 가지고 갑니다. 그렇기 때문에 AB와 GB의 최장 공통 부분수열이 B이며, AB와 GBC의 최장 공통 부분수열도 B가 된다.

 

2. 같은 값이 나왔을 경우

 최장 공통 문자열에서 봤던 것처럼 이전의 최장 공통 부분수열에 1을 더한 값을 입력합니다.

 위 그림에 (3, 3)에서 2로 값이 늘어 입력된 것을 확인하시면 됩니다.

 (3, 3)에서 ABC와 GBC가 같은 값이 나왔기 때문에 AB와 GB의 공통 부분수열에 1을 더해줬습니다.

 

이제 표와 함께 과정을 살펴보겠습니다.

ABCDEFG와 BDEFHGI를 비교해보겠습니다.

 

(1) ABCDEFG와 B를 비교  ->  {B}

AB에서 B와 같은 값을 찾아 그 이후로는 지금까지의 최장 공통 부분수열 길이를 유지합니다.

	0	A	B	C	D	E	F	G
0	0	0	0	0	0	0	0	0
B	0	0	1	1	1	1	1	1

 

(2) ABCDEFG와 BD를 비교  ->  {BD}

여기서 A와 BD를 비교한 후, AB와 BD를 비교했기 때문에 AB와 B의 공통 부분수열의 길이를 가져옵니다.

	0	A	B	C	D	E	F	G
0	0	0	0	0	0	0	0	0
B	0	0	1	1	1	1	1	1
D	0	0	1

 

이 후, ABCD와 BD를 비교하는 순간, 공통 부분수열이 {B}에서 {BD}로 늘어납니다.

	0	A	B	C	D	E	F	G
0	0	0	0	0	0	0	0	0
B	0	0	1	1	1	1	1	1
D	0	0	1	1	2	2	2	2

 

(3) ABCDEFG와 BDE를 비교  ->  {BDE}

ABCD와 BDE를 비교할 때까지는 최장 길이가 2이다가, ABCDE와 BDE를 비교하는 순간 공통 부분수열이 {BDE}로 3의 길이가 됩니다.

	0	A	B	C	D	E	F	G
0	0	0	0	0	0	0	0	0
B	0	0	1	1	1	1	1	1
D	0	0	1	1	2	2	2	2
E	0	0	1	1	2	3	3	3

 

(4) ABCDEFG와 BDEF를 비교  ->  {BDEF}

(1)~(3)과 같은 방법으로 공통 부분수열을 늘려줍니다.

ABCDEF에서 BDEF와의 공통 부분수열이 늘어납니다.

	0	A	B	C	D	E	F	G
0	0	0	0	0	0	0	0	0
B	0	0	1	1	1	1	1	1
D	0	0	1	1	2	2	2	2
E	0	0	1	1	2	3	3	3
F	0	0	1	1	2	3	4	4

 

(5) ABCDEFG와 BDEFH를 비교  ->  {BDEF}

이번에는 ABCDEFG와 H가 같은 값을 갖는 부분이 없기 때문에 이전의 공통 부분수열을 유지합니다.

	0	A	B	C	D	E	F	G
0	0	0	0	0	0	0	0	0
B	0	0	1	1	1	1	1	1
D	0	0	1	1	2	2	2	2
E	0	0	1	1	2	3	3	3
F	0	0	1	1	2	3	4	4
H	0	0	1	1	2	3	4	4

 

(6) ABCDEFG와 BDEFHG를 비교  ->  {BDEFG}

ABCDEFG를 BDEFHG까지 비교했을 때 같은 값을 찾을 수 있습니다. 공통 부분수열이 {BDEFG}로 늘어납니다.

	0	A	B	C	D	E	F	G
0	0	0	0	0	0	0	0	0
B	0	0	1	1	1	1	1	1
D	0	0	1	1	2	2	2	2
E	0	0	1	1	2	3	3	3
F	0	0	1	1	2	3	4	4
H	0	0	1	1	2	3	4	4
G	0	0	1	1	2	3	4	5

 

(7) ABCDEFG와 BDEFHGI를 비교  ->  {BDEFG}

I는 ABCDEFG와 같은 값을 찾을 수 없기 때문에 이전의 최장 공통 부분수열을 유지합니다.

	0	A	B	C	D	E	F	G
0	0	0	0	0	0	0	0	0
B	0	0	1	1	1	1	1	1
D	0	0	1	1	2	2	2	2
E	0	0	1	1	2	3	3	3
F	0	0	1	1	2	3	4	4
H	0	0	1	1	2	3	4	4
G	0	0	1	1	2	3	4	5
I	0	0	1	1	2	3	4	5

 

---

 

아래는 최장 공통 부분수열을 구해서 문자열로 결과를 받는 방법입니다!

 

1. LCS 배열의 가장 마지막 값에서 시작합니다. NxM 크기의 배열이라면 LCS[N-1][M-1]의 값이 되겠죠.
2. 결과를 저장할 result 배열을 준비하고, 위쪽 LCS[i-1][ j ]와 왼쪽 LCS[i][ j-1] 중 현재 값과 같은 값을 찾습니다.
   2-1) 같은 값이 있다면 해당 값으로 이동합니다
   2-2) 같은 값이 없다면 result 배열에 현재 값을 넣고 LCS[i-1][ j-1]로 이동합니다.
3. 2번을 반복하다가 0인덱스로 이동하게 되면 탐색을 종료합니다. result 배열을 역순으로 출력하면 최장 공통 부분수열을 출력할 수 있습니다.
   
   

배열 하나로 간단하게 과정을 확인하면

	0	A	B	C	D	E	F	G
0	0	0	0	0	0	0	0	0
B	0	0	1	1	1	1	1	1
D	0	0	1	1	2	2	2	2
E	0	0	1	1	2	3	3	3
F	0	0	1	1	2	3	4	4
H	0	0	1	1	2	3	4	4
G	0	0	1	1	2	3	4	5
I	0	0	1	1	2	3	4	5

 

표의 노란 부분은 출력하지 않은 경로이며, 파란색은 result 배열에 넣어준 문자의 위치입니다.

result = [ G, F, E, D, B] 

위 결과 배열을 거꾸로 접근하면 BDEFG로 최장 공통 부분수열을 구할 수 있습니다.

최장 공통 부분수열은 탐색하는 문자열과 탐색하는 첫 방향에 따라서 서로 다른 결과가 나올 수도 있으니 이점은 유의하시길 바랍니다!

 

제가 만든 문자열과 다른 문자열 예시를 보고 싶으시다면 아래 남긴 출처의 블로그에서 확인하시면 좋을 것 같습니다!

 

---

출처

 

[알고리즘] 그림으로 알아보는 LCS 알고리즘

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence

알고리즘 - LCS(Longest Common Subsequence, 최장 공통 부분 문자열) 알고리즘

알고리즘 - LCS(Longest Common Subsequence, 최장 공통 부분 문자열) 알고리즘

문자열 알고리즘 (4) - 최장 공통부분 문자열 (Longest Common String)

문자열 알고리즘 (4) - 최장 공통부분 문자열 (Longest Common String)