Chap 5-3. 편집거리 (Edit Distance)

[편집거리 (Edit Distance)]

 

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

즉, 3개의 연산(삽입, 삭제, 대체)을 통해 다른 문자열로 변환이 가능하다.

 

[예시 strong -> stone]

strong을 stone으로 바꿔보자 2가지 방법이 가능하다. 

 

방법 1 )

순서대로 s, t는 그대로 두고 o를 삽입하고 r, o를 삭제한다.

n은 그대로 두고 g를 e로 바꾼다. ⇒ 총 4회의 편집 연산을 했다.

 

방법 2)

‘s’와 ‘t’는 그대로 사용한 후, ‘r’을 삭제하고, ‘o’와 ‘n’을 그대로 사용한 후, ‘g’를 ‘e’로 대체하여, 총 2회의 편집 연산만이 수행되고, 이는 최소 편집 횟수이다.

 

=> 2가지 방법을 보면 편집 연산의 횟수는 어떤 연산을 어느 문자에 수행하는가에 따라서 달라진다는 것을 알 수 있다.

 

[부분 문제로 어떻게 표현할까?]

“접두부(prefix)”를 살펴보자

strong → stone으로 바꿀 때

예를 들어, ‘stro’에서 ‘sto’로 바꾸는 편집 거리를 이미 계산해두었다면 나머지 ‘ng’ → ‘ne’로 바꾸는 편집거리만 찾으면 된다.

 

[부분 문자열의 정의] 

S 문자열 = ‘strong’이고,

T 문자열 = “stone”이라고 하자

그러면

 

(1) 문자열의 길이

|S| = m(문자열의 길이 = 5)

|T| = n (문자열의 길이 = 4)

 

(2) 문자열 하나의 원소

- S = s1, s2, s3…. sm

- T = t1, t2, t3 … tn

- E[i, j] = S의 i개의 문자(1번부터 i번째까지)를 T의 j개 문자(1부터 j번째까지)로 바꾸는 데 필요한 편집 거리를 기억해 놓는 공간

  ex) “strong” → “stone”에 대해서 ‘stro’를 ‘sto’로 바꾸기 위한 편집거리는 E[4, 3]에 저장돼 있을 것이다.

 

[계산과정]

(1) s1 → t1 으로 변경 [ ‘s’ ⇒ ‘s’ ]

s1 = t1 = ‘s’ 이므로 변경할 필요 없다. → E[1, 1] = 0

 

(2) s1 → t1 t2 로 변경 [ ‘s’ → ‘st’ ]

일단 s1 = t1 = ‘s’이고 ‘t’을 삽입해야 하므로 1번의 연산만 필요하다. → E[1, 2] = 1

 

(3) s1 s2 → t1 로 변경 [’st’ → ‘s’ ]

‘st’ 가 ‘s’가 되기 위해서 ‘t’를 삭제해야 한다. 1번의 연산만 필요 → E[2, 1] = 1

 

(4) s1 s2 → t1 t2 로 변경 [’st’ → ‘st’ ]

s와 t가 같으므로 변경할 사항이 없다. → E[2, 2] = 0

 

*이 경우 E[1, 1] = 이라는 결과를 이용하고 s2 → t2만 계산하면 된다.

   E[1, 1] + 0 = 0이다.

 

이런 식으로 쭉 계산해 나간다. 이제 아래의 상황을 고려하여 일반화를 해보자

 

s1 s2 s3 s4 →t1 t2 t3 [‘stro’ ⇒ ‘sto’]

[표에 대한 설명]

1. 엡실론은 빈 문자열을 의미
2. 아래로 내려오면서 표를 채우는 것은 삭제 연산
3. 옆으로 가면서 표를 채우는 방법은 삽입 연산이다.
4. 같으면 대각선에 있는 것을 그대로 가져온다.

E[4, 2]의 해를 알면, t3=‘o’를 삽입하면 E[4, 2] + 1 E[3, 3]의 해를 알면, s4=‘o’를 삭제하면 E[3, 3] + 1

    E[3, 3]은 str → sto로 하는 것인데 r을 o으로 대체하는 연산이 필요하므로 1이다. ⇒ 1

E[3, 2]의 해를 알면, s4=‘o’과 t3=‘o’이 같으므로 E[3, 2] + 0 ⇒ 1

 

즉, 3가지 경우 중 최솟값을 찾으면 된다.

3가지 경우 = 위(삭제), 아래(삽입), 대각선(대체)

 

식으로 표현하면 다음과 같다.

다만, 대각선의 경우 비교하는 숫자가 다르면 1이 더해지고 같으면 0이 더해진다.

 

[의사코드]

입력: 스트링 S, T, 단, S와 T의 길이는 각각 m과 n이다.
출력: S를 T로 변환하는 편집 거리, E[m, n]
1. for i=0 to m E[i, 0] = i // 0번 열의 초기화
2. for j=0 to n E[0, j] = j // 0번 행의 초기화
3. for i=1 to m
4.     for j=1 to n
5.     E[i, j] = min{E[i, j-1]+1, E[i-1, j]+1, E[i-1, j1]+α}
6. return E[m, n]

 

[코드 구현]

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N 100

int getMin(int a, int b, int c)
{
	if (a < b)
		if (a < c)
			return a;
		else
			return c;
	else
		if (b < c)
			return b;
		else
			return c;
}

int editDistance(char* S, char* T, int m, int n)
{
	int E[m+1][n+1]; //엡실론(공백) 도 포함해야 하기 때문에 
	
	for (int j = 0; j <= n; j++) //초기화 
	{
		E[0][j] = j;
	}
	for (int i = 0; i <= m; i++)
	{
		E[i][0] = i;
	}

	for (int i = 1; i <= m; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (S[i - 1] == T[j - 1])
				E[i][j] = E[i - 1][j - 1]; // 같으면 이전에 있는 값 그대로 
			else
				E[i][j] = getMin(E[i][j - 1], E[i - 1][j], E[i - 1][j - 1]) + 1; //세 가지 연산 중 최솟값 
		}
	}

	for (int i = 0; i <= m; i++) //배열 출력 
	{
		for (int j = 0; j <= n; j++)
			printf("%d", E[i][j]);
		printf("\\n");

	}

}

int main()
{
	char S[N] = "STRONG";
	char T[N] = "STONE";

	editDistance(S, T, strlen(S), strlen(T));

	return 0;
}

 

시간 복잡도

EditDistance 알고리즘의 시간 복잡도는 O(mn).

단, m과 n은 두 스트링의 각각의 길이이다.