[Dynamic Programming] 근사 문자열 매칭과 거리 함수 & LCS

근사 문자열 매칭 (approximate string matching)

• 비슷한 문자열 비교
• 주어진 문자열과 비슷한 문자열을 검색 ex) 검색 엔진 유사어 추천 등..

비슷한 것이라는 것은 무엇인가?

이때 사용하는 것이 거리함수이다.

 

거리 함수

• 해밍거리 (Hamming distance) : 단순 문자열 매칭으로 다른 자리의 갯수 - 글자가 끼어들거나 빠지거나 할 수 없는 경우 사용할 수 있음 
• 편집거리 (edit distance) : 첫번째 문자열을 두번째 문자열로 바꾸는데 얼마나 많은 editing 작업을 해야하는가? 
• 가중편집거리 (weighted edit distance) 

 

편집 거리

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

 

편집 연산

• 삽입 (Insertion)
• 삭제 (Deletion)
• 교체 (Substitution or Replacement)

 

DP를 이용한 편집 거리 계산

두 문자열 S1과 S2에 대해, D(i,j)는 S1[1...i]과 S2[1...j]에 대한 편집거리를 나타냄

• S1, S2의 길이가 각각 n, m일 때, S1과 S2의 편집거리는 D(n,m)
• D(n,m)을 계산하기 위해 각 i와 j에 대해 D(i,j)를 계산함

 

DP 요소

• Recurrence relation
• Tabular computation
• Traceback

 

Recurrence Relation

match, change, insert, delete를 어떻게 조합하는지에 따라서 다양한 편집거리가 나올 수 있다

제일 좋은 operation 이 있을 것이다.

 

위에서부터 insert, delete, match/change이다.

 

마지막이 insert인 경우

insert하는 것을 제외하고 생각하면, i와 j-1까지의 편집거리를 알아야한다.

insert는 비용이 있기 때문에 +1 한다.

 

마지막이 delete인 경우

위에 delete하는 것을 제외하고 i-1과 j까지의 편집 거리를 알아야한다.

delete는 비용이 있기 때문에 +1 한다.

 

마지막 식은 마지막을 제외한 부분만 해서 비교한다.

t(i,j)가 같으면 0이고, 다르면 이전 부분에서 +1 해서 change를 의미한다.

 

Tabular Computation

배열 형태로 보면, 위 왼쪽 대각선 세 방향에서 오는 것이라는 것을 할 수 있다.

대각선으로 오면 같으면 0, 다르면 +1이고 위나 왼쪽에서는 무조건 +1이다

 

Traceback

 

최장 공통 부분 서열 (LCS)

두 개의 DNA 순서열 (sequence)이 있을 때, 이 두개가 얼마나 유사한지를 측정하는 일이 자주 발생한다. 

edit distance와 매우 비슷한 문제이다

-> match의 개수가 가장 많은 것이 LCS이다.

 

LCS 최적화 재귀식

DP로 해결하기 위해서

 

모든 i에 대해 x의 prefix를 Xi = (x1, x2, .... xi), Yi = (y1, y2, ... yi)로 정의한다. 

Z = (z1, ... zk)를 X, Y의 LCS라고 하자

 

If Xm = Yn, then zk = xm = yn and \(Z_{k-1}\) is an LCS of \(X_{m-1} \)and \(Y_{n-1}\)

마지막이 같으면 LCS에 마지막 글자를 붙인다

If Xm != Yn, then zk != xm implies that Z is an LCS of \(X_{m-1}\) and \(Y_n\)

If Xm != Xn, then zk != ym implies that Z is an LCS of \(Y_{n-1}\) and \(X_m\)

마지막이 다르면, 둘 중 더 좋은 것을 선택하여 LCS로 설정한다.

 

LCS(i, j) = 0 (if i = 0 or j = 0)

LCS(i,j) = LCS(i -1, j -1) + 1 (if xi = yi)

LCS(i,j) = max[LCS(i,j-1), LCS(i-1,j)} (if xi != yi)

 

얘는 "칸"이 아니라 배열의 "교차점"이라고 생각하면 좋음

shortest path와도 비슷하다. 결국, 맨 왼쪽 위에서 오른쪽 아래로 가는 빠른 길로 가는 방법이다