m 으로 변하는 한 글자의 변화로 첫번째 단어가 두번째로 된다. 단어 sport 는 p 한글자를 삭제하면 sort로 바뀔수 있고, 동일하게 sort는 p 한글자를 삽입하면 sport가 된다. 두 문자열 s1, s2의 편집거리는 s1에서 s2로의 최소 변환 문자의 수로 정의된다.
- 문자 변환
- 문자 삽입
- 문자 삭제
이런 반복적인 관계에 따라 편집 거리는 문자열 s1, s2에 대해 d(s1,s2)로 정의된다.
d(' ','') = 0 (''은 텅빈 문자열이다) d(s,'') = d('', s) = |s| (텅 빈 문자열과 s의 거리는 s의 길이이다.) d(s1+ch1, s2+ch2) = min( d(s1, s2) + ch1 != ch2 , (s1과 s2의 최소편집거리 + 두 문자의 유사도) d(s1+ch1, s2) + 1, (s1에 ch1이 삽입된 것과 s2와의 유사도 + 1) d(s1, s2+ch2) + 1 ) (s2에 ch2가 삽입된 것과 s2와의 유사도 + 1) (이 중 최소값을 선택하게 된다.)처음 두개의 규칙에 대해서는 명백한 사실이므로, 마지막 하나에 대한 고민만이 필수적이다. 여기 텅빈 문자열이 아닌, 서로 마지막 문자를 가진 각각의의 문자 ch1과 ch2이다. 어떻게든, ch1과 ch2는 s1+ch1과 s2+ch2의 편집으로 설명되야 한다.
만약 ch1 과 ch2 가 같다면, 그들은 아무 문제없이 일치될 수 있고, 전체 편집 거리는 d(s1,s2) 그대로 된다. 만약 ch1과 ch2가 다르다면, ch1은 ch2로 변경되어야만 하므로 전체적인 비용은 d(s1,s2)+1 이 된다. 다른 가능성은 ch1이 삭제되고, s1 과 s2+ch2이 편집되어 d(s1,s2+ch2)+1 이 되는 것이다. 마지막 가능성은 s1+ch1 이 s2와 편집이 되고 ch2가 삽입이 되어 d(s1+ch1,s2)+1이 되는 것이다. 다른 대안은 없다. 우리는 이 가능 대안 중 최소 비용을 선택하면 된다.
이 반복적인 관계는 명백히 삼중 재귀로 늘어난다. O(3^n) 이것은 기하급수적으로 느려지고 매우 적은 문자들 이상의 문자열에서는 비실용적이기 때문에 좋은 방법이 아니다.
이 관계들의 사례는 d(s1,s2)는 d(s1',s2')에 대해 s1'이 s1보다 짧거나, s2'는 s2보다 짧거나, 혹은 둘 다에 전적으로 의존하는 것을 보여준다. 이것은 동적 계획법 노하우가 사용되는 것을 따른다.
이차원 배열 m[|s1|][|s2|]은 편집거리값 고정에 이용된다.
m[i,j] = d(s1[1..i], s2[1..j]) m[0][0] = 0 m[i][0] = i, i=1..|s1| m[0][j] = j, i=1..|s2| m[i][j] = min( m[i-1][j-1] + s1[i] != s2[j] , m[i-1][j] + 1, m[i][j-1] + 1 ), i=1..|s1|, j=1..|s2|m[][]은 순차적으로 계산된다. i번째 줄은 i-1번째 줄에 의존된다. 이 알고리즘의 시간복잡도는 O(|S1|*|S2|)이다. 만약 s1과 s2과 비슷한 길이 n이라면, 시간복잡도는 O(n^2)로 기하급수보다 좋아지게 된다!원문 : http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Dynamic/Edit/ 번역 : pl0892029