Minimum Edit Distance

해당 동적 프로그래밍의 알고리즘을 정리하면 특정 위치에서의 값을 구하는 방법은

(i) 만약 행과 열에 해당하는 단어가 같다면 왼쪽 위에 해당하는 숫자를 그대로 가져오기

(ii) 만약 행과 열에 해당하는 단어가 다르다면 왼쪽, 왼쪽 위, 위쪽에 해당하는 숫자 중 가장 작은 숫자에 1을 더해 가져오기

두 문자가 서로 다를 때

(i) 왼쪽에 1을 더한값을 현재 할당 : 단어 추가(Add)

(i) 왼쪽 위에 1을 더한값을 현재 할당 : 단어 편집(Edit)

(i) 위쪽에 1을 더한값을 현재 할당 : 단어 삭제(Delete)

  가 되는 것입니다. 현재까지는 a와 ab를 비교할 때 a에 b를 더하면 간단하기 때문에 단어 추가(Add)에  해당하고 그렇기 때문에 거리가 1인 것을 이야기할 수 있습니다. 결과적으로 위 사진과 같이 행(a) 열(ab)에 해당하는 숫자가 1이 들어간 것을 볼 수 있습니다. 즉 3가지 기능을 바로 행렬 매트릭스에 적용함으로써 아주 간단하게 동적 프로그래밍이 설계되었다고 할 수 있습니다.

결과적으로 가장 오른쪽 하단에 있는 3이 최소 편집 거리(Minimum Edit Distance)가 되는 것입니다. 이제 반대로 편집 과정을 추적해보도록 합니다. 이 때는 가장 오른쪽 밑에서부터 시작하되 각각의 위치에서 다음의 알고리즘을 따르면 됩니다.

출처) http://blog.naver.com/PostView.nhn?blogId=ndb796&logNo=220870218783&parentCategoryNo=23&categoryNo=&viewDate=&isShowPopularPosts=true&from=search#