[자료구조 및 알고리즘] Dynamic Programming (3)

근사 문자열 매칭과 거리 함수

 

근사 문자열 매칭 (approximate string matching) 은 비슷한 문자열을 매칭하는 것을 말합니다.

 

거리 함수는 어떤 문자열과 문자열 사이의 거리를 구하는 함수로 다음 3가지의 예가 있습니다.

• 해밍거리
• 편집거리
• 가중 편집거리

 

편집 거리

 

한 문자열을 다른 문자열로 변경하기 위해 필요한 편집연산들의 최소 수

 

연산의 종류는 [삽입, 삭제, 교체, 유지]가 있습니다.

 

DP Idea

 

D(i,j)는 두 문자열 S1, S2에 대한 편집거리를 나타낸다고 할때, 제일 오른쪽 문자부터 비교를 하면서 연산들 중 값이 가장 작아지는 것을 고르면 됩니다.

 

D(i,j)값은 아래 4가지 값들 중 가장 작은 값입니다:

• D(i,j-1) + 1 → 삽입
• D(i-1,j) + 1 → 삭제
• D(i-1,j-1) + diff(i,j) → 같으면 diff값 0, 다르면 diff값 1

 

최장 공통 부분 서열, LCS (Longest Common Subsequence)

 

부분 서열은 주어진 서열에서 일부 문자를 삭제한 후 남은 문자들을 순서대로 연결하여 만들어지는 서열을 의미합니다. LSC는 X와 Y가 주어질 때 X와 Y의 공통 부분 서열 중 가장 긴 것을 의미합니다. X의 길이가 m, Y의 길이가 n일때 X와 Y의 LCS의 길이를 구하는 문제입니다.

 

DP Idea

 

LCS(i,j)를 Xi, Yi의 LCS의 길이라고 하면, 구해야하는 값은 LCS(m,n)입니다. 기본적인 아이디어는 위의 편집거리와 매우 유사합니다.

 

• LCS(i,j) = 0 → i = 0 이거나 j = 0인 경우
• LCS(i,j) = LCS(i-1, j-1) + 1 → Xi, Yi가 같으면 LCS의 길이가 1 추가됩니다
• LCS(i,j) = max{LCS(i-1,j) , LCS(i,j-1)} → Xi, Yi가 다르면 삽입 또는 삭제 연산을 통해 다음 문자를 보면 됩니다

 

Global Alignment

 

두 개의 문자열을 '-'을 포함하도록 확장하여 같은 길이의 문자열로 만드는데 대응되는 문자들의 쌍들의 score 합이 최대가 되는 alignment를 구하는 문제입니다.

 

가중 편집거리를 구하는 것으로 볼 수도 있습니다.

 

DP Idea

 

σ(x,y)를 문자 x와 문자 y에 대한 유사도라고 할때,

유사도는 x=y일때 점수가 가장 크고, x≠y일때 빈칸이 적을수록 점수가 더 많습니다. σ(-,-)는 0이하의 점수입니다.

이번에도 편집거리와 유사한 방식으로 두 Sequence A, B의 유사도를 가장 크게 만드는 Global Alignment를 구해볼 수 있습니다. V(i,j)는 Ai, Bj사이의 유사도이고, 최종 정답은 V(m,n)입니다.

 

기저 조건은 다음과 같습니다:

• V(0,0) = 0
• V(i,0) = V(i-1,0) + σ(Ai, -)
• V(0,j) = V(0,j-1) + σ(-, Bj)

 

V(i,j)는 아래 세 가지 값들 중 최대값입니다:

• V(i-1,j-1) + σ(Ai,Bj)
• V(i-1,j) + σ(Ai,-)
• V(i,j-1) + σ(-,Bj)