[편집거리 (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’]
[표에 대한 설명]
- 엡실론은 빈 문자열을 의미
- 아래로 내려오면서 표를 채우는 것은 삭제 연산
- 옆으로 가면서 표를 채우는 방법은 삽입 연산이다.
- 같으면 대각선에 있는 것을 그대로 가져온다.
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은 두 스트링의 각각의 길이이다.
'CS > 알고리즘' 카테고리의 다른 글
Chap 6-1. 버블 정렬(Bubble Sort) (0) | 2022.05.28 |
---|---|
Chap 6. 정렬 알고리즘(sort) (0) | 2022.05.28 |
Chap 5-2.연속 행렬 곱셈 (0) | 2022.05.26 |
Chap 5-1. 0-1 배낭 문제 (0) | 2022.05.06 |
Chap 5. 동적 계획 알고리즘 (0) | 2022.05.05 |