편집 거리

편집 거리 (Edit Distance)

삽입(insert), 삭제(delete), 대체(substitute) 연산을 사용하여 스트링 S를 수정하여 다른 스트링 T로 변환하고자 할 때 필요한 최소의 편집 연산 횟수

---

예제

S = strong

T = stone

E[i, j] = S의 처음 i개 문자를 T의 처음 j개 문자로 바꾸는데 필요한 편집 거리

E[4, 3] = 'strong' → 'stone'에 대해서, 'stro'를 'sto'로 바꾸기 위한 편집 거리

s₁ → t₁ ['s' → 's'] : s₁ = t₁ = 's' 이므로 E[1, 1] = 0

s₁ → t₁t₂ ['s' → 'st'] : s₁ = t₁ = 's'이고, 't'를 삽입하므로 E[1, 2] = 1

s₁s₂ → t₁ ['st' → 's'] : s₁ = t₁ = 's'이고, 't'를 삭제하므로 E[2, 1] = 1

s₁s₂ → t₁t₂ ['st' → 'st'] : s₁ = t₁ = 's'이고, s₂ = t₂ = 't' 이므로 E[2, 2] = E[1, 1] + 0 = 0

 

즉, E[4, 3]은 바로 그 주위의 편집 거리를 알면 해결 가능 (아래 그림 참고)

◼ E[4, 2]의 해를 알면 그 해에 t₃인 'o'를 삽입 (+1)

◼ E[3, 3]의 해를 알면 그 해에 s₄인 'o'를 삭제 (+1)

◼ E[3, 2]의 해를 알면 그 해에 s₄와 t₃의 문자가 같은 지를 비교 후 같으면 연산 X (+0) (만약 다르면 +1)

위 세 개의 값 중 가장 작은 값이 E[4, 3]

참고) 알기 쉬운 알고리즘

 

 

E[i, j] = min{E[i, j-1]+1, E[i-1, j]+1, E[i-1 j-1]+α}

(if s_i와 t_j가 다르면 α=1, s_i와 t_j가 같으면 α=0)

참고) 알기 쉬운 알고리즘

 

 

'strong' → 'stone'으로 바꾸는데 필요한 편집 거리

E[6, 5] = 2

참고) 알기 쉬운 알고리즘

 

 

def edit_distance(S, T):
    m = len(S)
    n = len(T)
    E = [[0] * (n + 1) for _ in range(m + 1)]   # 2차원 배열 생성
    
    for i in range(n + 1):      # 0번 열의 초기화
        E[0][i] = i
        
    for i in range(m + 1):      # 0번 행의 초기화
        E[i][0] = i
        
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            alpha = 0 if S[i-1] == T[j-1] else 1
            E[i][j] = min(E[i][j-1]+1, E[i-1][j]+1, E[i-1][j-1]+alpha)
            
        # print(E[i])
    
    return E, E[m][n]
    

def print_array2d(arr):
    for i in range(len(arr)):   # 행
        print(arr[i])


# 실행    
if __name__ == "__main__":
    s = "strong"
    t = "stone"
    array, editDistance = edit_distance(s,t)
    print_array2d(array)
    print(f"{s} -> {t} 편집 거리: {editDistance}")

 

실행 결과