[알고리즘] 동적계획법 | 스트링 편집 거리(String edit distance)

스트링 편집 거리(String edit distance)는 두 스트링의 유사도를 측정하기 위해 사용되는 알고리즘을 말한다.

이 알고리즘을 제안한 수학자의 이름을 따서 레벤슈타인 거리 라고도 불린다. (LD)

 

원래 스트링: S

목표 스트링: T

 

라고 할때, 원래 스트링을 목표 스트링으로 변환하는데 필요한 삽입, 삭제, 대치 연산의 최소 비용을 편집 거리하고 한다.

 

삽입: 원래 스트링에 새로운 문자를 삽입하는 연산

삭제: 특정 위치에 있는 문자를 삭제 

대치 : 특정 위치의 문자를 다른 문자로 바꾸는 연산

세 종류의 연산마다 비용이 정해져 있다.

 

예를 들어보자!

 

S: "test"이고 T: "tent"라면, "s" 을 "n"으로 변경하는 하나의 대치 연산을 함으로써

S를 T로 변환할 수 있으므로 LD(S, T) = 1이된다.

일반적으로 편집 거리가 커질수록, 두 스트링의 유사도는 낮아진다.

(당연한 말...)

이 알고리즘은 표절 탐지, DNA 분석, 음성인식, 철자 검사 등에 사용된다.

 

더 구체적인 예를 들어보면,

GUMBO라는 단어와 GAMBOL이라는 단어의 편집 거리는

U -> A로 대치 (비용 +1), 맨 마지막에 L 추가 (비용 +1)로 편집 거리는 2가 된다.

(삽입, 삭제, 대치 비용 모두 1로 설정했다.)

 

이를 MxN 행렬로 나타내서 계산해보면, 다음과 같이 나타낼 수 있다.

행렬의 [0][0] 인덱스의 0은 빈 문자열 로부터의 편집 거리이다.

0을 시작으로 1,2,3,4.. 를 채워 넣게 되고, 이는 빈 문자열을 기준으로 최소 편집 거리를 의미한다.

ex) 행렬의 [0][5] -> 5: 빈 문자열에서 'GUMBO'를 만드는데 최소 편집 비용 (삽입 5번)

 

같은 방식으로 두 번째 행과 두 번째 열을 채워 넣으면 위와 같이 채워 넣을 수 있다.

 

ex) 행렬의 [1][4] -> 3: 문자열 'G'에서 'GUMB'를 만드는데 필요한 최소 편집 비용 (삽입: 3번)

 

이와 같은 방법으로 행렬을 모두 채우면,

'GUMBO' -> 'GAMBOL'로 변환하는데 필요한 최소 편집 거리를 구할 수 있다!

 

여기서,  최소 편집 거리를 구할 때 이전에 구해둔 최적 해를 사용하여 점차 더 큰 문제의 최적해를 구해나갈 수 있다.

 

여기서 알 수 있는 점:

 

두 문자가 서로 다를 때

왼쪽에 1을 더하는 것: 단어 삭제

왼쪽 위(대각선 위)에 1을 더하기: 단어 대치

위쪽에 1을 더하기: 단어 삽입이 된다.

 

이 동적 프로그래밍의 알고리즘을 총 정리 해보겠다!

 

*행과 열에 해당하는 단어가 같다면, 왼쪽 위에 해당하는 숫자를 그대로 가져온다.

*행과 열에 해당하는 단어가 다르다면 왼쪽, 왼쪽 위, 위쪽에 해당하는 숫자 중 최소값에 +1을해서 가져온다.

 

 

점화식

D[i,j] = min(D[i,j-1] + 삽입 비용, D[i-1,j] + 삭제비용, D[i-1,j-1] + 대치 비용)

 

여기서 대치 비용은 S[i] == T[j] 일 때는 0,

S[i] != T[j]일 때는 1   (참고 S: 원래 스트링  T: 비교 스트링)

 

ex)  'GU' -> 'GA'의 최소 편집 거리를 구할 때 (행렬에서는 [3][3]),  

점화식을 사용해 구해보면 min(2,2,1)로 값은 1이 나오게 된다.

 

 

파이썬 코드

def edit_distance(s:str, t: str):
    m = len(s)+1
    n = len(t)+1
    D = [[0]*m for _ in range(n)]
    D[0][0] = 0
    
    for i in range(1,m):
        D[0][i] = D[0][i-1] + 1
    
    for j in range(1,n):
        D[j][0] = D[j-1][0] + 1
    
    for i in range(1,n):
        for j in range(1,m):
            cost = 0

            if s[j-1] != t[i-1]:
                cost = 1
            
            D[i][j] = min(D[i][j-1] + 1,D[i-1][j] + 1, D[i-1][j-1] + cost)
    
    return D[n-1][m-1]
                
edit_distance('GUMBO', 'GAMBOL')