[최단거리] 편집 거리. 이해하기 어려우시다고요?

 편집거리

 어떤 문자열에서 다른 문자열로 삽입, 삭제, 수정 세 가지 연산을 이용하여 변환할 때 해당 연산의 횟수를 편집거리라고 한다. 

 

 

---

 

알고리즘

 algorithmic을 altruistic로 변환한다. 

 

1. 먼저 앞에 al은 동일하기 때문에 어떤 연산도 하지 않는다.

2. g를 t로 바꾸는 수정연산을 한다. 

3. o를 r로 바꾸는 수정연산을 할 수도 있지만, 그런 것보다 o를 삭제하고 그 다음 r을 유지하는 것이 편집거리를 줄일 수 있으므로 o를 삭제하는 삭제 연산을 진행한다. 

 이렇게 o를 삭제하고 그 뒤의 r을 활용한다. 

4. 원래는 i=> u로 바꾸는 수정연산을 해야 하지만, 그것보다는 앞에 u를 추가하는 것이 편집거리를 줄일 수 있으므로 u를 추가하는 추가연산을 진행한다. 

5. 이제 말하지 않아도 알 거다. s를 추가해주는 추가 연산을 해 준다.. 

6. 다음은 원래 h를 i로 바꾸는 수정연산을 해야하지만 맨 뒤에 ic가 동일하므로 가운데 h와 m을 제거하는 삭제연산을 두 번 제거 해준다. 

 

 결과적으로 편집거리는 6번의 연산(삽입, 수정, 삭제)를 했으므로 6이 된다. 

 

 

---

 

편집거리 표

 행(algoruisthmic)=>열(altruistic)

 

 먼저 null값에서 해당 문자열들을 하나씩 추가해준다. 무슨 소리냐면, 0행 1열은 null값=>a니까 삽입연산을 한 번 거쳐야 한다. 그 뒤로도 계속 삽입연산해서 +1씩 되는거다. 

 계산 방식에 대해 두 가지만 알아보자. 

 

1. algorit=>alt

 삭제 연산 4번을 하므로 편집거리는 4가 된다.

2. altruis => altruis

 1 수정 연산, 4 추가 연산으로 편집거리는 5가 된다. 

 

---

 

코드

str1='algorithmic'
str2='altruistic'

ed = [[0] * (len(str2)+1) for _ in range(len(str1) + 1)]  #배열 초기화

for i in range(1, len(str1)+1): ed[i][0] = i  #null값에서의 편집거리
for j in range(1, len(str2)+1): ed[0][j] = j  #null값엥서의 편집거리

for i in range(1, len(str1)+1):   #null값을 제외하고, 문자열 길이만큼 반복
    for j in range(1, len(str2)+1): #null값을 제외하고, 문자열 길이만큼 반복
        if str1[i-1] == str2[j-1]: ed[i][j] = ed[i-1][j-1]  #현재 문자열이 동일하다면 편집거리를 찾을 필요 없음
        else: ed[i][j] = min(ed[i-1][j-1], ed[i-1][j], ed[i][j-1]) + 1 #현재 문자열이 동일하지 않다면 최소 편집거리를 찾아야 함, 편집했으므로 +1을 해줌
        
print('편집거리 : ', ed[-1][-1])  #편집거리 출력