편집거리 알고리즘 [파이썬]

알고리즘

리벤 슈테인 알고리즘 사용

두 개의 문자열 A, B가 주어졌을 때 두 문자열이 얼마나 유사한 지를 알아낼 수 있는 알고리즘입니다.

문자열 A가 문자열 B와 같아지기 위해서는 몇 번의 연산을 진행해야 하는 지 계산할 수 있습니다.

여기서의 연산이란, 삽입(Insertion), 삽입(Deletion), 대체(Replacement)를 말합니다.

 

점화식

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

 

입력 데이터가 다음이라고 생각해보자

str1 = 'saturday'

str2 = 'sunday'

S 를 가지고 SA 를 만들기 위한 최소 편집 거리에 교체 연산을 추가로 실시

SAU -> SAT 로 만들기 위한 것이라고 생각하면 된다. 

DP[2][3] = DP[1][2] + 교체 연산

소스코드

def edit_dist(str1, str2):
    n = len(str1)
    m = len(str2)

    dp = [[0] * (m + 1) for _ in range(n + 1)]
    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]
     #문자가 다르다면, 3가지 경우 중에서 최솟값 찾기
            else: #삽입(왼쪽), 삭제(위쪽), 교체 (왼쪽 위) 중에서 최소 비용
                dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1])

    for i in dp:
        for j in i:
            print(j, end=" ")
        print("")
    return dp[n][m]

str1 = 'sunday'
str2 = 'saturday'

print(edit_dist(str1, str2))

결과화면