[Python] 편집 거리 알고리즘 ( Edit Distance )

[Python] 편집거리 알고리즘

편집거리 알고리즘은 두 문자열의 유사도를 판단하는 알고리즘이다.

수정, 삽입, 삭제 기능이 있다고 할 때 몇 번의 동작이 필요한지 측정한다. 문자열 내에서 위치 변환 같은 기능이 없다.

2차원 메모이제이션 배열을 사용하는 Dynamic Programming의 한 종류이다.

편집거리 알고리즘의 규칙

1. str1에서 i번째 문자와 str2에서 j번째 문자를 서로 비교한다.
2. 두 문자가 같으면 dp[i-1][j-1]의 값을 그대로 가져온다.
3. 두 문자가 다르면 dp[i-1][j], dp[i][j-1], dp[i-1][j-1] 중 최소값에 1을 더해서 dp[i][j]에 저장

설명

편집 거리를 계산할 때 기준을 먼저 잡아야 한다. 왼쪽 문자열에서 위쪽 문자열로 변환한다고 기준을 잡겠다. 왼 쪽의 H와 위 쪽의 H를 비교할 때는 'PH' 가 'PYTH' 가 되기 위해서 연산이 몇 번 필요한 지 확인하는 것이다.

초기 상태는 위와 같다. 첫 행으로 설명을 하자면 빈 문자열{} 이 {}, P, PY, PYT, ... 로 바뀌기 위해서 몇 번의 연산이 필요한 지 나타내는 것이다. {}에서 {}이 되려면 아무 연산이 필요 없으므로 0, PYT가 되려면 P, Y, T를 각각 삽입해야 하므로 3이 된다.

'PH'가 'PYTH'가 되기 위한 연산의 수는 'P'를 'PYT'로 바꾸는 연산의 수와 같다. 두 문자열에서 똑같은 'H'를 붙이는 것이기 때문이다.

'O'와 'H'를 비교한 경우를 생각해보자.

1. A의 경우를 보면 'PH'에서 'PYT'로 2번의 연산으로 변환이 되었다고 생각한다. 다음 줄로 오면서 'O'가 더해지고 'PYTO'가 된 상황이다. 이 때는 'O'를 'H'로 수정 연산을 하면 된다.
2. B의 경우 'PH'를 'PYTH'로 2번의 연산으로 변환이 되었다고 생각한다. 마찬가지로 다음 줄로 넘어가면서 'O'가 더해지고 'PYTHO'가 된 상황이다. 이 경우에는 'O'를 삭제 연산을 하게 되면 'PYTH'로 만들 수 있다.
3. C의 경우 'PHO'를 'PYT'로 2번의 연산으로 변환이 되었다고 생각한다. 이 경우에는 다음 줄이 되는 것이 아니므로 'O'가 더해지는 것은 아니다. 'PYT'에서 'H'를 삽입하는 연산을 하게 되면 'PYTH'로 만들 수 있다.

각각의 횟수는 2번의 연산에 한 번 더 연산을 하는 과정이 필요하므로 3번 연산을 하면 'PHO'를 'PYTH'로 바꿀 수 있다. 우리는 최소 편집 거리를 찾기 때문에 A, B, C 과정을 한 후 최소값을 dp 테이블에 넣어주면 된다.

위에서 같은 문자끼리 비교하는 경우에는 A의 연산의 특수한 경우로 생각하면 된다. 수정 연산을 생각할 때 두 문자가 같으므로 수정을 굳이 안 해도 되는 경우라고 생각한다. 그리고 dp[i-1][j-1]은 dp[i-1][j] + 1, dp[i][j-1] + 1과 비교했을 때 최솟값을 가지는 것이 보장된다.

결과

모든 계산이 끝난 후의 결과는 그림과 같다. 이 후에 우리는 dp[-1][-1]을 계산하면 최소 편집 거리를 구할 수 있다. 최소 편집 거리를 만드는 경로는 여러가지가 될 수 있다.

CODE

def edit_dist(str1, str2):
    dp = [[0] * (len(str2)+1) for _ in range(len(str1) + 1)]
    for i in range(1, len(str1)+1):
        dp[i][0] = i
    for j in range(1, len(str2)+1):
        dp[0][j] = j

    for i in range(1, len(str1)+1):
        for j in range(1, len(str2)+1):
            if str1[i-1] == str2[j-1]:
                dp[i][j] = dp[i-1][j-1]

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

    return dp[-1][-1]


print(edit_dist('PYTHON', 'PHOTO'))     # 4