최소 편집 거리(edit distance)를 구하는 알고리즘

1. 문제

 

두 문자열 S1, S2가 주어질때, 다음과 같은 3가지 연산을 임의의 횟수만큼 실행할 수 있다.

 

1) 임의의 위치에 원하는 문자 하나를 삽입

 

예: banana >>> banacna

 

2) 임의의 위치에 있는 문자 하나를 삭제

 

예: banana >>> banna

 

3) 임의의 위치에 있는 문자 하나를 원하는 문자로 대체

 

예: banana >>> canana

 

 

2. 재귀를 이용한 해법

 

문자열의 왼쪽이나 오른쪽 끝에서부터 한문자씩 처리한다.

 

왼쪽부터 처리해서, 첫번째 문자가 서로 일치하는 경우, 나머지 문자에 대해 재귀적으로 처리

 

첫번째 문자가 서로 일치하지 않는다면, 여기에 3가지 작업으로 삽입, 제거, 대체 작업을 수행할 수 있다.

 

그리고 나머지 부분에 대해 재귀적으로 계산

 

 

첫번째 문자가 일치하면, 나머지 부분에 대해 계산하기 위해 f(len(s1)-1, len(s2)-1)

 

첫번째 문자가 일치하지 않는 경우

 

s2[0]를 s1의 처음에 삽입하면, s1의 길이는 len(s1)+1인데, 처음을 제외한 len(s1)부분을 len(s2)-1에 일치시켜야하므로

 

f(len(s1),len(s2)-1)

 

예를 들어 s1 = abc, s2 = cd이면 s2[0]를 s1의 처음에 삽입하면 cabc인데, 이러면 s2 = cd와 비교해서 첫번째가 일치하므로

 

len(s1) = 4로 1 증가했으므로, 일치시켜야하는 나머지 부분 abc는 len(s1) = 3이니까, len(s1)을 나머지 len(s2)-1부분인

 

s2 = d와 일치시켜야한다는 소리

 

 

s1[0]를 s2[0]로 바꾸면, s1의 처음을 제외한 len(s1)-1부분과 s2의 처음을 제외한 len(s2)-1 부분을 일치시켜야하므로,

 

f(len(s1)-1, len(s2)-1)

 

 

s1[0]를 삭제하면 s1의 나머지 부분 len(s1)-1을 s2에 일치시켜야하므로 f(len(s1)-1,len(s2))

 

def edit_distance(s1,s2,m,n):
    
    if s1[0] == s2[0]:
        
        return edit_distance(s1,s2,m-1,n-1)
    
    else:
        
        return 1 + min(edit_distance(s1,s2,m,n-1),edit_distance(s1,s2,m-1,n-1),edit_distance(m-1,n))

 

 

만약 len(s1) = m = 0이 된다면 len(s2)만큼 추가 연산을 수행하면 s1을 s2로 만들 수 있다.

 

마찬가지로 len(s2) = n = 0이 된다면 len(s1)만큼 삭제 연산을 수행하면 s1을 s2로 만들 수 있다

 

def edit_distance(s1,s2,m,n):
    
    if m == 0:
        
        return n
    
    if n == 0:
        
        return m
        
    if s1[0] == s2[0]:
        
        return edit_distance(s1,s2,m-1,n-1)
    
    else:
        
        return 1 + min(edit_distance(s1,s2,m,n-1),edit_distance(s1,s2,m-1,n-1),edit_distance(s1,s2,m-1,n))

 

 

근데 이렇게 하면... 재귀함수 매개변수로 s1,s2는 고정이고 비교하는 문자는 첫번째 문자 s1[0],s2[0]로 그대로니까...

 

매번 똑같은 연산을 수행해버린다는거임

 

무슨 말이냐면 예를 들어 s1 = abc, s2 = cab라고 하면

 

처음에 f(s1,s2,3,3)이 들어갈건데... s1[0] = a, s2[0] = c가 서로 다르니까..

 

1 + min(f(s1,s2,2,3), f(s1,s2,2,2), f(s1,s2,3,2))를 수행하러 들어갈건데...

 

만약 f(s1,s2,2,3)을 수행하러간다면... 또 s1[0] = a, s2[0] = c를 수행해버린다는거임

 

f(s1,s2,2,3)은 s1 = bc, s2 = cab로부터 s1을 s2로 바꿔야한다는건데 s1[0] = b, s2[0] = c를 비교해야한다는건데...

 

s1,s2는 그대로 들어가니까 문제

 

def edit_distance(s1,s2,m,n):
    
    if m == len(s1):
        
        return len(s2)-n
    
    if n == len(s2):
        
        return len(s1)-m

    if s1[m] == s2[n]:
        
        return edit_distance(s1,s2,m+1,n+1)
    
    else:
        
        return 1 + min(edit_distance(s1,s2,m,n+1),edit_distance(s1,s2,m+1,n+1),edit_distance(s1,s2,m+1,n))

 

 

그래서 edit_distance(s1,s2,0,0)으로 0부터 시작해서 1씩 증가시켜나간다음, 길이가 다 채워지면 나머지만큼 연산을 수행하도록 

 

이건 근데 그림이 너무 안이쁘다해야하나...

 

그래서 보통은 오른쪽 끝에서부터 처리함

 

마지막 문자가 서로 일치한다면 f(s1,s2,m-1,n-1)

 

마지막 문자가 서로 다르다면 1+min(f(s1,s2,m-1,n),f(s1,s2,m-1,n-1),f(s1,s2,m,n-1))

 

구하고자 하는 값은 f(s1,s2,len(s1),len(s2))

 

이때 마지막 문자 비교는 m,n이 1씩 감소하면서 s1[m-1] == s2[n-1]로 자연스럽게 할 수 있다

 

def edit_distance(s1,s2,m,n):
    
    if m == 0:
        
        return n
    
    if n == 0:
        
        return m

    if s1[m-1] == s2[n-1]:
        
        return edit_distance(s1,s2,m-1,n-1)
    
    else:
        
        return 1 + min(edit_distance(s1,s2,m,n-1),edit_distance(s1,s2,m-1,n-1),edit_distance(s1,s2,m-1,n))

s1 = input()
s2 = input()

print(edit_distance(s1,s2,len(s1),len(s2)))

 

 

 

이렇게 하면 되긴하는데 문제는 시간복잡도가 $O(3^{m})$으로 너무 크다는거임

 

 

3. 메모이제이션

 

위의 재귀 방식은 다음 그림을 보면 f(m-1,n-1)은 3번 호출되고 f(m-1,n-2)는 2번, f(m-2,n-1)은 2번 호출되는 문제가 있다

 

동일한 계산을 여러번 한다는 문제

 

 

 

 

그래서 dp[i][j]에 f(s1,s2,i,j)을 저장해두고 이 값이 존재한다면 f(s1,s2,i,j)를 호출하지 말고 dp[i][j]를 바로 호출하도록

 

from sys import setrecursionlimit
setrecursionlimit(10**6)

def edit_distance(s1,s2,m,n):
    
    if m == 0:
        
        return n
    
    if n == 0:
        
        return m
    
    if dp[m][n] != -1:
        
        return dp[m][n]

    if s1[m-1] == s2[n-1]:
        
        dp[m][n] = edit_distance(s1,s2,m-1,n-1)
    
    else:
        
        dp[m][n] = 1 + min(edit_distance(s1,s2,m,n-1),edit_distance(s1,s2,m-1,n-1),edit_distance(s1,s2,m-1,n))
    
    return dp[m][n]

s1 = input()
s2 = input()

m = len(s1)
n = len(s2)

dp = [[-1]*(n+1) for _ in range(m+1)]

print(edit_distance(s1,s2,m,n))

 

 

이러면 시간복잡도는 O(MN)이라는데 재귀라서 좀 느리다

 

 

4. 다이나믹 프로그래밍

 

위 논리 그대로를 dp배열만을 사용해서 해결할 수 있다

 

dp[i][j] = s1[:i+1]과 s2[:j+1]사이 edit distance의 최솟값

 

s1[i]와 s2[j]가 서로 같다면, dp[m][n] = edit_distance(s1,s2,m-1,n-1)을 그대로 넣어서

 

dp[i][j] = dp[i-1][j-1]

 

s1[i]와 s2[j]가 서로 다르다면, dp[m][n] = 1 + min(edit_distance(s1,s2,m,n-1),edit_distance(s1,s2,m-1,n-1),edit_distance(s1,s2,m-1,n))을 그대로 넣어서

 

dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1

 

최초 초기화는?

 

if m == 0: return n
    
if n == 0: return m

 

이거에 대응해서 dp[i][0] = i, dp[0][j] = j

 

def edit_distance(s1,s2):
    
    m,n = len(s1),len(s2)

    INF = 10**9

    dp = [[INF]*(n+1) for _ in range(m+1)]

    for i in range(m+1):
        
        dp[i][0] = i
    
    for j in range(n+1):
        
        dp[0][j] = j
    
    for i in range(1,m+1):
        
        for j in range(1,n+1):
            
            if s1[i-1] == s2[j-1]:
                
                dp[i][j] = dp[i-1][j-1]
            
            else:
                
                dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1
    
    return dp[m][n]

s1 = input()
s2 = input()

print(edit_distance(s1,s2))

 

 

 

5. 연습문제

 

 

15483번: 최소 편집