최소 편집 (Edit Distance) 문제에서 최소 편집 '횟수'를 구하는 것에서 확장하여
최소 편집 '방법'을 '추적'하는 문제이다.
문제 풀이
최소 편집 횟수를 구하는 table의 [r][c] 위치에서부터 [0][0]을 목적지로 가장 작은 숫자를 타고 올라가면
최적의 방법을 추적할 수 있다.
Pseudo Code
1. 3개의 값(좌, 상, 대각선) 중, 가장 작은 값을 찾는다.
(1) 가장 작은 값 = up 인 경우, DELETE 연산을 적용했다.
(2) 가장 작은 값 = left 인 경우, INSERT 연산을 적용했다.
(3) 가장 작은 값 = diagonal인 경우, 3-(1) 그 값이 현재값과 같은 경우, COPY를 적용했다.
3-(2) 그 값이 현재값과 다른 경우, SUBSTITUTE를 적용했다.
table[r-1][c-1]의 위치에서부터 [0][0]까지 1번 동작을 반복하며 stack에 적용한 연산의 종류를 넣는다.
2. stack이 empty상태가 될 때까지 있는 값을 출력한다.
위의 방법을 토대로 계산하면, 아래 그림의 빨간 네모를 따라서 이동하게 된다.
COPY COPY COPY DELETE COPY SUBSTITUTE SUBSTITUTE
내가 이해한 방법은 아래 그림과 함께 이해하기.
table[3][2] = "str" -> "st" = 1
좌, 상, 대각선 중에서 가장 작은 값 : 0 -> up = delete
*why*
table[r-1][c]에서 table[r][c]로 내려왔다는 건,
str1과 str2가 어떤 상태에서 s2는 그대로이고 s1만 문자가 추가되었다는 뜻이다.
그런데 s1에서 s2를 만들고 싶은거니까 가장 비슷했던 상황(table[r-1][c])에서 s1의 추가된 글자만 delete하는 연산을 하면 되는 것이다.
table[2][3] = "st" -> "sto" = 1
좌, 상, 대각선 중에서 가장 작은 값 : 0 -> left = INSERT
*why*
이것도 delete와 같은 맥락으로, 둘이 가장 가까웠던(비슷했던) 상태(table[r][c-1])에서
오른쪽으로 이동했다는 건,
s1은 변함이 없고 s2만 문자가 추가된 것이다.
그러면 s1을 s2로 바꾸고 싶은거니까 s1에 s2에 추가된 문자를 동일하게 INSERT하면 되는 것이다.
table[3][3] = "str" -> "sto" = 1
좌, 상, 대각선 중에서 가장 작은 값 : 0 -> diagonal, 현재값(1)과 다름 = SUBSTITUTE
*why*
str1과 str2이 가장 비슷했던 상태는 왼쪽 대각선이고, s1도 문자가 추가, s2도 문자가 추가된 것이다.
그런데 str1과 str2에 추가된 문자가 서로 다르므로(현재값과 다른 값을 가지고 있음) '대체' 연산이 적용된 것을 알 수 있다.
table[4][3] = "stron" -> "sto" : 1
좌, 상, 대각선 중에서 가장 작은 값 : 1 -> diagonal, 현재값(1)과 같음 = COPY
*why*
가장 작은 숫자인 대각선과 동일한 값이라는 것은 str1과 str2가 대각선의 위치에서 현재 위치로 이동하면서
s1도 증가하고 s2도 증가하였지만 아무 연산도 해주지 않았다는 것이다.
즉, 둘이 같은 값이 추가된 것이다.
*Edit Distance를 추적하는 방법이 딱 한 가지만 있을까?*
예를 들어, 끝에서 [0][0]방향으로 추적해가는 와중에, table[4][3]은 가장 작은 숫자 두 가지를 맞닥뜨리게 된다.
대각선인 table[3][2]와 위인 table[3][3] 모두 1의 값을 가지고 있다.
두 가지 경우 모두 생각해보자.
(1) 대각선에 위치한 table[3][2]를 지나갈 경우?
현재 위치(table[4][3])에 있는 값(1)과 동일한 값을 가지므로, COPY 연산을 적용한 것을 알 수 있음.
그리고 table[3][2]는 table[2][2]를 지나갈 것임.
따라서 COPY DELETE 연산을 수행했음.
(2) 위에 위치한 table[3][3]을 지나갈 경우?
DELETE연산을 수행했고, table[3][3]에서 table[2][2]로 갈 것인데 값이 다르므로
SUBSTITUTE 연산을 적용한 것을 알 수 있음.
따라서 DELETE SUBSTITUTE 연산을 수행했음
두 가지 경우 각각의 Edit Distance를 계산하면 (1)의 경우는 1, (2)의 경우는 2임.
결과적으로 (2)의 경우를 따를 경우 전체 edit distance가 다른 값이 나오는 것을 확인할 수 있고, (2)의 경우는 잘못된 것임.
따라서 좌, 상, 대각선 중 가장 작은 값을 찾을 때,
대각선이 가장 작을 경우를 우선순위로 둬야한다!!!!!!!
그리고 최적 편집 방법이 꼭 한 가지만 존재하는건지는 아직 확실치않다!!
지금 예시에서는 한 가지 방법만 존재함.
**구현할 때 유의사항
현재 위치에서 좌, 상, 대각선 3개 중에서 가장 작은 값을 고를 때,
대각선이 가장 작은 경우를 먼저 고려해줘야한다. 그래야 '최소' 편집 방법이 나올 수 있다.
왜냐하면 대각선이 copy일 수 있고, copy가 가장 작은 편집 거리 값(0)을 가지고 있기 때문이다.
C언어 구현코드
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
// 열거형
// 첫번째 변수부터 모든 변수가 0,1,2,3,...의 값을 차례로 가진다.
enum OPERATION {
COPY = 0,
INSERT,
DELETE,
SUBSTITUTE,
NON
};
int **createTable(int _num_r, int _num_c) {
int **res_table = (int **)malloc(_num_r*(sizeof(int*)));
for (int i = 0; i < _num_r; i++) {
res_table[i] = (int *)malloc(_num_c*(sizeof(int)));
}
return res_table;
}
int getMinimum(int a, int b, int c) {
if (a <= b && a <= c) return a;
else if (b <= a && b <= c) return b;
else if (c <= a && c <= b) return c;
}
void populateTable(int **_table, char *_s1, char *_s2, int _num_row, int _num_col) {
// 1행 채우기
for (int i = 0; i < _num_col; i++) {
_table[0][i] = i;
}
// 1열 채우기
for (int i = 0; i < _num_row; i++) {
_table[i][0] = i;
}
// 나머지 칸들 채우기
for (int i = 1; i < _num_row; i++) {
for (int j = 1; j < _num_col; j++) {
if (_s1[i-1]==_s2[j-1]) { // 마지막 글자가 같다면,
_table[i][j] = _table[i - 1][j - 1];
}
else {
_table[i][j] = getMinimum(_table[i][j-1], _table[i-1][j], _table[i-1][j-1]) + 1; // 좌, 상, 대각선
}
}
}
}
enum OPERATION *stack = 0; // stack을 전역변수로 생성해준다.
int stack_top = - 1;
void CreateStack(int _num_row, int _num_col) {
// stack의 최대 사이즈는 [num_row-1][num_col-1]에서 [0][0]로 가는 가장 긴 거리이다.
// 가장 긴 거리는 table의 테두리르 타고 올라가는 것으로,
// (행-1) +(열-1)이다.
stack = (enum OPERATION *)malloc(sizeof(enum OPERATION)*(_num_row + _num_col - 2));
stack_top = -1;
}
// 좌, 상, 대각선 중에서 가장 작은 값을 찾는 함수.
enum OPERATION findSmallestNeighbor(int **_table, int _r, int _c) {
int left, up, diag;
// boundary check를 해줘야한다.
// 좌
if (_c-1 >= 0) {
left = _table[_r][_c - 1];
}
else { // boundary를 넘어갈 경우,
// 절대 선택되지 못하도록 가장 큰 값으로 설정한다.
left = INT_MAX;
}
//상
if (_r-1>=0) {
up = _table[_r - 1][_c];
}
else {
up = INT_MAX;
}
// 대각선
if (_r-1>=0 && _c-1>=0) {
diag = _table[_r - 1][_c - 1];
}
else {
diag = INT_MAX;
}
// left, up, diag 중에서 가장 작은 값을 찾는다.
if (diag <= left && diag <= up) { // 대각선에 가장 높은 우선권을 줘야함!
if (_table[_r][_c] == diag) {
return COPY;
}
else {
return SUBSTITUTE;
}
}else if (left <= up && left<= diag) {
return INSERT;
}
else if (up <= left && up <= diag) {
return DELETE;
}
}
void stack_push(enum OPERAION _operation) {
stack_top++;
stack[stack_top] = _operation;
}
enum OPERATION stack_pop() {
if (stack_top==-1) { // empty
return NON;
}
enum OPERATION temp = stack[stack_top];
stack_top--;
return temp;
}
void showOperationSequence(int **_table, int _num_row, int _num_col) {
// 1. operation을 담을 stack을 만든다.
CreateStack(_num_row, _num_col);
// 2. [num_row-1][num_col-1] 부터 [0][0]까지 추적한다.
int r = _num_row - 1;
int c = _num_col - 1;
while (1) {
if (r == 0 && c == 0) { // 0,0일 경우 table을 추적 오나료.
break;
}
// 3개의 값(좌, 상, 대각선) 중 가장 작은 값을 확인하는 함수.
enum OPERATION result = findSmallestNeighbor(_table, r, c);
switch (result) {
case COPY:
stack_push(COPY);
r--;
c--;
break;
case INSERT:
stack_push(INSERT);
c--;
break;
case DELETE:
stack_push(DELETE);
r--;
break;
case SUBSTITUTE:
stack_push(SUBSTITUTE);
r--;
c--;
break;
}
}
// 3. stack이 empty 상태일 때까지, 출력한다.
while (1) {
enum OPERATION res = stack_pop();
if (res == NON) {
break;
}
switch (res) {
case COPY:
printf("operation COPY \n");
break;
case INSERT:
printf("operation INSERT \n");
break;
case DELETE:
printf("operation DELETE \n");
break;
case SUBSTITUTE:
printf("operation SUBSTITUTE \n");
break;
}
}
}
int main(void) {
// s1(행) -> s2(열)
char* s1 = "strong";
char* s2 = "storm";
int num_row = strlen(s1) + 1; // 처음의 " "(공백)을 포함하여 +1을 해준다. // 7
int num_col = strlen(s2) + 1; // 6
int **table = createTable(num_row, num_col); // 동적 배열을 생성해서 return 해준다.
populateTable(table, s1, s2, num_row, num_col); // table을 채우는 함수.
printf("\n----------------------Edit Distance----------------------\n");
printf("Edit distacne between %s and %s is %d\n",s1,s2,table[num_row-1][num_col-1]);
showOperationSequence(table, num_row, num_col);
}
실행결과
아래 실행 결과는 up, left, diag 중에서 가장 작은 값을 찾을 때,
diag에 우선권을 주지 않았을 때의 결과이다. (틀린 결과)
operation으로 edit distance를 계산해보면, 4(틀린 값)가 나오는 것을 확인할 수 있다.
