[알고리즘] 최소편집거리 알고리즘 edit distance, Levenshtien distance

- 동적프로그래밍을 사용한다.

- 서로 다른 문자열 str1과 str2이 같아지기 위해 몇 번의 과정을 거쳐야 하는지 이다. (두 문자열 사이 유사도 측정)

- 과정에서 할 수 있는 동작은 insert, delete, replace 아래 3가지이다.

예를 들어 abcdeg를 azcde로 바꾼다면

1. 문자 지우기 : g를 지운다.

2. 문자 삽입

3. 문자 바꿔치기(replace): b를 z로 바꾼다. 가 될 수 있다.

 

접근방법:

이차원 배열을 사용한다. dp[i][j]

dp[i][j]가 의미하는 바는 str1.substr(0,i)와 str2.substr(0,j)사이의 거리를 의미한다.

dp[0][0]은 공문자열 사이에서 비교하는 것이기 때문에 거리가 0이다. dp[0][i]는 공문자열과 str.substr(0,i)을 비교하는 것이기 때문에 dp[0][i] = i가 될 것이다. dp[i][0]도 마찬가지.

 

i와 j가 1이상일 경우를 따져보자. 이 때부터 주어진 위치에서 위, 왼쪽 위, 왼쪽을 본다.

1. str1[i] == str2[j] 인 경우

왼쪽 위값을 그대로 가져온다. 일치하는 최소 문자열의 거리를 가져온 셈

2. 다른 경우

셋 중에 가장 작은 값에 + 1을 한다. 일치하는 최소 문자열에 add delete replace중 하나를 했기 때문.

 

완성

최종적으로 두 문자열 사이 최소 거리는 오른쪽 맨 아래 있는 2이다.

이제 위 표가 의마하는 바를 오른쪽 아래부터 거꾸로 살펴보자.

 

현재 위치에서 왼쪽, 위쪽, 왼쪽 위 셋 중에 가장 작은 값을 s라 하자.

1. s와 현재 위치가 같다면 변화가 없다는 의미다. (빨간 네모)

2. s가 현재 위치값보다 작다면

2-1. s가 왼쪽: 문자열이 delete된 것 (보라 네모)

2-2. s가 왼위: 문자열이 replace된 것 (파란 네모)

2-3. s가 위: 문자열이 add된 것 (안만들어쪄..ㅠ)

 

수도 코드로 정리해보자

int dp[n][m];

for(int i=0; i<n; i++){
	for(int j=0; j<m; j++){
    	if(i==0) dp[0][j] = j;
        else if(j==0) dp[i][0] = i;
        else {
        
        	if(str[i] == str[j]){
            	dp[i][j] = dp[i-1][j-1];
                continue;
            }
        	dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1;
        }
    }
}

요렇게 된다.

 

참고:

m.blog.naver.com/ndb796/220870218783

최소 편집 거리(Minimum Edit Distance) 알고리즘

en.wikipedia.org/wiki/Edit_distance

Edit distance - Wikipedia