편집 거리

편집 거리 알고리즘이란, 두 문자열의 유사도를 판단하는 알고리즘이다. 리벤슈테인 거리라는 이름으로도 불린다.

 

문제를 통해 알아보자.

 

문제

두 개의 문자열 A와 B가 주어졌을 때, 문자열 A를 편집하여 문자열 B를 만들고자 한다.
문자열 A를 편집할 때는 다음의 세 연산 중에서 한 번에 하나씩 선택하여 이용할 수 있다.

1. 삽입 : 특정한 위치에 하나의 문자를 삽입한다.
   
2. 삭제 : 특정한 위치에 있는 하나의 문제를 삭제한다.
   
3. 교체 : 특정한 위치에 있는 하나의 문자를 다른 문자로 교체한다.

이때 편집 거리란 문자열 A를 편집하여 문자열 B로 만들기 위해 사용한 연산의 수를 의미한다.
문자열 A를 문자열 B로 만드는 최소 편집 거리를 계산하라.

 

입력

문자열 A, B
각 문자열은 영문 알파벳으로만 구성되어 있으며, 각 문자열의 길이는 1보다 크거나 같고, 5,000보다 작거나 같다.

 

출력

최소 편집 거리를 출력한다.

 

풀이

문자열 A : sunday

문자열 B : saturday

두 문자열을 위와 같이 입력 받았다고 하자.

 

이 문제는 최소 편집 거리를 담을 2차원 테이블을 초기화한 뒤에, 최소 편집 거리를 계산해 테이블에 저장하는 과정으로 문제를 해결할 수 있다.(다이나믹 프로그래밍)

 

초기 2차원 테이블은 다음과 같이 구성된다.

	∅	s	a	t	u	r	d	a	y
∅	0	1	2	3	4	5	6	7	8
s	1
u	2
n	3
d	4
a	5
y	6

2차원 테이블은 왼쪽(열)에 잇는 문자열을 위쪽(행)에 있는 문자열로 바꾸는 비용을 직관적으로 보여준다. 예를 들어 dp[3][3]의 은 "sun"이라는 문자열을 "sat"이라는 문자열을 바꾸기 위한 최소 편집거리가 된다.

(∅은 빈 문자열을 의미한다)

 

다이나믹 프로그래밍의 점화식은 다음과 같다.

1. 두 문자가 같은 경우 : dp[i][j] = dp[i-1][j-1]
2. 두 문자가 다른 경우 : dp[i][j] = 1 + min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])

이를 말로 풀어서 쓰면 다음과 같다.

1. 행과 열에 해당하는 문자가 서로 같다면, 왼쪽 위에 해당하는 수를 그대로 대입
2. 행과 열에 해당하는 문자가 서로 다르다면, 왼쪽(삽입), 위쪽(삭제), 왼쪽 위(교체)에 해당하는 수 중에서 가장 작은 수에 1을 더해 대입

더 쉽게 예시를 들어보면

"sunday", "saturday"의 마지막 문자끼리 비교할 때 'y'로 같기 때문에 추가 비용이 들지 않는다. 그래서 "sunda", "saturda"의 최소 편집거리를(dp[i-1][j-1]) 그대로 대입하면 된다.

 

그러나 "sun", "sat" 같이 'n'과 't'가 다른 경우가 있다. 이 때는 삽입, 삭제 혹은 교체 연산이 필요하다.

1. "sun", "sa"의 최소 편집거리에서 1을 더한다 : 't' 삽입
2. "su", "sat"의 최소 편집거리에서 1을 더한다 : 'n' 삭제
3. "su" "sa"의 최소 편집거리에서 1을 더한다. : 'n' -> 't' 교체

위 세 가지 경우 중 최소값을 대입하면 된다.

 

결과적으로 테이블의 가장 오른쪽 아래에 있는 값이 구하고자 하는 최소 편집 거리가 된다. 즉, 아래 예시에서 최소 편집 거리는 3이다.

	∅	s	a	t	u	r	d	a	y
∅	0	1	2	3	4	5	6	7	8
s	1	0	1	2	3	4	5	6	7
u	2	1	1	2	2	3	4	5	6
n	3	2	2	2	3	3	4	5	6
d	4	3	3	3	3	4	3	4	5
a	5	4	3	4	4	4	4	3	4
y	6	5	4	4	5	5	5	4	3

 

코드는 다음과 같다.

# 최소 편집 거리(Edit Distance) 계산을 위한 다이나믹 프로그래밍
def edit_dist(str1, str2):
    n = len(str1)
    m = len(str2)

    # 다이나믹 프로그래밍을 위한 2차원 DP 테이블 초기화
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    # DP 테이블 초기 설정
    for i in range(1, n + 1):
        dp[i][0] = i
    for j in range(1, m + 1):
        dp[0][j] = j
    
    # 최소 편집 거리 계산
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            # 문자가 같다면, 왼쪽 위에 해당하는 수를 그대로 대입
            if str1[i - 1] == str2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            # 문자가 다르다면, 세 가지 경우 중에서 최솟값 찾기
            else: # 삽입(왼쪽), 삭제(위쪽), 교체(왼쪽 위) 중에서 최소 비용을 찾아 대입
                dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1])

    return dp[n][m]

# 두 문자열을 입력 받기
str1 = input()
str2 = input()

# 최소 편집 거리 출력
print(edit_dist(str1, str2))